오일러의 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

오일러의 정리(Euler's theorem, -定理)는, 스위스수학자레온하르트 오일러가 만들어 낸 오일러 파이 함수와 관련된 정리이다. 다음과 같이 쓸 수 있다.

여기서 φ(n)는 오일러 파이 함수이다.

증명 방법[편집]

오일러의 정리를 증명하는 방법은 페르마의 소정리를 증명하는 방법과 거의 같다(실제로, 페르마의 소정리는 오일러의 정리의 따름정리이다). 즉, 합동식을 이용하는 것이다.

페르마의 소정리[편집]

오일러의 정리로 페르마의 소정리를 쉽게 유도할 수 있다. 페르마의 소정리란, 소수 p와 서로소인 임의의 정수 a에 대해,

a^{p-1} \equiv 1 \pmod{p}

가 성립한다는 정리이다. 이를 증명하기 위해, 오일러의 정리에서 n에 소수 p를 집어넣으면 된다.