최근 수정 시각 : 2022-06-12 20:12:56

오일러 정리

오일러의 정리에서 넘어옴
1. 개요2. 정수론에서의 오일러 정리
2.1. 증명
2.1.1. 다른 증명
2.2. 응용2.3. 기타
3. 동차함수에 대한 오일러 정리
3.1. 오일러 정리의 미분


Euler's theorem

1. 개요

레온하르트 오일러가 증명한 정리이다. 오일러 정리는 정수론에서의 정리와 동차함수에서의 정리로 구분된다.

2. 정수론에서의 오일러 정리

정수론
Number Theory
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px"
공리
페아노 공리계 · 정렬 원리 · 수학적 귀납법
산술
나눗셈 약수·배수 배수 · 약수( 소인수) · 소인수분해( 목록) · 공배수 · 공약수 · 최소공배수 · 최대공약수
약수들의 합에 따른 수의 분류 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 부부수 · 반완전수 · 불가촉 수 · 괴짜수
정리 베주 항등식 · 산술의 기본정리 · 나눗셈 정리
기타 유클리드 호제법 · 서로소
디오판토스 방정식 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버츠와 스위너톤-다이어 추측(미해결)
모듈러 연산
잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리
소수론
수의 분류 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수( 사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수
분야 대수적 정수론 · 해석적 정수론
함수 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수· 체비쇼프 함수 · 소수생성다항식
정리 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)( 천의 정리) · 폴리냑 추측(미해결) · 소수 정리
기타 에라토스테네스의 체 · 윌런스의 공식
}}}}}}}}} ||

정수론에서 유용하게 쓰이는 정리로, 합동식과 관련이 있다. 페르마의 소정리를 일반화한 것이다.
내용은 아래와 같다.
[math( a )]와 [math( n )]이 서로 소인 양의 정수일 때,
[math( a^{ \varphi \left( n \right) } \equiv 1 \left( \text{mod}\ n \right) )]

여기서 [math( \varphi \left( n \right) )]은 [math( 1 )]부터 [math( n )]까지의 정수 중 [math( n )]과 서로소인 정수의 개수를 구하는 오일러 파이 함수다.

2.1. 증명

[math(n)] 이하의 자연수중 [math(n)]과 서로소인 수만 모아놓은 집합을 [math(S)]라 하자.
정의에 의해 [math(S)]의 원소의 개수는 [math( \varphi \left( n \right) )]이다.

[math( S=\left\{b_1, \cdots, b_{\varphi\left(n\right)}\right\} )]

라 하자

[math(S)]의 각 원소들에 ([math(n)]과 서로소인) [math(a)]를 곱한 집합을 [math(aS)]라 하면
[math( aS=\left\{ab_1, \cdots, ab_{\varphi\left(n\right)}\right\} )]

이때, [math(aS)]의 모든 원소들은 [math(n)]과 서로소인 수들끼리 곱한 수들이므로 그 원소들 역시 [math(n)]과 서로소.

그리고 [math(aS)]의 모든 원소는 [math(n)]로 나눈 나머지가 서로 다르다 ([math(\because)] 만일 [math(ab_i \equiv ab_j (\text{mod}~n))], [math(1 \leq i,j \leq \varphi \left(n \right))]인 서로 다른 정수 [math(i)], [math(j)]가 존재한다면, [math(a(b_i - b_j ))]가 [math(n)]의 배수. [math(a)]와 [math(n)]이 서로소이므로 [math(b_i - b_j)]가 [math(n)]의 배수. 그런데, [math(b_i)]와 [math(b_j)]가 둘 다 [math(1)]이상 [math(n)]이하의 수들이므로 [math(-(n-1) \leq b_i -b_j \leq (n-1))]. 이 범위에는 [math(n)]의 배수가 [math(0)]뿐이므로 [math(b_i = b_j)]. 즉, 모순)

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

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

[math( b_1\cdots b_{\varphi\left(n\right)} \equiv a^{\varphi\left(n\right)}b_1\cdots b_{\varphi\left(n\right)} \left(\text{mod} ~n\right))]

[math( \therefore ~ a^{ \varphi \left( n \right) } \equiv 1 \left( \text{mod}~ n \right) )]

2.1.1. 다른 증명

[math(n)] 이하의 자연수중 [math(n)]과 서로소인 수만 모아놓은 집합을 [math(S)]라 하자.
정의에 의해 [math(S)]의 원소의 개수는 [math( \varphi n )]이다.

그러면, 자명하게 [math(S)]는 [math(\bmod n)] 곱셈군을 이루고, 라그랑주 정리에 의해 [math(|S:\langle a\rangle||\langle a\rangle | = |S|=\varphi (n))]로 [math(a)]의 위수는 [math(\varphi(n)]의 약수이다. 따라서, [math(a^{\varphi(n))})]는 곱셈의 항등원 [math(1)]이 된다.

2.2. 응용

오일러 정리는 거듭제곱의 마지막 세 자리 수를 구하는 데 자주 사용된다. 예를 들어 [math(7^{2016})]의 마지막 세 자리 수를 구하고 싶을 때, [math(\varphi \left( 1000 \right) = 400)]이므로 [math(7^{400} \equiv 1 \left(\text{mod}~1000 \right))]가 성립함을 이용하면, [math(7^{2016} \equiv \left( 7^{400} \right)^5 \times 7^{16} \left( \text{mod}~1000 \right))]에 의해 [math(7^{16})]을 [math(1000)]으로 나눈 나머지를 구하면 된다.[1]

2.3. 기타

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

3. 동차함수에 대한 오일러 정리

해석학 · 미적분학
Analysis · Calculus
{{{#!wiki style="word-break: keep-all; margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px; letter-spacing: -1px"
<colbgcolor=#8f76d6> 함수 합성 · 항등원 · 역원 · 멱함수( 비례·반비례 ) · 초등함수( 대수함수 · 초월함수) · 특수함수 · 범함수 · 다변수 ( 동차 · 숨은 함수( 다가 함수)) · 그래프 · 대칭 · 증감표 · 극값 · 연속 · 매끄러움 · 계단형 · 미끄럼틀형 · 볼록/오목 · 닮은꼴 함수 · 병리적 함수 · 해석적 연속 · 로그함수 · 지수함수 · 삼각함수
정리 · 토픽 좌표계 · 중간값 정리 · 최대·최소 정리 · 부동점 정리 · 오일러 동차함수 정리 · 립시츠 규칙
극한 부정형 · 어림( 유효숫자 ) · 근방 · 수열의 극한 · 엡실론-델타 논법 · 수렴 ( 균등수렴 ) · 발산 · 점근선 · 무한대 · 무한소 · 스털링 근사
정리 · 토픽 로피탈의 정리 · 슈톨츠-체사로 정리
수열
급수
규칙과 대응 · 단조 수렴 정리 · 멱급수 · 테일러 급수 ( 일람 ) · 조화급수 · 그란디 급수 · 망원급수 ( 부분분수분해 ) · 오일러 수열 · 베르누이 수열 · 파울하버의 공식 · 리만 재배열 정리
정리 · 토픽 바젤 문제 · 라마누잔합 · 0.999…=1 · 콜라츠 추측미해결
미적분 미분 도함수 일람 · 차분 · 유율법 · 변화량 · 변분법 · 도함수 ( 편도함수 ) · 곱미분 · 몫미분 · 연쇄 법칙 · 역함수 정리 · 임계점 ( 변곡점 · 안장점 ) · 미분형식 · 미분방정식 ( 풀이 ) · [math(boldsymbolnabla)] · 라그랑주 승수법
적분 역도함수 일람 · 부분적분 ( LIATE 법칙 · 도표적분법 · 예제 ) · 치환적분 · 정적분 ( 예제 ) · 이상적분 · 중적분 ( 선적분 · 면적분 · 야코비안 ) · 르베그 적분 · 스틸체스 적분 · 코시 주요값
정리 · 토픽 평균값 정리 ( 롤의 정리 ) · 스토크스 정리 ( 발산 정리 · 그린 정리 ) · 라플라스 변환 · 푸리에 해석 ( 푸리에 변환 ) · 아다마르 변환 · 미적분의 기본정리 · 2학년의 꿈 · 리시 방법

해석
측도론 ( 측도 · 르베그 측도 ) · 유계( 콤팩트성 ) · 칸토어 집합 · 비탈리 집합
정리 · 토픽
복소
해석
복소평면 · 편각 · 코시-리만 방정식
정리 · 토픽 오일러 공식 ( 드 무아브르 공식 ) · 리우빌의 정리 · 바이어슈트라스 분해 정리 · 미타그레플레르 정리
여타 하위 학문 수치해석학 ( FEM ) · 미분기하학 · 해석기하학 · 해석적 정수론 ( 소수 정리 ) · 벡터 미적분학( 야코비 공식 · 비앙키 항등식) · 확률론 ( 중심극한정리 )
기타 뉴턴-랩슨 방법 · 디랙 델타 함수 · 리만 가설미해결 · 카오스 이론미해결 · merry=x-mas
응용 수리물리학 · 수리경제학( 경제수학) · 공업수학 }}}}}}}}}


함수 [math(f(x_k))]가 [math(x_k)]에 대한 [math(n)]차 동차함수이면, 다음이 성립한다.
[math(\displaystyle \sum_{k}{ x_k \frac{ \partial f }{ \partial x_k } } = nf )]

3.1. 오일러 정리의 미분

n차 동차 함수에 대한 오일러 정리는 다음과 같다.
[math(\displaystyle x\frac{ \partial f}{ \partial x} + y\frac{ \partial f}{ \partial y} = nf(x,y) )]
이제 [math(n)]차 동차 함수의 정의를 사용하여, 오일러 정리가 연쇄 법칙을 따르는 것을 확인할 수 있다. 임의의 실수 [math(\lambda)]를 가정할때, [math(n)]차 동차 함수는 다음과 같다.
[math(f(\lambda x,\lambda y) = \lambda^n f(x,y))]

양측에 대해 미분할때, 왼쪽 식에 연쇄 법칙을 적용하자. [math(u=\lambda x, v=\lambda y)]로 치환하여 [math(f(\lambda x,\lambda y)=f(u,v))]를 가정하면,
[math(\dfrac{\partial f}{\partial u} \dfrac{{\rm d}u}{{\rm d}\lambda} +\dfrac{\partial f}{\partial v} \dfrac{{\rm d}v}{{\rm d}\lambda} = n\lambda^{n-1}f(x,y))]

그러므로,
[math(\displaystyle x\frac{ \partial f}{ \partial u} + y\frac{ \partial f}{ \partial v} = n\lambda^{n-1}f(x,y) )]



[1] 물론 이는 [math(7^2=49=50-1)]임을 이용해서 이항정리를 통해 간략화시키면 된다.