费马小定理详解

费马小定理

定义：

设 p 为素数，a 为整数，则 $a^p\equiv a(\mathrm{mod}p)$ ，若 $p\nmid a$ ，则 $a^{p-1}\equiv 1(\mathrm{mod}p)$

先证明若 $p\mid a$ ，证明过程如下：
$$\begin{gathered} \because p\mid a \\ a\mathrm{mod}p=0 \\ {a}^p\mathrm{mod}p=0 \end{gathered}$$
再证明当 $p\nmid a$ 时：

创建集合 $S=${ $x_1,x_2,x_3,\cdots ,x_{p-1}$} ，S为1，2，3，$\cdots$，p-1的一个 排列 ，$a{x}_1,a{x}_2,a{x}_3,\cdots ,a{x}_{p-1}$ ，任意两项模 p 不同余

若$\exists \forall i,j,╞1\le i<j<p$ ，使得 $a{x}_i\equiv a{x}_j(\mathrm{mod}p)$

则 $p\mid a(x_i-x_j)$

$\because p\nmid a,\therefore p\mid (x_i-x_j)$

又$\because x_i\mathrm{mod}p\ne x_j\mathrm{mod}p$

$\therefore 矛盾$

设$\forall k\in S,p\nmid S_k$

$\because a{x}_1\mathrm{mod}p,a{x}_2\mathrm{mod}p,\cdots ,a{x}_{p-1}\mathrm{mod}p$ 为1,2,3,$\cdots$ ，p-1的一个排列（上文已提到）

$\therefore (a{x}_1)(a{x}_2)(a{x}_3)\cdots (a{x}_{p-1})\equiv x_1\cdot x_2\cdot x_3\cdots x_{p-1}(\mathrm{mod}p)$
$$\begin{gathered} x_1\cdot x_2\cdot x_3\cdots x_{p-1} \\ =(p-1)(p-2)(p-3)\cdots 2\cdot 1 \\ =(p-1)! \end{gathered}$$
$\because p\nmid (p-1)!$

$\therefore a^{p-1}\equiv 1(\mathrm{mod}p)$

得证