学习笔记：证费马小定理

· · 算法·理论

什么是费马小定理？

若 p 为质数，且 \gcd(a,p) = 1，则：

a^{p - 1} \equiv 1 \ \ (\bmod \ p)

对于任意整数 a，推广形式：

a^p \equiv a \ \ (\bmod \ p)

简单证明

设集合：

S = \{1,2,3,\cdots,p - 1 \}

不难发现，这些数都与 p 互质。

将集合内每一项都乘以符合 \gcd(a,p) = 1 的数 a，得：

S' = \{a \cdot 1,a \cdot 2,\cdots,a \cdot (p - 1) \}

可以看出，S' 只是 S 的一种排列。

所以：

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

消去公因式（因为 \gcd((p - 1)!,p) = 1），得：

a^{p - 1} \equiv 1 \ \ (\bmod \ p)

证毕。