费马小定理

若 $p$ 是素数且 $\gcd(a,p)=1$ ，则 $a^p\equiv a\pmod p$ ，也可以表示为 $a^{p-1}\equiv 1\pmod p$ 。

证明方法1：

构造集合

A=\{1,2,\dots,p-1\}

。若

\gcd(a,p)=1

，则

a,2a,\dots,(p-1)a

在模

p

后互不相同。

用反证法证：若

ai\equiv aj\pmod p,i,j\in[1,p-1],i\ne j

，则

a(i-j)\equiv 0\pmod p

。显然不成立。

\prod\limits_{i=1}^{p-1}A_i\equiv \prod\limits_{i=1}^{p-1}(A_ia)\pmod p

(p-1)!\equiv a^{p-1}(p-1)!\pmod a

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

证明方法2：

用数学归纳法。

首先

1^p\equiv 1\pmod p

显然成立。

假设对于

a

时

a^p\equiv a\pmod p

成立，那么验证

a+1

时是否成立。

二项式展开：

(a+1)^p=a^p+\begin{pmatrix}p\\1\end{pmatrix}a+\begin{pmatrix}p\\2\end{pmatrix}a^2+\dots+\begin{pmatrix}p\\p-1\end{pmatrix}a^{p-1}+1

当

1\le i\le p-1

时

\begin{pmatrix}p\\i\end{pmatrix}=\frac{p(p-1)\dots(p-i+1)}{i!}

，在模

p

意义下都为

0

，所以：

(a+1)^p\equiv a^p+1\equiv a+1\pmod p

文章操作