오일러 정리 (정수론)

NK590·2023년 10월 4일

설명

$a, n$ 이 각각 서로소인 자연수이고, 오일러 피 함수 $\varphi(n)$ 가 주어졌을 때, 다음과 같은 관계가 성립한다.

a^{\varphi(n)} \equiv 1 \mod n

이를 오일러 정리(Euler's theorem)라고 한다.

증명

정수 $n$ 보다 작고 $n$ 과 서로소인 정수의 집합 $M$ 을 생각하자. 이 때, 오일러 피 함수의 정의에 의해 $M$ 의 원소의 개수는 정확히 $\varphi(n)$ 개이다. 이를 $M$ 의 각각의 원소 $p$ 의 인덱스로 생각하면, 다음과 같이 나타낼 수 있다.

M = \{ p_1, p_2, \cdots, p_{\varphi(n)} \}

여기서, 집합 $M$ 의 각 원소에 $n$ 과 서로소인 자연수 $a$ 를 곱한 집합 $aM$ 을 생각한다.

aM = \{ ap_1, ap_2, \cdots, ap_{\varphi(n)} \}

Lemma. $M = aM$ 이다.
증명 : 귀류법을 통해 증명한다.
$M \neq aM$ 이라고 가정하자. 그렇다면, $aM$ 의 임의의 서로 다른 두 원소 $ap_i, ap_j$ 가 $\mod n$ 에서 같거나, 두 원소 중 하나 이상이 $n$ 과 서로소가 아니어야 한다.
여기서, $a$ 와 $n$ 은 서로소이고, $p_i, p_j$ 도 각각 $n$ 과 서로소이므로 $ap_i, ap_j$ 또한 $n$ 과 서로소이다.
그렇다면 $aM$ 의 임의의 두 원소 $ap_i, ap_j$ 에 대해 $ap_i \equiv ap_j\mod n$ 이어야 되고, 이는 $a(p_i - p_j) \equiv 0\mod n$ 을 의미하는데, $a$ 와 $n$ 은 서로소이므로 곧 $p_i - p_j\equiv 0\mod n$ , 즉 $p_i, p_j$ 는 $n$ 의 배수만큼 차이나야 된다. 그런데, 여기서 $M$ 의 정의에 의해 $p_i, p_j$ 의 차는 $0$ 보다 크고 $n$ 보다 작을 수밖에 없으므로, $M \neq aM$ 이라는 가정과 모순된다.

Lemma에 의해 $M = aM$ 이 보여졌으므로, $M$ 의 모든 원소의 곱 $p_1p_2\cdots p_{\varphi(n)}$ 과 $aM$ 의 모든 원소의 곱 $a^{\varphi(n)} p_1p_2\cdots p_{\varphi(n)}$ 도 같다. 즉, 다음이 성립한다.