오일러 정리

수론에서, 오일러 정리(영어: Euler’s theorem)는 페르마의 소정리를 일반화한 정리의 하나이다.

정의

정수 $a$ 및 양의 정수 $n$ 이 주어졌고, $a$ 와 $n$ 이 서로소라고 하자. 오일러 정리에 따르면, $a^{ϕ (n)}$ 과 1은 법 $n$ 에 대하여 합동이다.

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

증명

군론적 증명

정수환의 몫환 $ℤ / (n)$ 의 가역원군 $(ℤ / (n))^{\times}$ 을 생각하자. $ord a$ 가 $a$ 의 $(ℤ / (n))^{\times}$ 에서의 위수라고 하자. 라그랑주 정리에 따라, $ord a$ 는 가역원군의 크기 $ϕ (n)$ 의 약수이다. 즉,

ϕ (n) = k ord a

인 양의 정수 $k$ 가 존재한다. 따라서

a^{ϕ (n)} = a^{k ord a} = (a^{ord a})^{k} \equiv 1^{k} = 1 (\mod n)

이다.

수론적 증명

정수의 집합 ${x_{1}, x_{2}, \dots, x_{m}}$ 에 대한 다음 네 조건을 생각하자.

㈀ 만약 $i \neq j$ 라면, $x_{i} \equiv̸ x_{j} (\mod n)$ 이다.
㈁ 각 $i$ 에 대하여, $x_{i}$ 와 $n$ 은 서로소이다.
㈂ 만약 $x$ 와 $n$ 이 서로소라면, $x = x_{i} (\mod n)$ 인 $i$ 이 존재한다.
㈃ $m = ϕ (n)$

위 네 조건을 만족시키는 정수 집합은 반드시 존재한다. 예를 들어 ${0, 1, 2, \dots, n - 1}$ 속의 정수 가운데 $n$ 과 서로소인 것들의 집합은 네 조건을 모두 만족시킨다. 사실 각 조건은 남은 세 조건으로부터 유도될 수 있다. 예를 들어 ${x_{1}, x_{2}, \dots, x_{ϕ (n)}}$ 이 조건 ㈀, ㈁, ㈃을 만족시킨다고 하자. $r_{i} \in {0, 1, 2, \dots, n - 1}$ 가 $x_{i}$ 를 $n$ 으로 나눈 나머지라고 하자. 그렇다면 ${r_{1}, r_{2}, \dots, r_{ϕ (n)}}$ 역시 조건 ㈀, ㈁, ㈃을 만족시킨다. $ϕ$ 의 정의에 따라 이는 ${0, 1, 2, \dots, n - 1}$ 속에서 $n$ 과 서로소인 모든 정수의 집합이다. 만약 $x$ 와 $n$ 이 서로소라면, $x$ 는 그 $n$ 에 대한 나머지와 합동이며, 이 나머지는 $r_{i}$ 가운데 하나다.

위 네 조건을 만족시키는 정수 집합 ${x_{1}, x_{2}, \dots, x_{ϕ (n)}}$ 을 취하자. 이제, ${a x_{1}, a x_{2}, \dots, a x_{ϕ (n)}}$ 역시 네 조건을 만족시킴을 증명하자. 조건 ㈀, ㈁, ㈃을 만족시킴을 증명하면 충분하다.

조건 ㈀. $a x_{i} \equiv a x_{j} (\mod n)$ 라고 하자. $n$ 은 $a (x_{i} - x_{j})$ 의 약수이다. 즉, $n$ 의 중복도를 감안한 소인수들은 모두 $a (x_{i} - x_{j})$ 의 소인수이다. $a$ 와 $n$ 이 서로소이므로 $a$ 와 $n$ 은 소인수를 공유하지 않으며, 따라서 $n$ 의 중복도를 감안한 소인수들은 모두 $x_{i} - x_{j}$ 의 소인수이다. 즉, $n$ 은 $x_{i} - x_{j}$ 의 약수이다. 따라서 $x_{i} \equiv x_{j}$ 이며, $i = j$ 이다.

조건 ㈁. $a$ 와 $x_{i}$ 모두 $n$ 과 서로소이므로 그 곱 $a x_{i}$ 역시 $n$ 과 서로소다.

조건 ㈃. 첫 번째 조건에 따라 $a x_{i}$ 는 서로 합동이 아니며, 특히 서로 다르다.

이제, ${a x_{1}, a x_{2}, \dots, a x_{ϕ (n)}}$ 과 ${x_{1}, x_{2}, \dots, x_{ϕ (n)}}$ 이 조건 ㈀, ㈁, ㈂, ㈃을 만족시키므로, 각 $i \in {1, 2, \dots, ϕ (n)}$ 에 대하여,

x_{i} \equiv a x_{σ (i)} (\mod n)

인 $σ (i) \in {1, 2, \dots, ϕ (n)}$ 이 존재한다. $x_{i}$ 가 서로 합동이 아니므로 $a x_{σ (i)}$ 역시 서로 합동이 아니며, $σ (i)$ 는 서로 다르다. 즉, $σ : {1, 2, \dots, ϕ (n)} \to {1, 2, \dots, ϕ (n)}$ 은 단사 함수이며, ${1, 2, \dots, ϕ (n)}$ 이 유한 집합이므로 사실 이는 전단사 함수이다. 따라서

a^{ϕ (n)} \prod_{i = 1}^{n} x_{i} = \prod_{i = 1}^{n} a x_{σ (i)} \equiv \prod_{i = 1}^{n} x_{i} (\mod n)

이며, $\prod_{i = 1}^{n} x_{i}$ 와 $n$ 이 서로소이므로

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

이다.

예

페르마의 소정리

페르마의 소정리는 오일러 정리의 특수한 경우이다. 정수 $a$ 및 소수 $p$ 가 주어졌다고 하자. 또한, $p$ 가 $a$ 의 약수가 아니라고 하자. 그렇다면 $a$ 와 $p$ 는 서로소이다. $1, 2, \dots, p - 1$ 은 모두 $p$ 와 서로소이므로

ϕ (p) = p - 1

이다. 따라서

a^{p - 1} \equiv 1 (\mod p)

이다.

오일러 피 함숫값의 홀짝성

양의 정수 $n \geq 3$ 이 주어졌다고 하자. −1과 $n$ 은 서로소이므로, 오일러 정리에 따라

(- 1)^{ϕ (n)} \equiv 1 (\mod n)

이다. 즉, $ϕ (n)$ 은 짝수이다.

역사

스위스의 수학자 레온하르트 오일러가 증명하였다.

같이 보기

오일러 다면체 정리