오일러 정리 문서 원본 보기

{{위키데이터 속성 추적}}
{{다른 뜻|오일러 삼각형 정리||기하학 정리}}
'''오일러 정리'''({{llang|en|Euler’s theorem}})는 [[수론]]의 하나로, [[페르마의 소정리]]를 일반화한 정리의 하나이다.

== 정의 ==
정수 <math>a</math> 및 양의 정수 <math>n</math>이 주어졌고, <math>a</math>와 <math>n</math>이 [[서로소 아이디얼|서로소]]라고 하자. '''오일러 정리'''에 따르면, <math>a^{\phi(n)}</math>과 1은 법 <math>n</math>에 대하여 [[모듈러 산술|합동]]이다.
:<math>a^{\phi(n)}\equiv 1\pmod n</math>

== 증명 ==
=== 군론을 통한 증명 ===
[[정수환]]의 [[몫환]] <math>\mathbb Z/(n)</math>의 [[가역원군]] <math>(\mathbb Z/(n))^\times</math>을 생각하자. <math>\operatorname{ord}a</math>가 <math>a</math>의 <math>(\mathbb Z/(n))^\times</math>에서의 위수라고 하자. [[라그랑주 정리 (군론)|라그랑주 정리]]에 따라, <math>\operatorname{ord}a</math>는 가역원군의 크기 <math>\phi(n)</math>의 약수이다. 즉,
:<math>\phi(n)=k\operatorname{ord}a</math>
인 양의 정수 <math>k</math>가 존재한다. 따라서
:<math>a^{\phi(n)}=a^{k\operatorname{ord}a}=(a^{\operatorname{ord}a})^k\equiv 1^k=1\pmod n</math>
이다.

=== 군론을 사용하지 않는 증명 ===
정수의 집합 <math>\{x_1,x_2,\dots,x_m\}</math>에 대한 다음 네 조건을 생각하자.
* ㈀ 만약 <math>i\ne j</math>라면, <math>x_i\not\equiv x_j\pmod n</math>이다.
* ㈁ 각 <math>i</math>에 대하여, <math>x_i</math>와 <math>n</math>은 서로소이다.
* ㈂ 만약 <math>x</math>와 <math>n</math>이 서로소라면, <math>x=x_i\pmod n</math>인 <math>i</math>이 존재한다.
* ㈃ <math>m=\phi(n)</math>
위 네 조건을 만족시키는 정수 집합은 반드시 존재한다. 예를 들어 <math>\{0,1,2,\dots,n-1\}</math> 속의 정수 가운데 <math>n</math>과 서로소인 것들의 집합은 네 조건을 모두 만족시킨다. 사실 각 조건은 남은 세 조건으로부터 유도될 수 있다. 예를 들어 <math>\{x_1,x_2,\dots,x_{\phi(n)}\}</math>이 조건 ㈀, ㈁, ㈃을 만족시킨다고 하자. <math>r_i\in\{0,1,2,\dots,n-1\}</math>가 <math>x_i</math>를 <math>n</math>으로 나눈 나머지라고 하자. 그렇다면 <math>\{r_1,r_2,\dots,r_{\phi(n)}\}</math> 역시 조건 ㈀, ㈁, ㈃을 만족시킨다. <math>\phi</math>의 정의에 따라 이는 <math>\{0,1,2,\dots,n-1\}</math> 속에서 <math>n</math>과 서로소인 모든 정수의 집합이다. 만약 <math>x</math>와 <math>n</math>이 서로소라면, <math>x</math>는 그 <math>n</math>에 대한 나머지와 합동이며, 이 나머지는 <math>r_i</math> 가운데 하나다.

위 네 조건을 만족시키는 정수 집합 <math>\{x_1,x_2,\dots,x_{\phi(n)}\}</math>을 취하자. 이제, <math>\{ax_1,ax_2,\dots,ax_{\phi(n)}\}</math> 역시 네 조건을 만족시킴을 증명하자. 조건 ㈀, ㈁, ㈃을 만족시킴을 증명하면 충분하다.

조건 ㈀. <math>ax_i\equiv ax_j\pmod n</math>라고 하자. <math>n</math>은 <math>a(x_i-x_j)</math>의 약수이다. 즉, <math>n</math>의 중복도를 감안한 소인수들은 모두 <math>a(x_i-x_j)</math>의 소인수이다. <math>a</math>와 <math>n</math>이 서로소이므로 <math>a</math>와 <math>n</math>은 소인수를 공유하지 않으며, 따라서 <math>n</math>의 중복도를 감안한 소인수들은 모두 <math>x_i-x_j</math>의 소인수이다. 즉, <math>n</math>은 <math>x_i-x_j</math>의 약수이다. 따라서 <math>x_i\equiv x_j</math>이며, <math>i=j</math>이다.

조건 ㈁. <math>a</math>와 <math>x_i</math> 모두 <math>n</math>과 서로소이므로 그 곱 <math>ax_i</math> 역시 <math>n</math>과 서로소다.

조건 ㈃. 첫 번째 조건에 따라 <math>ax_i</math>는 서로 합동이 아니며, 특히 서로 다르다.

이제, <math>\{ax_1,ax_2,\dots,ax_{\phi(n)}\}</math>과 <math>\{x_1,x_2,\dots,x_{\phi(n)}\}</math>이 조건 ㈀, ㈁, ㈂, ㈃을 만족시키므로, 각 <math>i\in\{1,2,\dots,\phi(n)\}</math>에 대하여,
:<math>x_i\equiv ax_{\sigma(i)}\pmod n</math>
인 <math>\sigma(i)\in\{1,2,\dots,\phi(n)\}</math>이 존재한다. <math>x_i</math>가 서로 합동이 아니므로 <math>ax_{\sigma(i)}</math> 역시 서로 합동이 아니며, <math>\sigma(i)</math>는 서로 다르다. 즉, <math>\sigma\colon\{1,2,\dots,\phi(n)\}\to\{1,2,\dots,\phi(n)\}</math>은 일대일 대응이다. 따라서
:<math>a^{\phi(n)}\prod_{i=1}^nx_i=\prod_{i=1}^nax_{\sigma(i)}\equiv\prod_{i=1}^nx_i\pmod n</math>
이며, <math>\textstyle\prod_{i=1}^nx_i</math>와 <math>n</math>이 서로소이므로
:<math>a^{\phi(n)}\equiv 1\pmod n</math>
이다.

== 예 ==
=== 페르마의 소정리 ===
{{본문|페르마의 소정리}}
[[페르마의 소정리]]는 오일러 정리의 특수한 경우이다. 정수 <math>a</math> 및 [[소수 (수론)|소수]] <math>p</math>가 주어졌다고 하자. 또한, <math>p</math>가 <math>a</math>의 약수가 아니라고 하자. 그렇다면 <math>a</math>와 <math>p</math>는 서로소이다. <math>1,2,\dots,p-1</math>은 모두 <math>p</math>와 서로소이므로
:<math>\phi(p)=p-1</math>
이다. 따라서
:<math>a^{p-1} \equiv 1 \pmod{p}</math>
이다.

=== 오일러 피 함숫값의 홀짝성 ===
{{본문|오일러 피 함수}}
양의 정수 <math>n\ge 3</math>이 주어졌다고 하자. −1과 <math>n</math>은 서로소이므로, 오일러 정리에 따라
:<math>(-1)^{\phi(n)}\equiv 1\pmod n</math>
이다. 즉, <math>\phi(n)</math>은 짝수이다.

== 역사 ==
[[스위스]]의 [[수학자]] [[레온하르트 오일러]]가 증명하였다.

== 같이 보기 ==
* [[오일러 다면체 정리]]

[[분류:수론]]
[[분류:수론 정리]]
[[분류:모듈러 산술]]
[[분류:레온하르트 오일러]]