定理

令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