Euler's theorem

When \(a\) and \(n\) are coprime positive integers, then $$ a ^{\varphi(n)} \equiv 1 \quad (\text{mod}\ n) $$ where \(\varphi (n)\) is Euler’s totient function. 즉, \(n\)보다 작으면서 \(n\)과 서로소인 자연수의 갯수. 예를들어, \(\varphi(10) = 4 ( \{1, 3, 7, 9\})\). \(n\)이 prime이면 \(\varphi(n) = n-1\).

\(\mathbf{R}=\){\(x_1, x_2, \cdots, x_{\phi(n)}\)}을 reduced residue system (mod \(n\))이라고 하면, \(n\)과 coprime인 임의의 수 \(a\)를 곱했을 때, 다시 (순서만 뒤섞인) \(\mathbf{R}\)이 된다. 즉, {\(x_1, x_2, \cdots, x_{\phi(n)}\)} = {\(ax_1, ax_2, \cdots, ax_{\phi(n)}\)}. 왜냐하면 \(ax_j \equiv ax_k\) (mod \(n\))이면 \(j = k\)이어야 하기 때문이다.

따라서 $$\prod_{i=1}^{\varphi(n)} x_i \equiv \prod_{i=1}^{\varphi(n)} ax_i \equiv a^{\varphi(n)}\prod_{i=1}^{\varphi(n)} x_i \pmod{n}$$ 이고, 양변 cancel하면 \( a^{\varphi(n)}\equiv 1 \pmod{n}

. \ \square\)