8. 오일러-피 함수, 오일러 정리

8. 오일러 피-함수, 오일러 정리

$n$보다 크지 않은 자연수 중에서 $n$과 서로소인 자연수의 갯수를 $\phi(n)$이라 하고, 이 함수 $\phi$를 오일러 피-함수(Euler phi-function)라고 한다. 예를들어 $\phi(1)=1,\,\phi(2)=1,\,\phi(3)=1,\,\phi(4)=2$이고, 또한 $n>1$일 때, $n$이 소수일 필요충분조건은 $\phi(n)=n-1$이다.

소수 $p$에 대하여 $\phi(p^{k})=p^{k}-p^{k-1}$이다.

증명: $1$과 $p^{k}$사이의 자연수 $n$ 중에서 $p^{k}$와 서로소가 아닐 필요충분조건은 $p|n$이고, 이 조건을 만족하는 $p$는 $\{p,\,2p,\,\cdots,\,(p^{k-1})p\}$($p^{n-1}$개)이다. 그러므로 $\phi(p^{k})=p^{k}-p^{k-1}$이다.

$\text{gcd}(k,\,mn)=1$일 필요충분조건은 $\text{gcd}(k,\,m)=1$이고 $\text{gcd}(k,\,n)=1$이다.

증명: 생략

오일러 피-함수 $\phi$는 승법적이다.

증명: $\phi(1)=1$이므로 $m,\,n>1\,(\text{gcd}(m,\,n)=1)$이라 하고 $1$부터 $mn$까지의 정수를 다음과 같이 배열하자. $$\begin{matrix}1&2&\cdots&r&\cdots&m\\m+1&m+2&\cdots&m+r&\cdots&2m\\2m+1&2m+2&\cdots&2m+r&\cdots&3m\\ \vdots&\vdots&\ddots&\vdots&\ddots&\vdots\\(n-1)m+1&(n-1)m+2&\cdots&(n-1)m+r&\cdots&nm\end{matrix}$$

이때 $\text{gcd}(qm+r,\,m)=\text{gcd}(r,\,m)$이 성립한다.

$d|qm+r,\,d|m$이면, $d|\{(qm+r)-qm\}=r$이므로, $d|r$이고 $d\leq\text{gcd}(r,\,m)$이므로 따라서 $\text{gcd}(qm+r,\,m)\leq\text{gcd}(r,\,m)$이다.

$d|m,\,d|r$이므로 $d|qm+r$이고 $d\leq\text{gcd}(qm+r,\,r)$이므로 따라서 $\text{gcd}(m,\,r)\leq\text{gcd}(qm+r,\,r)$이다. 그러므로 $\text{gcd}(qm+r,\,m)=\text{gcd}(r,\,m)$이 성립한다.

이 식은 $m$과 서로소인 열이 $\phi(m)$개 존재함을 뜻한다.

그 다음으로 $r$번째 열의 성분은 어느 두개도 법 $n$으로 합동이 아니다.

$0\leq k<j\leq n-1$에 대하여 $km+r\equiv jm+r\,(\text{mod}\,n)$이라 하자. 그러면 $km\equiv jm\,(\text{mod}\,n)$이고, $\text{gcd}(m,\,n)=1$이므로 $k\equiv j\,(\text{mod}\,n)$이고 $k=j$이어야 하는데 $k<j$이므로 모순이다.

따라서 $r$번째 열의 성분은 어떤 순서로 $0,\,1,\,\cdots,\,n-1$과 합동이고, $\{0,\,1,\,\cdots,\,n-1\}$중 $n$과 서로소인 것은 $\phi(n)$개가 존재한다. 따라서 $$\{r,\,m+r,\,\cdots,\,(n-1)m+r\}$$ 에서 $n$과 서로소인 것이 $\phi(n)$개 존재하고 $n$과 $m$에 모두 서로소인 성분은 $\phi(m)\phi(n)$개 있고 $\phi(mn)=\phi(m)\phi(n)$이다.

$n>1$의 소인수분해가 $n=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}$이면, $$\phi(n)=n\left(1-\frac{1}{p_{1}}\right)\cdots\left(1-\frac{1}{p_{r}}\right)$$ 이다.

증명: $\phi$는 승법적이므로 $$\begin{align*}\phi(n)&=\phi(p_{1}^{k_{1}})\cdots\phi(p_{r}^{k_{r}})\\&=(p_{1}^{k_{1}}-p_{1}^{k_{1}-1})\cdots(p_{r}^{k_{r}}-p_{r}^{k_{r}-1})\\&=p_{1}^{k_{1}}\cdots p_{r}^{k_{r}}\left(1-\frac{1}{p_{1}}\right)\cdots\left(1-\frac{1}{p_{r}}\right)\\&=n\left(1-\frac{1}{p_{1}}\right)\cdots\left(1-\frac{1}{p_{r}}\right)\end{align*}$$ 이다.

$360=2^{3}\cdot3^{2}\cdot5$이므로 $$\phi(360)=360\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)\left(1-\frac{1}{5}\right)=96$$ 이다.

$n>2$이면, $\phi(n)$은 짝수이다.

증명: $n=2^{k}$이면, $$\phi(n)=\phi(2^{k})=2^{k}-2^{k-1}=2^{k}\left(1-\frac{1}{2}\right)=2^{k-1}$$ 이므로 $\phi(n)$은 짝수이다.

$n\neq2^{k}$이면, 산술의 기본정리에 의해 홀수 소수 $p$가 존재해서 $n=p^{k}m\,(\text{gcd}(p,\,m)=1)$이다. $$\phi(n)=\phi(p^{k})\phi(m)=p^{k-1}(p-1)\phi(m)$$ 이고 $p-1$은 짝수이므로 따라서 $\phi(n)$은 짝수이다.

소수의 개수는 무한개이다.

증명: 소수가 다음과 같이 유한개라 하자. $$p_{1},\,\cdots,\,p_{n}$$ $n=p_{1}\cdots p_{n}$이라 하면 $1<a\leq n$인 $a$에 대하여 소수 $p$가 존재해서 $p|a$이고, 이때 $p$는 $p_{1},\,\cdots,\,p_{n}$ 중 하나이다. 그러면 $\text{gcd}(a,\,n)\geq p$이므로 $\phi(n)=1$이 되는데 이것은 $n\geq2$이므로 $\phi(n)$이 짝수가 되어야 한다는 사실에 모순이다.

$n>1$, $\text{gcd}(a,\,n)=1$이라 하자. $a_{1},\,a_{2},\,\cdots,\,a_{\phi(n)}\in\mathbb{N}$이 $n$보다 작고 $n$과 서로소이면,  $aa_{1},\,aa_{2},\,\cdots,\,aa_{\phi(n)}$은 어떤 순서로 $a_{1},\,a_{2},\,\cdots,\,a_{\phi(n)}$과 법 $n$으로 합동이다.

증명: $1\leq i,\,j\leq\phi(n)$에 대하여 $aa_{i}\equiv aa_{j}\,(\text{mod}\,n)$이라 하자. $\text{gcd}(a,\,n)=1$이므로 $a_{i}\equiv a_{j}\,(\text{mod}\,n)$이고 $a_{i}=a_{j}$이어야 하므로 $i=j$이어야 한다. 그러므로 $\{aa_{1},\,\cdots,\,aa_{\phi(n)}\}$은 어느 두개로 법 $n$으로 합동이 아니다.

$aa_{i}$에 대하여 $b\in\mathbb{Z} (0\leq b\leq n-1)$가 존재해서 $aa_{i}\equiv b\,(\text{mod}\,n)$이고, $\text{gcd}(b,\,n)=\text{gcd}(aa_{i},\,n)=1$이므로 $b$는 $a_{1},\,\cdots,\,a_{\phi(n)}$중 하나이다. 이것은 $aa_{1},\,\cdots,\,aa_{\phi(n)}$과 $a_{1},\,\cdots,\,a_{\phi(n)}$은 법 $n$에 대해 어떤 순서로 합동임을 뜻한다.

오일러 정리(Euler's theorem)

$n\geq1$이고 $\text{gcd}(a,\,n)=1$이면, $a^{\phi(n)}\equiv1\,(\text{mod}\,n)$이다.

증명: $a_{1},\,\cdots,\,a_{\phi(n)}\in\mathbb{N}$을 $n$보다 작고 $n$과 서로소라고 하자. $\text{gcd}(a,\,n)=1$이므로, 앞의 정리에 의해 $aa_{1},\,\cdots,\,aa_{\phi(n)}$은 $a_{1},\,\cdots,\,a_{\phi(n)}$과 어떤 순서로 법 $n$으로 합동이다. $a_{1}',\,\cdots,\,a_{\phi(n)}'$을 $a_{1},\,\cdots,\,a_{\phi(n)}$의 재배열이라고 하면 $$\begin{align*}aa_{1}&\equiv a_{1}'\,(\text{mod}\,n)\\&\vdots\\aa_{\phi(n)}&\equiv a_{\phi(n)}'\,(\text{mod}\,n)\end{align*}$$ 이므로 $$(aa_{1})\cdots(aa_{\phi(n)})\equiv a_{1}\cdots a_{\phi(n)}\,(\text{mod}\,n)$$ 이고 따라서 $a^{\phi(n)}\equiv1\,(\text{mod}\,n)$이다.

$p$가 소수이면 $\phi(p)=p-1$이므로, 오일러 정리는 페르마 정리의 일반화이다.

$3^{256}$의 마지막 두자리수를 구하자. 이 문제는 $3^{256}\equiv r\,(\text{mod}\,100)$인 $r$을 구하는 문제와 같다.

$\text{gcd}(3,\,10)=1$이고 $\displaystyle\phi(100)=100\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)=40$이므로 오일러 정리에 의해 $3^{40}\equiv1\,(\text{mod}\,100)$이다. 그러면 $$3^{256}=3^{6\cdot40+16}\equiv(3^{40})^{6}\cdot3^{16}\equiv3^{16}\,(\text{mod}\,100)$$ 이고 $$3^{16}\equiv(3^{4})^{4}\equiv81^{4}\equiv(-19)^{4}\equiv61^{2}\equiv21\,(\text{mod}\,100)$$ 이므로 따라서 $r=21$이고 $3^{256}$의 마지막 두자리수는 $21$이다.

$n>1$이라 하자. $n$보다 작고 $n$과 서로소인 양의 정수의 합은 $\displaystyle\frac{1}{2}n\phi(n)$이다.

증명: $a_{1},\,\cdots,\,a_{\phi(n)}\in\mathbb{N}$을 $n$보다 작고 $n$과 서로소라고 하자. $\text{gcd}(a,\,n)=1$일 필요충분조건이 $\text{gcd}(n-a,\,n)=1$이므로 $n-a_{1},\,\cdots,\,n-a_{\phi(n)}$은 어떤 순서로 $a_{1},\,\cdots,\,a_{\phi(n)}$과 법 $n$으로 합동이다. 그러면 $$(n-a_{1})+\cdots+(n-a_{\phi(n)})\equiv a_{1}+\cdots+a_{\phi(n)}\,(\text{mod}\,n)$$ 이고 $$n\phi(n)-\sum_{k=1}^{\phi(n)}{a_{k}}\equiv\sum_{k=1}^{\phi(n)}{a_{k}}\,(\text{mod}\,n)$$ 이므로 $\displaystyle\sum_{k=1}^{\phi(n)}{a_{k}}=\frac{1}{2}n\phi(n)$이다.

참고자료:

Elementary Number Theory 7th edition, Burton, McGraw-Hill