欧拉定理的证明

前提知识

1. $(a,b)$符号表示$a$与$b$的最大公因数，若$(a,b)=1$，则$a$与$b$互素
2. $\phi (m)$是指$[1,m]$中与m互素的数的个数。$[1,m]$中所有与$m$互素的数构成模$m$的简化剩余系。
3. 若$m$是一个正整数，$a$是满足$(a,m)=1$的数，若集合 K = { k 1 , k 2 , . . . k φ ( m ) } K=\{k_1,k_2,...k_{\varphi(m)}\} K={k1​,k2​,...kφ(m)​}遍历$m$的简化剩余系，则$a\cdot K$也遍历$m$的一个简化剩余系。

欧拉定理：

设$m$是大于1的整数。如果$a$是满足$(a,m)=1$的整数时，则
$$a^{\phi (m)}\equiv 1modn$$

证明：

证: 取$r_1,r_2,\cdots ,r_{\phi (m)}$为模$m$的一个最小简化剩余系，则当$a$是满足$(a,m)=1$的整数时，根据前提知识3，有
$$a\cdot r_1,a\cdot r_2,\cdots ,a\cdot r_{\phi (m)}$$
也为模$m$的一个简化剩余系。也就是说，$a\cdot r_1,a\cdot r_2,\cdots ,a\cdot r_{\phi (m)}$是$r_1,r_2,\cdots ,r_{\phi (m)}$模$m$的一个排列。因此有
$$(a\cdot r_1)\cdot (a\cdot r_2)\cdots (a\cdot r_{\phi (m)})\equiv r_1\cdot r_2\cdots r_{\phi (m)}modm$$
因此，
$$r_1{r}_2\cdots r_{\phi (m)}(a^{\phi (m)}-1)\equiv 0modm$$
又从$(r_1,m)=1,(r_2,m)=1,\cdots ,(r_{\phi (m)},m)=1$可以推出$r_1{r}_2\cdots r_{\phi (m)}$与$m$互素，即
$$(r_1{r}_2\cdots r_{\phi (m)},m)=1$$
所以
$$a^{\phi (m)}-1\equiv 0modn$$
即
$$a^{\phi (m)}\equiv 1modn$$