Loading [MathJax]/jax/output/HTML-CSS/jax.js

오일러의 정리

Euler's Theorem.

1 개요

정수론에서 유용하게 쓰이는 정리로, 합동식과 관련이 있다. 페르마의 소정리를 일반화한 것이다.

오일러에 의해 증명되었으며, 그 내용은 아래와 같다.

an이 서로 소인 양의 정수일 때,

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로 나눈 나머지가 서로 다르다 ( 만일 abiabj(mod n), 1i,jφ(n)인 서로 다른 정수 i, j가 존재한다면, a(bibj)n의 배수. an이 서로소이므로 bibjn의 배수. 그런데, bibj가 둘 다 1이상 n이하의 수들이므로 (n1)bibj(n1). 이 범위에는 n의 배수가 0뿐이므로 bi=bj. 즉, 모순)

그러므로 aS의 원소들을 n으로 나눈 나머지는 S의 원소들의 재배열이 된다.

따라서 S의 모든 원소의 곱과 aS의 모든 원소의 곱은 n으로 나눈 나머지가 같다.

b1bφ(n)aφ(n)b1bφ(n)(mod n)

 aφ(n)1(mod n)

2 응용

오일러 정리는 KMO 1차시험의 특성상 거듭제곱의 마지막 세 자리 수를 구하는 데 자주 사용된다. 예를 들어 72016의 마지막 세 자리 수를 구하고 싶을 때, φ(1000)=400이므로 74001(mod 1000)가 성립함을 이용하면, 72016(7400)5×716(mod 1000)에 의해 7161000으로 나눈 나머지를 구하면 된다. 참 쉽죠?

3 기타

오일러 정리는 대표적인 공개키 암호화 방식 중 하나인 RSA의 가장 중요한 이론이 되는 정리다.
참고로 오일러의 공식, 오일러 방정식과는 다른 것이다.