若$p$是质数，且$(a,p)=1$，则$ a^{p-1} \equiv 1(\mod p)$。
举例：
$(2,7)=1$，则$2^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$的余数也是互不相同的，若$2m$和$2n$除以$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$的余数一定是$1$、$2$、$3$、$\cdots$、$6$，虽然顺序是乱的。
所以$(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)$
所以$ 2^{6} \equiv 1(\mod 7)$
$1$、$2$、$3$、$\cdots$、$p-1$，这$p-1$个数除以$p$的余数互不相同，那么
$a$、$2a$、$3a$、$\cdots$、$(p-1)a$除以$p$的余数也是互不相同的，若$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$的余数一定是$1$、$2$、$3$、$\cdots$、$p-1$，虽然顺序是乱的。
所以$a\cdot 2a\cdot 3a\cdots(p-1)a\equiv 1\cdot 2\cdot 3\cdots (p-1) (\mod p)$
所以$ a^{p-1} \equiv 1(\mod p)$
暂无评论内容