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