오일러의 정리

[math]\displaystyle{ e^{ix}=\cos x+i\sin x }[/math]에 관한 내용은 오일러의 공식 문서를 읽어 주세요.

개요

페르마의 소정리를 좀 더 일반화시킨 버전. 레온하르트 오일러가 1763년에 증명했다고 알려져있다. 정리의 내용은 다음과 같다.

양의 정수 [math]\displaystyle{ n }[/math]과 정수 [math]\displaystyle{ a }[/math]에 관해, [math]\displaystyle{ \gcd\left(a,n\right)=1 }[/math]이면 [math]\displaystyle{ a^{\phi\left(n\right)}\equiv1\pmod n }[/math]이 성립한다 (단, [math]\displaystyle{ \phi\left(n\right) }[/math]은 오일러 파이 함수).

여기서 오일러 파이 함수란, [math]\displaystyle{ n }[/math]보다 작은 양의 정수 중에서 [math]\displaystyle{ n }[/math]과 서로소인 수들의 개수를 나타내는 함수다.

증명

집합 [math]\displaystyle{ R=\left\{r_1,r_2,\cdots,r_{\phi\left(n\right)}\right\} }[/math]을 법 [math]\displaystyle{ n }[/math]에 관한 기약잉여계라고 하자. 먼저, 집합 [math]\displaystyle{ A=\left\{ar_1,ar_2,\cdots,ar_{\phi\left(n\right)}\right\} }[/math]도 법 [math]\displaystyle{ n }[/math]에 관한 기약잉여계임을 보이겠다.

1. 만약 [math]\displaystyle{ ar_i\equiv ar_j\pmod n }[/math]이면, [math]\displaystyle{ \gcd\left(a,n\right)=1 }[/math]이기 때문에 [math]\displaystyle{ r_i\equiv r_j\pmod n }[/math]이다. 그런데 [math]\displaystyle{ r_i,\,r_j\in R }[/math]이기 때문에, 이게 가능한 경우는 [math]\displaystyle{ r_i=r_j }[/math]일 때 밖에 없다.
2. 만약 [math]\displaystyle{ \gcd\left(ar_i,n\right)\gt 1 }[/math]이면, 적당한 소수 [math]\displaystyle{ p }[/math]에 대해 [math]\displaystyle{ p\mid n }[/math]이고 [math]\displaystyle{ p\mid ar_i }[/math]이다. [math]\displaystyle{ p }[/math]가 소수이므로, [math]\displaystyle{ p\mid ar_i }[/math]이면 [math]\displaystyle{ p\mid a }[/math]이거나 [math]\displaystyle{ p\mid r_i }[/math]인데, 조건에서 [math]\displaystyle{ \gcd\left(a,n\right)=1 }[/math]이므로 [math]\displaystyle{ p\not\mid a }[/math]이고, [math]\displaystyle{ r_i\in R }[/math]이므로 [math]\displaystyle{ p\not\mid r_i }[/math]이다. 이는 모순이므로 모든 [math]\displaystyle{ i }[/math]에 관해 [math]\displaystyle{ \gcd\left(ar_i,n\right)=1 }[/math]이다.

따라서 집합 [math]\displaystyle{ A }[/math]는 법 [math]\displaystyle{ n }[/math]에 관한 기약잉여계이다. 즉, [math]\displaystyle{ R\equiv A\pmod n }[/math] (원소의 순서까지 같을 필요는 없다). 따라서, [math]\displaystyle{ ar_1\cdot ar_2\cdot\cdots\cdot ar_{\phi\left(n\right)}\equiv r_1\cdot r_2\cdot\cdots\cdot r_{\phi\left(n\right)}\pmod n }[/math]이다. 한편, [math]\displaystyle{ \gcd\left(r_i,n\right)=1 }[/math]이므로, [math]\displaystyle{ \gcd\left(r_1r_2\cdots r_{\phi\left(n\right)},n\right)=1 }[/math]이다. 따라서, [math]\displaystyle{ a^{\phi\left(n\right)}\equiv1\pmod n }[/math].

증명을 보면 알겠지만, 페르마의 소정리의 증명 방법과 거의 동일하다.

따름정리

• 페르마의 소정리: [math]\displaystyle{ n }[/math]이 소수이면 [math]\displaystyle{ \phi\left(n\right)=n-1 }[/math]이 되어 바로 증명이 된다.
• [math]\displaystyle{ \gcd\left(a,n\right)=1 }[/math]이면, [math]\displaystyle{ \bar{a}\equiv a^{\phi\left(n\right)-1} }[/math] ([math]\displaystyle{ \bar{a} }[/math]는 법 [math]\displaystyle{ n }[/math]에 관한 [math]\displaystyle{ a }[/math]의 역수).

추상대수학에서

군의 성질을 이용하여 오일러의 정리를 증명할 수도 있다. 먼저 약간의 표기법에 대해 집고 넘어가자. 책마다 표기법이 다를 수 있으므로 주의.

• [math]\displaystyle{ m\geq2 }[/math]인 정수이고, [math]\displaystyle{ a\in\mathbb{Z} }[/math]일 때, [math]\displaystyle{ \left[a\right]_m }[/math]를 법 [math]\displaystyle{ m }[/math]에 관한 congruence class라 정의한다. 즉, [math]\displaystyle{ \left[a\right]_m=\left\{b\in\mathbb{Z}\mid b\equiv a\pmod m\right\} }[/math]
• 법 [math]\displaystyle{ m }[/math]에 관한 congruence class들을 모아놓은 집합을 [math]\displaystyle{ \mathbb{I}_m }[/math]이라 정의한다.
• [math]\displaystyle{ U\left(\mathbb{I}_m\right) }[/math]를 [math]\displaystyle{ \mathbb{I}_m }[/math]의 원소 중, 법 [math]\displaystyle{ m }[/math]에 관해 역원을 가지는 원소들의 집합이라 정의한다.

여기서 [math]\displaystyle{ U\left(\mathbb{I}_m\right) }[/math]는 order가 [math]\displaystyle{ \phi\left(m\right) }[/math]인 multiplicative 아벨 군임이 알려져 있다. 또한, 유한한 order [math]\displaystyle{ n }[/math]을 가지는 임의의 군 [math]\displaystyle{ G }[/math]에 대해, [math]\displaystyle{ g\in G }[/math]이면 [math]\displaystyle{ g^n=1 }[/math]이다. 이를 [math]\displaystyle{ U\left(\mathbb{I}_m\right) }[/math]에 적용하면, [math]\displaystyle{ {\left[r\right]}_m^{\phi\left(m\right)}=\left[1\right]_m }[/math]이고, 이를 합동식으로 나타내면 [math]\displaystyle{ \gcd\left(r,m\right)=1 }[/math]인 [math]\displaystyle{ r }[/math]에 대해 [math]\displaystyle{ r^{\phi\left(m\right)}\equiv1\pmod m }[/math]임과 동치이다.

추상적으로 써 놓으니 뭔가 있어보이지만, 실제로 증명을 시도해보면 정수론적인 증명과 별반 다를게 없다. 유일하게 차이점이 발생하는 부분은 order에 관한 것.

같이 보기

• 페르마의 소정리