기약잉여계
$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$이다.
'수학' 카테고리의 다른 글
⟪발칙한 수학책⟫ 혜성처럼 등장한 유쾌한 수학책 (7) | 2021.06.26 |
---|---|
정수와 곱셈, 유리수의 정의 (1) | 2020.05.21 |
투퍼의 자기언급식 (Tupper's Self-Referential Formula) (0) | 2020.01.13 |
포함배제의 원리 고난도 문제 (0) | 2019.10.09 |
페아노 공리계 - 1+1=2 증명하기 (36) | 2018.11.11 |