# 费马素性检验

## 概念

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$

${\displaystyle a^{n-1}\equiv 1{\pmod {n}}}$

${\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}$

 a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 最小的n值 4 341 91 15 4 35 6 9 4 9 10 65 4 15 14 15 4 25 6 21 4 21 22 25 4 9 26 9 4 49

## 缺点

${\displaystyle a\in (\mathbb {Z} /n\mathbb {Z} )^{*}}$

${\displaystyle (a\cdot a_{i})^{n-1}\equiv a^{n-1}\cdot a_{i}^{n-1}\equiv a^{n-1}\not \equiv 1{\pmod {n}}}$