证明：

如果 p 是一个素数，且 a 不能被 p 整除，那么：

$a^{p-1} \bmod p = 1$

1）构造集合 X:

$X = \{1, 2, ... ,p-1 \}$

2) 对集合 X 中的每个元素施以乘 a 模 p 操作得到集合 Y:

$Y = \{1a \bmod p, 2a\bmod p, ... ,(p-1)a \bmod p \}$

取集合 Y 中的任意两个元素， $y_{i} = i \times a \bmod p, y_{j} =j \times a \bmod p, (1 \leq i < j \leq p - 1)$ ，若这两个元素同余则有:

$\begin{align*}&i \times a \equiv j \times a ( \bmod p)\\&a(j - i) \equiv 0 ( \bmod p) \\\end{align*}$

由于 p 是素数, p 不能整除 a, 且 (j-i) < p, 所以只有当 i - j = 0 时才能整除 p;

换言之, Y 中的元素各不相同且均大于等于1 且小于等于(p-1);

所以集合X等于集合Y，顺序不一定一样，集合X所有元素的乘积必然等于集合Y所有元素的乘积:

$1 \times 2 \times ... \times (p-1) = (1a \bmod p) \times (2a \bmod p) \times ... \times ((p-1)a \bmod p)$

两边模 p :

$\begin{align*}(1 \times 2 \times ... \times (p-1)) \bmod p &=( (1a \bmod p) \times (2a \bmod p) \times ... \times ((p-1)a \bmod p)) \bmod p \\((p-1)!) \bmod p & = (a^{p-1} \times (p-1)!) \bmod p\end{align*}$

$a^{p-1} \times (p-1)! - (p-1)! \equiv 0 ( \bmod p)$

$(a^{p-1} -1) \times (p-1)! \equiv 0 ( \bmod p)$

由于 (p-1)! 不能被p整除, 所以

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

证毕

(若有误，望指正)

Proof of Fermat's Little Theorem 费尔马小定理证明

Proof of Fermat's Little Theorem 费尔马小定理证明

证明：