정수론 | 오일러의 정리

오일러의 phi 함수

[정의] 자연수 $n\in N$에 대하여 n이하의 자연수 중 $n$과 서로소인 수의 개수를 $\phi(n)$으로 표기한다. 정의에 따라 $\phi(n)$은 하나의 함수이고 $\phi : N \rightarrow N:n \rightarrow \phi(n)$이 성립한다. 이 함수를 오일러의 phi 함수(Euler's phi-function)이라고 부른다.

$\phi : N \rightarrow N:n \rightarrow \phi(n)$ 해석: phi함수의 정의역인 자연수 집합 $N$의 결과값이 자연수 집합 $N$에 속한다는 의미이며 $n \rightarrow \phi(n)$은 자연수 $n$을 대입한 결과가 $\phi(n)$에 대응됨을 말한다.

정리: $p$가 소수이고 양의 정수 $k>0$에 대하여 $\phi(p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p})$이다.

정수 $1,\ 2,\cdots\ ,\ p^k$ 중 $p^k$와 서로소가 아닌 정수는 $p$의 배수 뿐이다. $p$로 묶어서 정리하면 서로소가 아닌 정수들은 $p(1,\ 2,\ 3,\ \cdots,\ p^{k-1})$이 성립하고 그 개수는 $p^{k-1}$이다. phi 함수의 정의에 따라 $\phi(p^k)=p^k-p^{k-1}=p^k(1-\frac{1}{p})$이다.

[증명] 만약 $a\equiv0\pmod{p}$이면 당연히 주어진 조건은 성립한다. $a\nmid p$일 때, 페르마의 작은 정리에 의해 성립함을 알 수 있다.

정리: 정수의 부분 집합 $R_{\phi(m)}$이 다음 두 개의 조건을 만족하면 $m$을 법으로 한 기약 잉여계(reduced residue system modulo m)라 부른다.

1. $a\in R_{\phi(m)} \Rightarrow\ \gcd(a,m)=1$
2. $b\in Z,\ \gcd(b,m)=1 \Rightarrow \exists! a\in R_{\phi(m)}\ s.t\ b\equiv a\ \pmod{m}$

$\exists!$는 유일하게 존재한다는 기호이다.

[증명] 집합 $R_{\phi(m)}$의 정의에 따라 집합 $R_{\phi(m)}$의 원소 개수는 $\phi(m)$개이다. 1번은 $\phi(m)$의 정의에 따라 성립하며 2번은 기약 잉여계의 정의에 따라 성립한다.

m을 법으로 한 기약 잉여계 판별법

정수 부분집합 $S_{\phi(m)}$이 $m$을 법으로 하는 기약 잉여계인지 판별하는 방법은 다음 세 가지 조건을 만족하면 된다.

1. $\forall\ s\in S_{\phi(m)}\ \Rightarrow\ \gcd(s,m)=1$
2. $S_{\phi(m)}$은 $\phi(m)$개의 원소를 갖는다.
3. $s,t \in S_{\phi(m)}$이고 $s\equiv t\ \pmod{m}\ \Rightarrow\ s=t$

정리: 집합 $R_{\phi(m)}$이 $m$을 법으로 하는 기약 잉여계이고 정수 $a$가 $\gcd(a,m)=1$이면 집합 $T_{\phi(m)}= \{ar |r\in R_{\phi(m)} \}$도 $m$을 법으로 하는 기약 잉여계이다.

[증명] 집합 $T_{\phi(m)}$가 위에서 작성한 판별법의 세 가지 조건을 만족하는 지 증명하면 된다.

1. $\gcd(a,m)=1,\ \gcd(r,m)=1,\ \forall\ r\in R_{\phi(m)}$이므로 $\gcd(ar,m)=1,\ \forall\ r\in R_{\phi(m)}$이 되어 조건을 만족한다.
2. 3번 조건을 먼저 증명한다. 임의의 $r_1,\ r_2 \in R_{\phi(m)}$에 대하여 $ar_1\equiv ar_2 \pmod{m}$이라고 하자. $\gcd(a,m)=1$이므로 $r_1 \equiv r_2 \pmod{m}$이다. $R_{\phi(m)}$은 $m$을 법으로 한 기약 잉여계이므로 $r_1=r_2$가 되고 $ar_1=ar_2$가 된다.
3. 2번 조건의 증명은 3번 조건이 사용된다. $R_{\phi(m)}$이 $\phi(m)$개의 원소를 가지며 3번 조건에 따라 $T_{\phi(m)}$도 $\phi(m)$개의 원소를 갖는다.

따라서, 세 조건을 모두 만족하므로 $m$을 법으로 하는 기약 잉여계이다.

정리: $A=\{a_1, a_2 \cdots a_{\phi(m)}\}$, $B=\{b_1,b_2\cdots b_{\phi(m)} \}$가 $m$을 법으로 하는 기약 잉여계라고 하면 $a_1a_2\cdots a_{\phi(m)}\equiv b_1b_2\cdots b_{\phi(m)} \pmod{m}$이다.

[증명] 기약 잉여계의 정의에 따라 임의의 원소 $a_k\in {a_1\cdots a_{\phi(m)}}$에 대해 유일하게 $b_l \in {b_1 \cdots b_{\phi(m)} }$이 존재하여 $a_k\equiv a_l$이 성립한다. 즉, 집합 $A$의 모든 원소에 대해 적절히 순서만 바꾸면 집합 $B$의 원소와 일대일 대응이 됨을 알 수 있다.

정리: $\gcd(m,n)=1$이면 $T_{\phi(m,n)}=\{nr+ms|\ r\in R_{\phi(m)}, s\in S_{\phi(n)}\}$의 원소 개수는 $\phi(m)\phi(n)$이고 $mn$을 법으로 하는 기약 잉여계이다.

[증명] $R_{\phi(m)}$을 $m$을 법으로 하는 기약 잉여계, $S_{\phi(n)}$을 $n$을 법으로 하는 기약 잉여계라고 하자. 임의의 $r\in R_{\phi(m)},\ s\in S_{\phi(n)}$에 대하여 $\gcd(nr+ms,mn)=1$임을 증명하자. $nr+ms \equiv nr \pmod{m}$이고 $\gcd(n,m)=1,\ \gcd(r,m)=1$이므로 $\gcd(nr,m)=1$이다. 그러므로 $\gcd(nr+ms,m)=gcd(nr,m)=1$이다. 동일한 방법으로 $\gcd(nr+ms,n)=\gcd(ms,n)=1$이 되어 $\gcd(nr+ms,mn)=1$이다.

원소의 유일성을 증명하기 위해 임의의 $r_1,r_2\in R_{\phi(m)},\ s_1,s_2\in S_{\phi(n)}$에 대하여 $nr_1+ms_1\equiv nr_2+ms_2 \pmod{mn}$이라 하면 $n(r_1-r_2)\equiv m(s_2-s_1) \Rightarrow n(r_1-r_2)\equiv 0 \pmod{m}$이고 $r_1-r_2\equiv 0 \pmod{m}$이 되어 기약 잉여계의 정의에 따라 $r_1=r_2$이 된다. 같은 방법으로 $s_1=s_2$도 성립한다. 따라서 원소의 개수는 $\phi(m)\phi(n)$이 된다.

마지막으로 기약 잉여계임을 증명하기 위해 어떤 정수 $a$가 $\gcd(a,mn)=1$이면 집합 $T_{\phi(mn)}$의 원소 중 한 개의 원소 $b$에 대해 $a\equiv b \pmod{mn}$임을 증명하자. $\gcd(a,mn)=1$이면 $\gcd(a,m)=\gcd(a,n)=1$이다. $\gcd(m,n)=1$이므로 정수 $x,y\in Z$가 존재하여 디오판토스 방정식 $mx+ny=1$을 만족한다. 그러므로 각 변수 $m,n,x,y$ 모두 각각에 대해 서로소이다.

양변에 $a$를 곱하면 $amx+any=a$이고 $\gcd(a,m)=\gcd(a,n)=1$이므로 $\gcd(ax,n)=\gcd(ay,m)=1$이다. 만약 어떤 $r\in R_{\phi(m)}$, $s\in S_{\phi(n)}$이 존재하여 $ax\equiv s \pmod{n}$, $ay\equiv r \pmod{m}$이라고 하면 합동식의 정의에 따라 $ax=s+kn$, $ay=r+lm$으로 표현할 수 있다. 이를 대입하면 $(s+kn)m+(r+lm)n=a$이다. 정리하면 $nr+ms+mn(k+l)=1$이 되어 $a\equiv nr+ms \pmod{mn}$을 성립한다.

양의 정수 $a$의 $\phi(a)$ 값 구하기

양의 정수 $a>1$을 소인수 분해하여 임의의 소수들의 조합인 $a=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$로 표현할 수 있다고 하자. 이때 각 소수들은 다른 소수들에 대해 서로소이므로 $\phi(a)=\phi(p_1^{k_1})\phi(p_2^{k_2})\cdots\phi(p_r^{k_r})$이고 앞서 정리에 따라 $\phi(a)=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})\cdots(p_r^{k_r}-p_r^{k_r-1})$이고 $p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}(1-\cfrac{1}{p_1})(1-\cfrac{1}{p_2})\cdots(1-\cfrac{1}{p_r})$이다.

오일러의 정리 : Euler's Theorem

정의: $\gcd(a,m)=1$이면 $a^{\phi(m)}\equiv 1 \pmod{m}$이다.

[증명] $R_{\phi(m)}={r_1, r_2\cdots r_{\phi(m)} }$을 $m$을 법으로 한 기약 잉여계라고 하자. $\gcd(a,m)=1$이므로 ${ar_1, ar_2 \cdots ar_{phi(m)} }$도 순서만 바뀌었을 뿐 $m$을 법으로 한 기약 잉여계이다. 즉, $ar_1ar_2\cdots ar_{\phi(m)} = a^{\phi(m)}r_1r_2\cdots r_{\phi(m)}\equiv r_1r_2\cdots r_{\phi(m)} \pmod{m}$ 이고 $\gcd(r_1r_2\cdots r_{\phi(m)},m)=1$이므로 $a^{\phi(m)}\equiv 1 \pmod{m}$이다.

예제: 어떤 양의 정수를 2진법으로 표현하면 마지막 세 자리가 011이고 5진법으로 표현하면 마지막 세 자리가 101이다. 이 수를 10진법으로 표현할 때 마지막 세 자리를 구하여라.

어떤 양의 정수를 $a=n\cdot10^3+b\equiv b \pmod{10^3}$이라 하면 $a=5^2+1=26\pmod{5^3}$이므로 $b=125k+26$으로 표현할 수 있다. 그리고 2진법 조건에 따라 $a\equiv 2+1=3 \pmod{2^3}$이므로 $b\equiv 125k+26\equiv 5k+2 \equiv 3 \pmod{2^3}$에서 $5k\equiv 1 \pmod{2^3}$이다. 즉 $k=5$가 되어 $125\cdot5+26=651$이다.

예제: $n$은 1보다 큰 정수일 때, $n\nmid 2^n-1$임을 증명하여라.

$n|2^n-1$이라 하자. $2^n-1$은 홀수이므로 $n$도 홀수이고 $p|n$인 소수 $p\ (2<p\le n)$가 존재하여 $p|2^n-1$을 만족한다. 그리고 $\gcd(n,p-1)=1$이 성립하여 디오판토스 방정식 $nx+(p-1)y=1$이 성립한다. 문제가 지수와 관련되어 있으므로 2의 지수로 변환하면 $2=2^{nx+(p-1)y}=(2^n)^x(2^{p-1})^y\equiv 1 \pmod{p}$인데 앞서 $p$가 2 이상의 소수라고 가정하였으므로 모순이 발생한다. 따라서 $n \nmid 2^n-1$이다.

예제: $p$는 소수이고 만약 정수 $n$이 존재해서 $p|(4n^2+1)$이면 $p\equiv 1 \pmod{4}$이다.

우변이 홀수이므로 $p$는 2가 아니다. 따라서 홀수인 정수이므로 $p \ne 4k+3$임을 보이면 된다. 증명을 위해 $p=4k+3$이라 가정하자. $x=2n$이라 하면 $p\nmid x$이므로 $x^{p-1}\equiv 1 \pmod{p}$이다. 조건에 따라 $p|4n^2+1$이므로 $x^2=4n^2\equiv -1 \pmod{p}$이다. $x^{p-1}=x^{4k+2}=(x^2)^{2k+1}\equiv(-1)^{2k+1}\equiv-1\pmod{p}$이 되어 모순이 되어 $p\ne 4k+3$이다.

예제: $1989^{2008}$의 마지막 두 자리 수를 구하여라.

$1989^{2008}$의 마지막 두 자리 수는 100으로 나눈 나머지 값이다. $1989^{2008}\equiv89^{2008}\equiv(-11)^{2008}\pmod{100}$이고 $\gcd(-11,100)=1$이므로 오일러의 정리에 따라 $(-11)^{\phi(100)}\equiv 1 \pmod{100}$이다. $\phi(100)=100(1-\cfrac{1}{2})(1-\cfrac{1}{5})=40$이므로 $1989^{2008}=1989^{40\cdot50+8}\equiv(-11)^8\pmod{100}$이다. $(-11)^8\equiv21^4\equiv41^2\equiv81 \pmod{100}$이 되어 마지막 두 자리 수는 81이다.

작성에 도움이 된 자료

• KMO 수학경시 정수론, 장환수학, 임장환 저