学习笔记：证费马小定理

什么是费马小定理？

若

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)

证毕。