费马小定理

定理内容：
$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: