오일러 함수와 오일러 정리

오일러 $\phi$ 함수

양의 정수 $m$에 대하여, $m$ 이하의 양의 정수 중에서 $m$과 서로 소인 수의 개수를 오일러의 $\phi$-함수라 하며 $\phi (m)$으로 나타낸다.

$$\phi (m)=m\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_n}\right)$$

여기서 $p_1,p_2,\dots ,p_n$은 $m$의 서로 다른 소인수이다.

예를 들어 $\phi (12)=12\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=4$, $\phi (100)=100\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)=40$, $\phi (1000)=1000\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)=400$이다.

$a,b$가 서로 소인 양의 정수이고, $p$가 소수이며 $m$이 양의 정수일 때

1. $\phi (ab)=\phi (a)\cdot \phi (b)$ ¹
2. $\phi (p^m)=p^m-p^{m-1}$ ²

오일러 정리

양의 정수 $n$에 대하여, $\gcd (a,n)=1$이면

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

예를 들어 $\phi (40)=16$이고, $\gcd (9,40)=1$이므로 $9^{16}\equiv 1(\mathrm{mod}40)$이다.

증명

$\phi (n)=r$라고 하고, $\{a_1,a_2,\dots ,a_r\}$을 법 $n$에 대한 기약 잉여계라 하자. $a$와 $n$이 서로 소이므로, 곱해진 집합 $\{a{a}_1,a{a}_2,\dots ,a{a}_r\}$도 법 $n$에 대한 기약 잉여계이다.

따라서 곱셈한 전체값은

$$(a{a}_1)(a{a}_2)\cdots (a{a}_r)\equiv a_1{a}_2\cdots a_r(\mathrm{mod}n)$$

즉,

$$a^r\cdot (a_1{a}_2\cdots a_r)\equiv a_1{a}_2\cdots a_r(\mathrm{mod}n)$$

이다. $a_1{a}_2\cdots a_r$와 $n$은 서로소이므로 약분 가능하고,

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

가 된다.

예제

1. $33^{100}$을 $40$으로 나눈 나머지를 구하여라. ³

2. $2009^{1002}$를 $100$으로 나눈 나머지를 구하여라. ⁴

3. $n^{1998}-4$가 $17$의 배수가 되는 $n$의 최소값을 구하여라. ⁵

Footnotes

1. $a=p_1^{e_1}\cdot p_2^{e_2}\cdots p_n^{e_n}$, $b=q_1^{f_1}\cdot q_2^{f_2}\cdots q_m^{f_m}$ 이면, $ab=p_1^{e_1}\cdot p_2^{e_2}\cdots p_n^{e_n}\cdot q_1^{f_1}\cdot q_2^{f_2}\cdots q_m^{f_m}$ 이고, $\phi (ab)=ab\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_n}\right)\left(1-\frac{1}{q_1}\right)\left(1-\frac{1}{q_2}\right)\cdots \left(1-\frac{1}{q_m}\right)=\phi (a)\cdot \phi (b)$이다. ↩

2. $\phi (p^m)=p^m\left(1-\frac{1}{p}\right)=p^m-p^{m-1}$이다. ↩

3. 오일러 정리에 의해 $33^{16}\equiv 1(\mathrm{mod}40)$이므로 $33^{100}=(33^{16}{)}^6\cdot 33^4\equiv 1\cdot 33^4$ 이다. $33^4\equiv (-7{)}^4\equiv 9^2\equiv 81\equiv 1(\mathrm{mod}40)$ 이므로 $33^{100}\equiv 1(\mathrm{mod}40)$이다. ↩

4. $\gcd (2009,100)=1$이므로 오일러 정리에 의해 $2009^{40}\equiv 1(\mathrm{mod}100)$이다. $2009^{1002}=(2009^{40}{)}^{25}\cdot 2009^2\equiv 1^{25}\cdot 2009^2\equiv 9^2(\mathrm{mod}100)$이다. 따라서 $2009^{1}002$를 $100$으로 나눈 나머지는 $81$이다. ↩

5. $n$은 $17$의 배수가 아니므로, $\gcd (n,17)=1$이다. 오일러 정리에 의해 $\phi (17)=16$이므로 $n^{16}\equiv 1(\mathrm{mod}17)$이다. $1998\equiv 14(\mathrm{mod}16)\Rightarrow n^{14}\equiv 4(\mathrm{mod}17)$ 즉, 이 문제는 결국 $n^{14}\equiv 4(\mathrm{mod}17)$을 만족하는 최소 자연수 $n$을 찾는 문제이다. $n^{16}\equiv 4n^2\equiv 1(\mathrm{mod}17)$이므로, $n^2\equiv -4(\mathrm{mod}17)$이다. 따라서 구하는 최솟값 $n=8$이다. ↩