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