抽象代数/群论/子群/循环子群/欧拉函数定理

定理

令n 为一个正整数。令x 为一个与n 互质的整数。令 φ(n) = 小于且与n 互质的正整数的个数

$x^{\varphi (n)}\equiv 1{\pmod {n}}$

证明

$\mathbb {Z} /n^{\times }$ 在模n 乘法下是一个群，包含小于且与整数n 互质的正整数。

φ(n) = o($\mathbb {Z} /n^{\times }$)

令 X 为 $\mathbb {Z} /n^{\times }$ 由 x 模 n 生成的循环子群。

由于 X 是 $\mathbb {Z} /n^{\times }$ 的子群

0. o(X) 整除 o($\mathbb {Z} /n^{\times }$)

1. o($\mathbb {Z} /n^{\times }$) / o(X) 是一个整数

2. $x^{\varphi (n)}=x^{o(\mathbb {Z} /n^{\times })}=x^{o(X)o(\mathbb {Z} /n^{\times })/o(X)}=[x^{o(X)}]^{o(\mathbb {Z} /n^{\times })/o(X)}=e^{o(\mathbb {Z} /n^{\times })/o(X)}=e$