费马小定理
lunivia
·
·
算法·理论
- 若 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