数论四大定理之费马小定理

先举一个费马的例子：
$\because 2$、$3$、$4$、$5$、$6$都与$7$互质
$\therefore 2^{6} \equiv 3^{6} \equiv 4^{6} \equiv 5^{6} \equiv 6^{6} \equiv 1(\mod 7)$

$1$、$2$、$3$、$\cdots$、$6$，这$6$个数除以$7$的余数互不相同，那么$1\times 2$、$2\times 2$、$3\times 2$、$\cdots$、$6\times 2$除以$7$的余数也是互不相同的，我们可以验证一下：

$1\times 2 \equiv 2 (\mod 7)$
$2\times 2 \equiv 4 (\mod 7)$
$3\times 2 \equiv 6 (\mod 7)$
$4\times 2 \equiv 1 (\mod 7)$
$5\times 2 \equiv 3 (\mod 7)$
$6\times 2 \equiv 5 (\mod 7)$

这是为什么呢，我们可以用反证法来证明：

假设$m\times 2$和$n\times 2$除以$7$余数相同了，其中$m$和$n$是$1$~$6$中的某两个数，即

$m\times 2 \equiv n\times 2 (\mod 7)$，由同余的性质，则$7|2m-2n=2(m-n)$，又$(2$，$7)=1$，所以$7|m-n$，则$m=n$，矛盾。即$1\times 2$、$2\times 2$、$3\times 2$、$\cdots$、$6\times 2$除以$7$的$6$个余数一定是互不相同且不为$0$，那么只能是$1$、$2$、$3$、$\cdots$、$6$，虽然顺序是乱的。

$\therefore (2\times 1)\times (2\times 2)\times (3\times 2)\times \cdots \times (6\times 2)\equiv 1\cdot 2\cdot 3\cdots 6 (\mod 7)$

$\therefore 2^{6} \equiv 1(\mod 7)$

现在正式来证明费马小定理

$1$、$2$、$3$、$\cdots$、$p-1$，这$p-1$个数除以$p$的余数互不相同，那么$a$、$2a$、$3a$、$\cdots$、$(p-1)a$除以$p$得到的$p-1$个余数也是互不相同的。采用反证法：

假设$ma$和$na$除以$p$余数相同，则$p|ma-na=(m-n)a$，又$(a$，$p)=1$，所以$p|m-n$，则$m=n$，矛盾。即$a$、$2a$、$3a$、$\cdots$、$(p-1)a$除以$p$的$p-1$个余数一定不为$0$且互不相同，那么只能是$1$、$2$、$3$、$\cdots$、$p-1$，虽然顺序是乱的。

$\therefore a\cdot 2a\cdot 3a\cdots(p-1)a\equiv 1\cdot 2\cdot 3\cdots (p-1) (\mod p)$

$\therefore a^{p-1} \equiv 1(\mod p)$

来几道习题

$2^{35} \equiv (2^{6} )^{5} \times 2^{5} \equiv 1 \times 32 \equiv 4 (\mod 7)$

$2222^{5555} \equiv 3^{5555} \equiv (3^{6} )^{925} \times 3^{5} \equiv 1\times 243 \equiv 5(\mod 7)$

$5555^{2222} \equiv 4^{2222} \equiv (4^{6} )^{370} \times 4^{2} \equiv 1\times 16 \equiv 2 (\mod 7)$

$8888^{2222} \equiv 8^{2222} \equiv (8^{36} )^{61} \times 8^{26} \equiv 2^{78} \equiv (2^{36} )^{2} \times 2^{6} \equiv 64 \equiv 27(\mod 37) $