오일러 정리의 증명

기약잉여계

$n$과 서로소인 수 $b_1, b_2, \cdots, b_{\phi(n)}$을 생각하자($\phi(n)$은 $1$부터 $n$까지 $n$과 서로소인 수의 개수).

이 수들로 이루어진 집합 $S$를 생각하자.
$$
S = \lbrace b_1, b_2, \cdots, b_{\phi(n)} \rbrace
$$
$S$의 각 원소에 $n$과 서로소인 수 $a$를 곱한 집합을 $aS$라 하자.
$$
aS = \lbrace ab_1, ab_2, \cdots, ab_{\phi(n)} \rbrace
$$
이 때 다음 Lemma가 성립한다.

$i \neq j$에 대해 $ab_i \not\equiv ab_j \quad (\bmod n)$이다.

증명은 귀류법으로 한다.

만약 $ab_i \equiv ab_j$인 $i, j$가 존재한다면, $a(b_i - b_j) \equiv 0$이다.

그런데 $a$는 $n$과 서로소이므로, $b_i - b_j \equiv 0$이다.

그런데 $i \neq j$이므로 이는 불가능하다.

따라서 모순.

 

이로부터 $S$와 $aS$ 모두 서로 다른 $\phi(n)$개의 원소를 가지고 있으므로, 두개가 동일한 집함임을 알 수 있다.

오일러 정리

$S$와 $aS$가 동일한 집합이므로 각 집합의 모든 원소를 곱한 값도 같다. 따라서,
$$
b_1b_2 \cdots b_{\phi(n)} \equiv a^{\phi(n)}b_1b_2 \cdots b_{\phi(n)}
$$
이다. 이로부터 $a^{\phi(n)} \equiv 1$임을 알 수 있다. 이가 오일러 정리이다.

오일러 정리: $a$와 $n$이 서로소일 때, $a^{\phi(n)} \equiv 1$이다.