오일러 정리

틀:위키데이터 속성 추적 틀:다른 뜻 오일러 정리(틀:Llang)는 수론의 하나로, 페르마의 소정리를 일반화한 정리의 하나이다.

정의

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

$a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$

증명

군론을 통한 증명

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

$\varphi (n)=k\mathrm{ord}a$

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

$a^{\varphi (n)}=a^{k\mathrm{ord}a}=(a^{\mathrm{ord}a}{)}^k\equiv 1^k=1(\mathrm{mod}n)$

이다.

군론을 사용하지 않는 증명

정수의 집합 $\{x_1,x_2,\dots ,x_m\}$에 대한 다음 네 조건을 생각하자.

• ㈀ 만약 $i\ne j$라면, $x_i\equiv ̸x_j(\mathrm{mod}n)$이다.
• ㈁ 각 $i$에 대하여, $x_i$와 $n$은 서로소이다.
• ㈂ 만약 $x$와 $n$이 서로소라면, $x=x_i(\mathrm{mod}n)$인 $i$이 존재한다.
• ㈃ $m=\varphi (n)$

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

위 네 조건을 만족시키는 정수 집합 $\{x_1,x_2,\dots ,x_{\varphi (n)}\}$을 취하자. 이제, $\{a{x}_1,a{x}_2,\dots ,a{x}_{\varphi (n)}\}$ 역시 네 조건을 만족시킴을 증명하자. 조건 ㈀, ㈁, ㈃을 만족시킴을 증명하면 충분하다.

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

조건 ㈁. $a$와 $x_i$ 모두 $n$과 서로소이므로 그 곱 $a{x}_i$ 역시 $n$과 서로소다.

조건 ㈃. 첫 번째 조건에 따라 $a{x}_i$는 서로 합동이 아니며, 특히 서로 다르다.

이제, $\{a{x}_1,a{x}_2,\dots ,a{x}_{\varphi (n)}\}$과 $\{x_1,x_2,\dots ,x_{\varphi (n)}\}$이 조건 ㈀, ㈁, ㈂, ㈃을 만족시키므로, 각 $i\in \{1,2,\dots ,\varphi (n)\}$에 대하여,

$x_i\equiv a{x}_{\sigma (i)}(\mathrm{mod}n)$

인 $\sigma (i)\in \{1,2,\dots ,\varphi (n)\}$이 존재한다. $x_i$가 서로 합동이 아니므로 $a{x}_{\sigma (i)}$ 역시 서로 합동이 아니며, $\sigma (i)$는 서로 다르다. 즉, $\sigma :\{1,2,\dots ,\varphi (n)\}\to \{1,2,\dots ,\varphi (n)\}$은 일대일 대응이다. 따라서

$a^{\varphi (n)}\prod _{i=1}^n{x}_i=\prod _{i=1}^{n}a{x}_{\sigma (i)}\equiv \prod _{i=1}^n{x}_i(\mathrm{mod}n)$

이며, ${\prod }_{i=1}^n{x}_i$와 $n$이 서로소이므로

$a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$

이다.

예

페르마의 소정리

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

$\varphi (p)=p-1$

이다. 따라서

$a^{p-1}\equiv 1(\mathrm{mod}p)$

이다.

오일러 피 함숫값의 홀짝성

틀:본문 양의 정수 $n\ge 3$이 주어졌다고 하자. −1과 $n$은 서로소이므로, 오일러 정리에 따라

$(-1{)}^{\varphi (n)}\equiv 1(\mathrm{mod}n)$

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

역사

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

같이 보기

• 오일러 다면체 정리