附录1 费马小定理的证明

作为数论的基础定理之一，费马小定理被后世数学家开发出了许多种思路截然不同的证明方法，在动力系统发展之后，还诞生了基于不定点的证明方法，即构造一个迭代映射，分析其不动点或周期点的个数与性质，结合计数原理导出同余关系。这里我们主要介绍经典构造法与数学归纳法。

法1：构造法

此为莱布尼茨和欧拉的经典证法。

原定理表述:设p为素数，整数a不整除p,则 $a^{p - 1} \equiv 1 (m o d p)$ .

现在证明ia被p除得的余数两两不同，其中i=1,2,…p-1.

假设存在 $1 \leq s, t \leq p - 1$ ，使得 $s a \equiv t a (m o d p)$ ,则 $(s - t) a \equiv 0 (m o d p)$ .

由于a不整除p，则 $s \equiv t (m o d p)$ .

又由于 $1 \leq s, t \leq p - 1$ ,

故s=t.得证。

将a,2a,3a…(p-1)a乘在一起，得

$a \cdot 2 a \cdot 3 a \cdot . . . \cdot (p - 1) a \equiv 1 \cdot 2 \cdot . . . \cdot (p - 1) (m o d p)$

即

$(p - 1)! a^{p - 1} \equiv (p - 1)! (m o d p)$

由于p是素数，则 $(p - 1)$ !被p除结果不为零，于是两边可同时除以(p-1)!，得

$a^{p - 1} \equiv 1 (m o d p)$

于是费马小定理得证。

法2：归纳法

当a=1时，对任意的素数p，都显然有 $1^{p - 1} \equiv 1 (m o d p)$ 成立；

假设a=k时成立，则对于a=k+1,有 ${(k + 1)}^{p} = k^{p} + (\begin{matrix} p \\ 1 \end{matrix}) k^{p - 1} + . . . + (\begin{matrix} p \\ p - 1 \end{matrix}) k + 1$ ，

由于 $(\begin{matrix} p \\ 1 \end{matrix})$ , … , $(\begin{matrix} p \\ p - 1 \end{matrix})$ 均能整除p，故 ${(k + 1)}^{p} \equiv k^{p} + 1 (m o d p)$ ，

由假设，知 $k^{p} \equiv k (m o d p)$ ，于是 ${(k + 1)}^{p} \equiv k + 1 (m o d p)$ 成立，得证。