오일러 정리

1. 개요

오일러 정리는 정수 a와 양의 정수 n이 서로소일 때, a의 φ(n) 제곱이 법 n에 대해 1과 합동이라는 정리이다. 이 정리는 페르마의 소정리의 일반화이며, 군론과 직접적인 방법으로 증명될 수 있다. 오일러 정리는 큰 수의 거듭제곱을 특정 수로 나눈 나머지를 구하는 데 활용되며, 오일러 피 함수의 값과 페르마의 소정리를 이해하는 데에도 사용된다.

2. 정의

정수 $a$와 양의 정수 $n$이 주어졌고, $a$와 $n$이 서로소일 때, 오일러 정리는 다음과 같다.
:$a^\{\backslash phi(n)\}\backslash equiv\; 1\backslash pmod\; n$
여기서 $\backslash varphi\; (n)$는 오일러의 φ 함수이다.

이 정리는 페르마의 소정리를 일반화한 것이며, 더 나아가 카마이클의 정리로 일반화할 수 있다.

3. 증명

오일러 정리는 군론을 사용하거나, 군론을 사용하지 않고 직접 증명할 수 있다.

각각의 증명 방법에 대해서는 하위 섹션에서 자세히 설명한다.

3.1. 군론을 통한 증명

정수환의 몫환 $\backslash mathbb\; Z/(n)$의 가역원군 $(\backslash mathbb\; Z/(n))^\backslash times$을 생각하자. $\backslash operatorname\{ord\}a$가 $a$의 $(\backslash mathbb\; Z/(n))^\backslash times$에서의 위수라고 할 때, 라그랑주 정리에 따라 $\backslash operatorname\{ord\}a$는 가역원군의 크기 $\backslash phi(n)$의 약수이다. 즉,
:$\backslash phi(n)=k\backslash operatorname\{ord\}a$
인 양의 정수 $k$가 존재한다. 따라서
:$a^\{\backslash phi(n)\}=a^\{k\backslash operatorname\{ord\}a\}=(a^\{\backslash operatorname\{ord\}a\})^k\backslash equiv\; 1^k=1\backslash pmod\; n$
이다.

$n$과 서로소인 $n$의 잉여류는 곱셈 아래에서 군을 형성한다. (정수 모듈로 n의 곱셈군 참조) 그 군의 차수는 $\backslash phi(n)$이다. 라그랑주의 정리에 따르면 유한군의 부분군의 차수는 전체 군의 차수를 나누며, 이 경우 $\backslash phi(n)$이다. 만약 $a$가 $n$과 서로소인 임의의 숫자라면 $a$는 이 잉여류 중 하나에 속하며, $a,\; a^2,\; \backslash dots,\; a^k$ 모듈로 $n$의 거듭제곱은 잉여류 군의 부분군을 형성하며, $a^k\; \backslash equiv\; 1\; \backslash pmod\; n$이다. 라그랑주의 정리에 따르면 $k$는 $\backslash phi(n)$을 나누어야 하며, 즉 $kM\; =\; \backslash phi(n)$인 정수 $M$이 존재한다. 이는 다음을 의미한다.
:$a^\{\backslash varphi(n)\}\; =\; a^\{kM\}\; =\; (a^\{k\})^M\; \backslash equiv\; 1^M\; =1\; \backslash pmod\{n\}.$

3.2. 군론을 사용하지 않는 증명

$n$과 서로소인 $n$ 이하의 양의 정수 집합을 $\backslash \{x\_1,x\_2,\backslash dots,x\_\{\backslash phi(n)\}\backslash \}$이라 하자. 이 집합의 각 원소에 $a$를 곱한 집합 $\backslash \{ax\_1,ax\_2,\backslash dots,ax\_\{\backslash phi(n)\}\backslash \}$ 역시 $n$과 서로소인 $n$ 이하의 양의 정수 집합과 법 $n$에 대해 합동이다. 즉, 두 집합은 합동류 집합 ($\backslash mod\; n$)으로 간주하면 동일하다(집합으로서 순서는 다를 수 있음). 따라서 두 집합의 모든 원소의 곱은 서로 합동이다($\backslash mod\; n$).

:$$
\prod_{i=1}^{\varphi(n)} x_i \equiv
\prod_{i=1}^{\varphi(n)} ax_i =
a^{\varphi(n)}\prod_{i=1}^{\varphi(n)} x_i \pmod{n},


소거 법칙을 사용하여 각 $x\_i$를 소거하면 오일러 정리를 얻는다.

:$$
a^{\varphi(n)}\equiv 1 \pmod{n}.


이는 다음과 같이 표현할 수도 있다. $n$과 서로소인 $n$ 이하의 양의 정수 집합을 $A=\backslash \{b\_1,b\_2,...,b\_\{\backslash varphi(n)\}\backslash \}$이라 하자. 이 집합의 각 원소에 $a$를 곱한 집합 $B=\backslash \{ab\_1,ab\_2,...,ab\_\{\backslash varphi(n)\}\backslash \}$을 생각하면, $a$와 $n$은 서로소이므로 집합 $A$와 $B$는 법 $n$에 대해 일치하고, 그 곱도 법 $n$에서 같다. 즉, $A$의 원소의 곱을 $P$라고 하면,

:$P\backslash equiv\; a^\{\backslash varphi(n)\}P\backslash pmod\{n\}$

$n$과 $P$는 서로소이므로

:$a^\{\backslash varphi(n)\}\backslash equiv\; 1\backslash pmod\{n\}$ 이다.

4. 예

예를 들어 7²⁰⁰⁹의 아래 두 자릿수를 구하는 방법은 다음과 같다.

오일러 피 함수(100)=40이므로, 오일러 정리에 따라 7⁴⁰≡ 1 (mod 100)이다.

따라서 7²⁰⁰⁹=7⁹× (7⁴⁰)⁵⁰≡ 7⁹≡ 7 (mod 100)이므로, 아래 두 자릿수는 07이다.

4.1. 페르마의 소정리

페르마의 소정리는 오일러 정리의 특수한 경우이다. 정수 $a$ 및 소수 $p$가 주어졌다고 하자. 또한, $p$가 $a$의 약수가 아니라고 하면, $a$와 $p$는 서로소이다. $1,2,\backslash dots,p-1$은 모두 $p$와 서로소이므로,
:$\backslash phi(p)=p-1$
이다. 따라서
:$a^\{p-1\}\; \backslash equiv\; 1\; \backslash pmod\{p\}$
이다.

4.2. 오일러 피 함숫값의 홀짝성

$n\backslash ge\; 3$일 때, -1과 $n$은 서로소이므로, 오일러 정리에 따라
:$(-1)^\{\backslash phi(n)\}\backslash equiv\; 1\backslash pmod\; n$
이다. 즉, $\backslash phi(n)$은 짝수이다.

4.3. 응용 예시

오일러 정리에 따르면, $\backslash varphi(100)=40$이므로,
:$7^\{40\}\backslash equiv\; 1\backslash pmod\{100\}$이다.

따라서 $7^\{2009\}=7^9\backslash times\; (7^\{40\})^\{50\}\backslash equiv\; 7^9\backslash equiv\; 7\backslash pmod\{100\}$이 된다.

그러므로 7²⁰⁰⁹의 아래 두 자릿수는 07이 된다.

5. 역사

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