定理内容：
$a$为自然数，$p$为一个质数。则有
$$
a^p \equiv a\ (mod\ p)
$$
其中 $\equiv$ 是同模符号，表示左右的数字对于p来说取模，是相等的。
证明：
数学归纳法
- 当$a = 1$时， 显然成立。
- 当$a = a$时，设 $p|(a^p - a)$，即$p$为$a^p - a$的约数。
- 则当$a = a + 1$时， 尝试证明 $p | ((a + 1)^p - (a + 1))$。
证明如下：
根据二项式定理，展开该项：
$$
\begin{aligned}
(a + 1)^p - (a + 1) &= \sum_{k=0}^{p}C_p^ka^k1^{p-k} -a - 1 \
&= C_p^0a^01^p + \sum_{k=1}^{p-1}C_p^ka^k1^{p-k} + C_p^pa^p1^0 - a - 1 \
&= 1 + \sum_{k=1}^{p-1}C_p^ka^k1^{p-k} + a^p - a - 1 \
&= \sum_{k=1}^{p-1}C_p^ka^k1^{p-k} + a^p - a
\end{aligned}
$$
因为$C_p^k = \frac{p!}{k!(p - k)!}$并且$p$为质数，所以$p$为$\sum_{k=1}^{p-1}C_p^ka^k1^{p-k}$的因数，即 $p\ | \sum_{k=1}^{p-1}C_p^ka^k1^{p-k}$。
又因为由假设2可知$p$为$a^p - a$的因数。所以$p$为$\sum_{k=1}^{p-1}C_p^ka^k1^{p-k} + a^p - a$的因数，即为$(a + 1)^p - (a + 1)$的因数。证毕。
应用：
如果$a$不是$p$的倍数，那么还有
$$
a^{p - 1} \equiv 1\ (mod\ p)
$$
所以可以用上式解决一些问题，如计算$2^{100}$模13。
因为2不是13的倍数，则$2^{13 - 1} \equiv 1 (mod \ 13)$。
$$
\begin{aligned}
2^{100} &= 2^{12 * 8 + 4} \ (mod \ 13)\
&= (2^{12})^8 * 2^4\ (mod \ 13)\
&= 1^8 * 2^4\ (mod \ 13)\
&= 16\ (mod\ 13)\
&= 3
\end{aligned}
$$
reference: