费马小定理 (Fermat's little theorem) 是数论中的一个重要定理，在1636年提出。
如果 pp 是一个质数，而整数 aa 不是 pp 的倍数，则有
ap−1≡1(modp)a^{p-1}≡1 \pmod p
或者写成
ap≡a(modp)a^{p}≡a \pmod p
证明 1
设一个质数为 pp，我们取一个不为 pp 倍数的数 aa。
构造一个序列：A={1,2,3…,p−1}A=\{1,2,3\dots,p-1\}，这个序列有着这样一个性质：
∏i=1p−1 Ai≡∏i=1p−1(Ai×a)(modp)\prod_{i=1}^{p-1}\space A_i\equiv\prod_{i=1}^{p-1} (A_i\times a) \pmod p
证明：
∵(Ai,p)=1,(Ai×a,p)=1\because (A_i,p)=1,(A_i\times a,p)=1
又因为每一个 Ai×a(modp)A_i\times a \pmod p 都是独一无二的，且 Ai×a(modp)<pA_i\times a \pmod p < p
得证（每一个 Ai×aA_i\times a 都对应了一个 AiA_i）
设 f=(p−1)!f=(p-1)!, 则 f≡a×A1×a×A2×a×A3⋯×Ap−1(modp)f\equiv a\times A_1\times a\times A_2\times a \times A_3 \dots \times A_{p-1} \pmod p
ap−1×f≡f(modp)ap−1≡1(modp)\begin{aligned} a^{p-1}\times f &\equiv f \pmod p \\ a^{p-1} &\equiv 1 \pmod p \end{aligned}
证毕。
证明 2
用归纳法证明：
显然 1p≡1(modp)1^p\equiv 1\pmod p，假设 ap≡a(modp)a^p\equiv a\pmod p 成立，那么通过二项式定理有
(a+1)p=ap+(p1)ap−1+(p2)ap−2+⋯+(pp−1)a+1(a+1)^p=a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{p-1}a+1
因为 (pk)=p(p−1)⋯(p−k+1)k!\binom{p}{k}=\frac{p(p-1)\cdots (p-k+1)}{k!} 对于 1≤k≤p−11\leq k\leq p-1 成立，在模 pp 意义下 (p1)≡(p2)≡⋯≡(pp−1)≡0(modp)\binom{p}{1}\equiv \binom{p}{2}\equiv \cdots \equiv \binom{p}{p-1}\equiv 0\pmod p，那么 (a+1)p≡ap+1(modp)(a+1)^p \equiv a^p +1\pmod p，将 ap≡a(modp)a^p\equiv a\pmod p 带入得 (a+1)p≡a+1(modp)(a+1)^p\equiv a+1\pmod p 得证。
使用原根证明
假设 aa 和 pp 互质，那么我们可以表示 aa 为原根的某种幂次形式：
a≡gk(modp).a \equiv g^k \pmod{p}.
因为 gp−1≡1(modp)g^{p-1} \equiv 1 \pmod{p}（根据原根的定义），所以：
ap−1≡gk(p−1)=(gp−1)k≡1k=1(modp).a^{p-1} \equiv g^{k(p-1)} = (g^{p-1})^k \equiv 1^k = 1 \pmod{p}.
因此：
ap−1≡1(modp).a^{p-1} \equiv 1 \pmod{p}.
素数检测
若有整数 aa 满足 an≢a(modn)a^n\not\equiv a \pmod n，那么 nn 为合数.
证明：由费马小定理逆否命题得到.
扩展到更高次幂pkp^k 的情况
apk≡a(modp)a^{p^k} \equiv a \pmod{p}
证明：
(1) 当 a≡0(modp)a \equiv 0 \pmod{p} 显然成立.
(2) 当 a≢0(modp)a \not\equiv 0 \pmod{p}：
由费马小定理得：
ap≡a(modp).a^p \equiv a \pmod{p}.
注意到：
apk=(apk−1)p.a^{p^k} = (a^{p^{k-1}})^p.
根据费马小定理的性质，对apk−1a^{p^{k-1}} 再取幂pp，仍然保持同余：
(apk−1)p≡apk−1(modp).(a^{p^{k-1}})^p \equiv a^{p^{k-1}} \pmod{p}.
通过递归应用 kk 次费马小定理，可以证明：
apk≡a(modp).a^{p^k} \equiv a \pmod{p}.