若$(a,n)=1$，则$a^{\varphi(n)}\equiv 1(\mod n)$，其中$\varphi(n)$是$1\sim n$中与$n$互质的自然数的个数。
费马小定理是欧拉定理的特殊情况，当$n$为质数时，就是费马小定理。
12月28日 20:41举例：
若$(3,10)=1$，$\varphi(10)=10\times \left(1-\dfrac{1}{2} \right)\times \left(1-\dfrac{1}{5} \right)=4$，则$3^4\equiv 1(\mod 10)$
考虑$1$至$10$中与$10$互质的数：$1$、$3$、$7$、$9$，这$4$个数除以$10$的余数互不相同，那么
$1\times 3$、$3\times 3$、$7\times 3$、$9\times 3$这$4$个数除以$10$的余数也是互不相同的，假设这$4$个数中存在两个数$m\times 3$和$n\times 3$模$10$同余，即$m\times 3 \equiv n\times 3 (\mod 10)$，则$10|(m\times 3-n\times 3)=3(m-n)$，因为$(3,10)=1$，所以$10|m-n$，那么$m=n$，矛盾。
所以$1\times 3$、$3\times 3$、$7\times 3$、$9\times 3$这$4$个数除以$10$的余数互不相同，又不可能是$0$、$2$、$4$、$5$、$6$、$8$，所以只能是$1$、$3$、$7$、$9$
所以$(1\times 3)\times (3\times 3)\times (7\times 3)\times (9\times 3)\equiv 1\times 3\times 7\times 9(\mod 10)$
所以$3^4 \equiv 1(\mod 10)$
$1$至$n$中与$n$互质的自然数的个数是$\varphi(n)$个，记这$\varphi(n)$个数为$a_1$、$a_2$、$a_3$、$\cdots$、$a_{\varphi(n)}$，这$\varphi(n)$个数除以$n$的余数互不相同，那么$a\times a_1$、$a\times a_2$、$a\times a_3$、$\cdots$、$a\times a_{\varphi(n)}$除以$n$的余数也是互不相同的，若$a\times a_m$和$a\times a_n$模$n$同余，即$a\times a_m \equiv a\times a_n (\mod n)$，则$n|(a\times a_m-a\times a_n)=a(a_m-a_n)$，因为$(a,n)=1$，所以$n|a_m-a_n$，那么$a_m=a_n$，矛盾。
所以$a\times a_1$、$a\times a_2$、$a\times a_3$、$\cdots$、$a\times a_{\varphi(n)}$除以$n$的余数互不相同，只能为$a_1$、$a_2$、$a_3$、$\cdots$、$a_{\varphi(n)}$
所以$(a\times a_1)\cdot(a\times a_2)\cdots(a\times a_{\varphi(n)})\equiv a_1\cdot a_2\cdots a_{\varphi(n)}$
所以$a^{\varphi(n)}\equiv 1(\mod n)$
暂无评论内容