오일러 정리

오일러 정리(영어: Euler’s theorem)는 수론의 하나로, 페르마의 소정리를 일반화한 정리의 하나이다.

기하학 정리에 대해서는 오일러 삼각형 정리 문서를 참고하십시오.

정의

정수 ${\displaystyle a}$ 및 양의 정수 ${\displaystyle n}$이 주어졌고, ${\displaystyle a}$와 ${\displaystyle n}$이 서로소라고 하자. 오일러 정리에 따르면, ${\displaystyle a^{\phi (n)}}$과 1은 법 ${\displaystyle n}$에 대하여 합동이다.

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

증명

군론을 통한 증명

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

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

인 양의 정수 ${\displaystyle k}$가 존재한다. 따라서

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

이다.

군론을 사용하지 않는 증명

정수의 집합 ${\displaystyle \{x_{1},x_{2},\dots ,x_{m}\}}$에 대한 다음 네 조건을 생각하자.

• ㈀ 만약 ${\displaystyle i\neq j}$라면, ${\displaystyle x_{i}\not \equiv x_{j}{\pmod {n}}}$이다.
• ㈁ 각 ${\displaystyle i}$에 대하여, ${\displaystyle x_{i}}$와 ${\displaystyle n}$은 서로소이다.
• ㈂ 만약 ${\displaystyle x}$와 ${\displaystyle n}$이 서로소라면, ${\displaystyle x=x_{i}{\pmod {n}}}$인 ${\displaystyle i}$이 존재한다.
• ㈃ ${\displaystyle m=\phi (n)}$

위 네 조건을 만족시키는 정수 집합은 반드시 존재한다. 예를 들어 ${\displaystyle \{0,1,2,\dots ,n-1\}}$ 속의 정수 가운데 ${\displaystyle n}$과 서로소인 것들의 집합은 네 조건을 모두 만족시킨다. 사실 각 조건은 남은 세 조건으로부터 유도될 수 있다. 예를 들어 ${\displaystyle \{x_{1},x_{2},\dots ,x_{\phi (n)}\}}$이 조건 ㈀, ㈁, ㈃을 만족시킨다고 하자. ${\displaystyle r_{i}\in \{0,1,2,\dots ,n-1\}}$가 ${\displaystyle x_{i}}$를 ${\displaystyle n}$으로 나눈 나머지라고 하자. 그렇다면 ${\displaystyle \{r_{1},r_{2},\dots ,r_{\phi (n)}\}}$ 역시 조건 ㈀, ㈁, ㈃을 만족시킨다. ${\displaystyle \phi }$의 정의에 따라 이는 ${\displaystyle \{0,1,2,\dots ,n-1\}}$ 속에서 ${\displaystyle n}$과 서로소인 모든 정수의 집합이다. 만약 ${\displaystyle x}$와 ${\displaystyle n}$이 서로소라면, ${\displaystyle x}$는 그 ${\displaystyle n}$에 대한 나머지와 합동이며, 이 나머지는 ${\displaystyle r_{i}}$ 가운데 하나다.

위 네 조건을 만족시키는 정수 집합 ${\displaystyle \{x_{1},x_{2},\dots ,x_{\phi (n)}\}}$을 취하자. 이제, ${\displaystyle \{ax_{1},ax_{2},\dots ,ax_{\phi (n)}\}}$ 역시 네 조건을 만족시킴을 증명하자. 조건 ㈀, ㈁, ㈃을 만족시킴을 증명하면 충분하다.

조건 ㈀. ${\displaystyle ax_{i}\equiv ax_{j}{\pmod {n}}}$라고 하자. ${\displaystyle n}$은 ${\displaystyle a(x_{i}-x_{j})}$의 약수이다. 즉, ${\displaystyle n}$의 중복도를 감안한 소인수들은 모두 ${\displaystyle a(x_{i}-x_{j})}$의 소인수이다. ${\displaystyle a}$와 ${\displaystyle n}$이 서로소이므로 ${\displaystyle a}$와 ${\displaystyle n}$은 소인수를 공유하지 않으며, 따라서 ${\displaystyle n}$의 중복도를 감안한 소인수들은 모두 ${\displaystyle x_{i}-x_{j}}$의 소인수이다. 즉, ${\displaystyle n}$은 ${\displaystyle x_{i}-x_{j}}$의 약수이다. 따라서 ${\displaystyle x_{i}\equiv x_{j}}$이며, ${\displaystyle i=j}$이다.

조건 ㈁. ${\displaystyle a}$와 ${\displaystyle x_{i}}$ 모두 ${\displaystyle n}$과 서로소이므로 그 곱 ${\displaystyle ax_{i}}$ 역시 ${\displaystyle n}$과 서로소다.

조건 ㈃. 첫 번째 조건에 따라 ${\displaystyle ax_{i}}$는 서로 합동이 아니며, 특히 서로 다르다.

이제, ${\displaystyle \{ax_{1},ax_{2},\dots ,ax_{\phi (n)}\}}$과 ${\displaystyle \{x_{1},x_{2},\dots ,x_{\phi (n)}\}}$이 조건 ㈀, ㈁, ㈂, ㈃을 만족시키므로, 각 ${\displaystyle i\in \{1,2,\dots ,\phi (n)\}}$에 대하여,

${\displaystyle x_{i}\equiv ax_{\sigma (i)}{\pmod {n}}}$

인 ${\displaystyle \sigma (i)\in \{1,2,\dots ,\phi (n)\}}$이 존재한다. ${\displaystyle x_{i}}$가 서로 합동이 아니므로 ${\displaystyle ax_{\sigma (i)}}$ 역시 서로 합동이 아니며, ${\displaystyle \sigma (i)}$는 서로 다르다. 즉, ${\displaystyle \sigma \colon \{1,2,\dots ,\phi (n)\}\to \{1,2,\dots ,\phi (n)\}}$은 일대일 대응이다. 따라서

${\displaystyle a^{\phi (n)}\prod _{i=1}^{n}x_{i}=\prod _{i=1}^{n}ax_{\sigma (i)}\equiv \prod _{i=1}^{n}x_{i}{\pmod {n}}}$

이며, ${\displaystyle \textstyle \prod _{i=1}^{n}x_{i}}$와 ${\displaystyle n}$이 서로소이므로

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

이다.

예

페르마의 소정리

 이 부분의 본문은 페르마의 소정리입니다.

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

${\displaystyle \phi (p)=p-1}$

이다. 따라서

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

이다.

오일러 피 함숫값의 홀짝성

 이 부분의 본문은 오일러 피 함수입니다.

양의 정수 ${\displaystyle n\geq 3}$이 주어졌다고 하자. −1과 ${\displaystyle n}$은 서로소이므로, 오일러 정리에 따라

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

이다. 즉, ${\displaystyle \phi (n)}$은 짝수이다.

역사

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

같이 보기

• 오일러 다면체 정리