Euler's Theorem.
1 개요
정수론에서 유용하게 쓰이는 정리로, 합동식과 관련이 있다. 페르마의 소정리를 일반화한 것이다.
오일러에 의해 증명되었으며, 그 내용은 아래와 같다.
a와 n이 서로 소인 양의 정수일 때,aφ(n)≡1(mod n)
여기서 φ(n)은 1부터 n까지의 정수 중 n과 서로소인 정수의 개수이다. 오일러 피 함수라고도 부른다.
n 이하의 자연수중 n과 서로소인 수만 모아놓은 집합을 S라 하자.
정의에 의해 S의 원소의 개수는 φ(n)이다.
S={b1,⋯,bφ(n)}
라 하자
S의 각 원소들에 (n과 서로소인) a를 곱한 집합을 aS라 하면
aS={ab1,⋯,abφ(n)}
이 때, aS의 모든 원소들은 n과 서로소인 수들끼리 곱한 수들이므로 그 원소들 역시 n과 서로소.
그리고 aS의 모든 원소는 n로 나눈 나머지가 서로 다르다 (∵ 만일 abi≡abj(mod n), 1≤i,j≤φ(n)인 서로 다른 정수 i, j가 존재한다면, a(bi−bj)가 n의 배수. a와 n이 서로소이므로 bi−bj가 n의 배수. 그런데, bi와 bj가 둘 다 1이상 n이하의 수들이므로 −(n−1)≤bi−bj≤(n−1). 이 범위에는 n의 배수가 0뿐이므로 bi=bj. 즉, 모순)
그러므로 aS의 원소들을 n으로 나눈 나머지는 S의 원소들의 재배열이 된다.
따라서 S의 모든 원소의 곱과 aS의 모든 원소의 곱은 n으로 나눈 나머지가 같다.
b1⋯bφ(n)≡aφ(n)b1⋯bφ(n)(mod n)
∴ aφ(n)≡1(mod n)
2 응용
오일러 정리는 KMO 1차시험의 특성상 거듭제곱의 마지막 세 자리 수를 구하는 데 자주 사용된다. 예를 들어 72016의 마지막 세 자리 수를 구하고 싶을 때, φ(1000)=400이므로 7400≡1(mod 1000)가 성립함을 이용하면, 72016≡(7400)5×716(mod 1000)에 의해 716을 1000으로 나눈 나머지를 구하면 된다. 참 쉽죠?
3 기타
오일러 정리는 대표적인 공개키 암호화 방식 중 하나인 RSA의 가장 중요한 이론이 되는 정리다.
참고로 오일러의 공식, 오일러 방정식과는 다른 것이다.