맨위로가기

오일러 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

오일러 정리는 정수 a와 양의 정수 n이 서로소일 때, a의 φ(n) 제곱이 법 n에 대해 1과 합동이라는 정리이다. 이 정리는 페르마의 소정리의 일반화이며, 군론과 직접적인 방법으로 증명될 수 있다. 오일러 정리는 큰 수의 거듭제곱을 특정 수로 나눈 나머지를 구하는 데 활용되며, 오일러 피 함수의 값과 페르마의 소정리를 이해하는 데에도 사용된다.

2. 정의

정수 a와 양의 정수 n이 주어졌고, a와 n이 서로소일 때, '''오일러 정리'''는 다음과 같다.

:a^{\phi(n)}\equiv 1\pmod n

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

이 정리는 페르마의 소정리를 일반화한 것이며, 더 나아가 카마이클의 정리로 일반화할 수 있다.

3. 증명

오일러 정리는 군론을 사용하거나, 군론을 사용하지 않고 직접 증명할 수 있다.

각각의 증명 방법에 대해서는 하위 섹션에서 자세히 설명한다.

3. 1. 군론을 통한 증명

정수환의 몫환 \mathbb Z/(n)의 가역원군 (\mathbb Z/(n))^\times을 생각하자. \operatorname{ord}a가 a의 (\mathbb Z/(n))^\times에서의 위수라고 할 때, 라그랑주 정리에 따라 \operatorname{ord}a는 가역원군의 크기 \phi(n)의 약수이다. 즉,

:\phi(n)=k\operatorname{ord}a

인 양의 정수 k가 존재한다. 따라서

:a^{\phi(n)}=a^{k\operatorname{ord}a}=(a^{\operatorname{ord}a})^k\equiv 1^k=1\pmod n

이다.[3]

n과 서로소인 n의 잉여류는 곱셈 아래에서 군을 형성한다. (정수 모듈로 ''n''의 곱셈군 참조) 그 군의 차수는 \phi(n)이다. 라그랑주의 정리에 따르면 유한군의 부분군의 차수는 전체 군의 차수를 나누며, 이 경우 \phi(n)이다. 만약 a가 n과 서로소인 임의의 숫자라면 a는 이 잉여류 중 하나에 속하며, a, a^2, \dots, a^k 모듈로 n의 거듭제곱은 잉여류 군의 부분군을 형성하며, a^k \equiv 1 \pmod n이다. 라그랑주의 정리에 따르면 k는 \phi(n)을 나누어야 하며, 즉 kM = \phi(n)인 정수 M이 존재한다. 이는 다음을 의미한다.

:a^{\varphi(n)} = a^{kM} = (a^{k})^M \equiv 1^M =1 \pmod{n}.

3. 2. 군론을 사용하지 않는 증명

n과 서로소인 n 이하의 양의 정수 집합을 \{x_1,x_2,\dots,x_{\phi(n)}\}이라 하자. 이 집합의 각 원소에 a를 곱한 집합 \{ax_1,ax_2,\dots,ax_{\phi(n)}\} 역시 n과 서로소인 n 이하의 양의 정수 집합과 법 n에 대해 합동이다.[4][5] 즉, 두 집합은 합동류 집합 (\mod n)으로 간주하면 동일하다(집합으로서 순서는 다를 수 있음). 따라서 두 집합의 모든 원소의 곱은 서로 합동이다(\mod n).[6]

:

\prod_{i=1}^{\varphi(n)} x_i \equiv

\prod_{i=1}^{\varphi(n)} ax_i =

a^{\varphi(n)}\prod_{i=1}^{\varphi(n)} x_i \pmod{n},



소거 법칙을 사용하여 각 x_i를 소거하면 오일러 정리를 얻는다.

:

a^{\varphi(n)}\equiv 1 \pmod{n}.



이는 다음과 같이 표현할 수도 있다. n과 서로소인 n 이하의 양의 정수 집합을 A=\{b_1,b_2,...,b_{\varphi(n)}\}이라 하자. 이 집합의 각 원소에 a를 곱한 집합 B=\{ab_1,ab_2,...,ab_{\varphi(n)}\}을 생각하면, a와 n은 서로소이므로 집합 A와 B는 법 n에 대해 일치하고, 그 곱도 법 n에서 같다. 즉, A의 원소의 곱을 P라고 하면,

:P\equiv a^{\varphi(n)}P\pmod{n}

n과 P는 서로소이므로

:a^{\varphi(n)}\equiv 1\pmod{n} 이다.

4. 예

예를 들어 72009의 아래 두 자릿수를 구하는 방법은 다음과 같다.

오일러 피 함수(100)=40이므로, '''오일러 정리'''에 따라 740≡ 1 (mod 100)이다.

따라서 72009=79× (740)50≡ 79≡ 7 (mod 100)이므로, 아래 두 자릿수는 07이다.

4. 1. 페르마의 소정리

페르마의 소정리는 오일러 정리의 특수한 경우이다. 정수 a 및 소수 p가 주어졌다고 하자. 또한, p가 a의 약수가 아니라고 하면, a와 p는 서로소이다. 1,2,\dots,p-1은 모두 p와 서로소이므로,

:\phi(p)=p-1

이다. 따라서

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

이다.

4. 2. 오일러 피 함숫값의 홀짝성

n\ge 3일 때, -1과 n은 서로소이므로, 오일러 정리에 따라

:(-1)^{\phi(n)}\equiv 1\pmod n

이다. 즉, \phi(n)은 짝수이다.

4. 3. 응용 예시

오일러 정리에 따르면, \varphi(100)=40이므로,

:7^{40}\equiv 1\pmod{100}이다.

따라서 7^{2009}=7^9\times (7^{40})^{50}\equiv 7^9\equiv 7\pmod{100}이 된다.

그러므로 72009의 아래 두 자릿수는 07이 된다.

5. 역사

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

참조

[1] 논문 Theorematum quorundam ad numeros primos spectantium demonstratio https://books.google[...] Commentarii academiae scientiarum Petropolitanae 1741
[2] 논문 Theoremata arithmetica nova methodo demonstrata https://books.google[...] Novi Commentarii academiae scientiarum Petropolitanae 1763
[3] 서적 Ireland & Rosen, corr. 1 to prop 3.3.2
[4] 서적 Hardy & Wright, thm. 72
[5] 서적 Landau, thm. 75
[6] 문서 Bézout's lemma


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com