오일러 정리
Euler's Theorem.
1. 개요
레온하르트 오일러가 증명한 정리이다.
2. 정수론에서
정수론에서 유용하게 쓰이는 정리로, 합동식과 관련이 있다. 페르마의 소정리를 일반화한 것이다.
내용은 아래와 같다.
여기서 $$ \varphi \left( n \right) $$은 $$ 1 $$부터 $$ n $$까지의 정수 중 $$ n $$과 서로소인 정수의 개수를 구하는 오일러 파이 함수다.$$ a $$와 $$ n $$이 서로 소인 양의 정수일 때,
$$ a^{ \varphi \left( n \right) } \equiv 1 \left( \text{mod}\ n \right) $$ [1]
2.1. 증명
$$n$$ 이하의 자연수중 $$n$$과 서로소인 수만 모아놓은 집합을 $$S$$라 하자.
정의에 의해 $$S$$의 원소의 개수는 $$ \varphi \left( n \right) $$이다.
$$ S=\left\{b_1, \cdots, b_{\varphi\left(n\right)}\right\} $$
라 하자
$$S$$의 각 원소들에 ($$n$$과 서로소인) $$a$$를 곱한 집합을 $$aS$$라 하면
$$ aS=\left\{ab_1, \cdots, ab_{\varphi\left(n\right)}\right\} $$
이 때, $$aS$$의 모든 원소들은 $$n$$과 서로소인 수들끼리 곱한 수들이므로 그 원소들 역시 $$n$$과 서로소.
그리고 $$aS$$의 모든 원소는 $$n$$로 나눈 나머지가 서로 다르다 ($$\because$$ 만일 $$ab_i \equiv ab_j (\text{mod}~n)$$, $$1 \leq i,j \leq \varphi \left(n \right)$$인 서로 다른 정수 $$i$$, $$j$$가 존재한다면, $$a(b_i - b_j )$$가 $$n$$의 배수. $$a$$와 $$n$$이 서로소이므로 $$b_i - b_j$$가 $$n$$의 배수. 그런데, $$b_i$$와 $$b_j$$가 둘 다 $$1$$이상 $$n$$이하의 수들이므로 $$-(n-1) \leq b_i -b_j \leq (n-1)$$. 이 범위에는 $$n$$의 배수가 [math(0)]뿐이므로 $$b_i = b_j$$. 즉, 모순)
그러므로 $$aS$$의 원소들을 $$n$$으로 나눈 나머지는 $$S$$의 원소들의 재배열이 된다.
따라서 $$S$$의 모든 원소의 곱과 $$aS$$의 모든 원소의 곱은 $$n$$으로 나눈 나머지가 같다.
$$ b_1\cdots b_{\varphi\left(n\right)} \equiv a^{\varphi\left(n\right)}b_1\cdots b_{\varphi\left(n\right)} \left(\text{mod} ~n\right)$$
$$ \therefore ~ a^{ \varphi \left( n \right) } \equiv 1 \left( \text{mod}~ n \right) $$
2.2. 응용
오일러 정리는 거듭제곱의 마지막 세 자리 수를 구하는 데 자주 사용된다. 예를 들어 $$7^{2016}$$의 마지막 세 자리 수를 구하고 싶을 때, $$\varphi \left( 1000 \right) = 400$$이므로 $$7^{400} \equiv 1 \left(\text{mod}~1000 \right)$$가 성립함을 이용하면, $$7^{2016} \equiv \left( 7^{400} \right)^5 \times 7^{16} \left( \text{mod}~1000 \right)$$에 의해 $$7^{16}$$을 $$1000$$으로 나눈 나머지를 구하면 된다. [2]
2.3. 기타
오일러 정리는 대표적인 공개키 암호화 방식 중 하나인 RSA의 가장 중요한 이론이 되는 정리다.
참고로 오일러 공식, 오일러 방정식과는 다른 것이다.
3. 동차함수에 대한 오일러 정리
위의 정수론에 대한 정리와는 다른 정리이다. 내용은 다음과 같다.
함수 $$f(x_k)$$가 $$x_k$$에 대한 $$n$$차 동차함수이면, 다음이 성립한다.