欧拉定理证明

证明\(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}\] 证毕。