欧拉定理证明

证明$a^{\varphi (m)} \equiv 1 \pmod{m}$,其中$(a,m)=1$,$\varphi (x)$为欧拉函数。

证明

取出区间$[1,m-1]$内和$m$互质的$\varphi (m)$个数$p_1, p_2 \cdots p_{\varphi (m)}$。根据简化剩余系的性质,对于任意一个满足$(a,m)=1$的$a$,这$\varphi (m)$个数同时乘以$a$再模$m$,得到的序列仍然是$p_1, p_2 \cdots p_{\varphi (m)}$的一个排列。所以我们得到:

$$\prod_{i = 1}^{\varphi (m)} p_i \equiv \prod_{i =1}^{\varphi (m)} a \cdot p_i \pmod{m}$$

提取$a$,得到

$$ \prod_{i = 1}^{\varphi (m)} p_i \equiv a^{\varphi (m)} \prod_{i =1}^{\varphi (m)} p_i \pmod{m} $$

由于$(p_i, m) = 1$,所以同余关系两边的$p_i$可以被消去:

$$1 \equiv a^{\varphi (m)} \pmod{m}$$

证毕。

说点什么

avatar
50
  Subscribe  
提醒