오일러 ϕ\phi 함수Permalink

Definition 7.1Permalink

주어진 n1n \ge 1 에 대해 ϕ(n)\phi(n)nn과 서로소이면서 nn 이하인 자연수의 개수이다.

특히, gcd(1,1)=1gcd(1,1)=1 이므로 ϕ(1)=1\phi(1)=1, 소수는 자기 자신으로만 나뉘어지므로 ϕ(p)=p1\phi(p)=p-1 임에 주목한다.

\because 서로소의 정의에 의해 11은 자기 자신과 서로소이다.

ϕ(n)=n1\phi(n)=n-1 인 것은 nn이 소수다와 동치이다.

증명

nn이 합성수라고 할 때, 1<d<n1 < d < n 을 만족하는 진약수 dd가 존재하여 ϕ(n)n2\phi(n) \le n-2 가 되기 때문에 ϕ(n)=n1\phi(n)=n-1 이 되려면 nn이 소수여야만 한다. \square

오일러 ϕ\phi함수와 소인수분해를 이용한 계산법Permalink

Theorem 7.1Permalink

pp가 소수이고 k>0k > 0이면,

ϕ(pk)=pkpk1 \phi(p^k)=p^k-p^{k-1}

증명

gcd(n,pk)=1gcd(n,p^k)=1 일 조건은 pnp \nmid n 이다.

11부터 pkp^k 까지 pp의 배수는 정확히 pk1p^{k-1}개이다.

  p,2p,,pk1ppk1\because ~~ \overbrace{ p,2p,\dots,p^{k-1} \cdot p }^{p^{k-1} \text{개}}

따라서 이 수들을 제외한 개수는

ϕ(pk)=pkpk1 \phi(p^k)=p^k-p^{k-1}

\square

오일러 ϕ\phi함수의 승법성Permalink

LemmaPermalink

주어진 정수 a,b,ca,b,c에 대해 gcd(a,bc)=1gcd(a,bc)=1 일 필요충분조건은 gcd(a,b)=1gcd(a,b)=1 그리고 gcd(a,c)=1gcd(a,c)=1 이다.

증명

gcd(a,bc)=1gcd(a,bc)=1 이라 가정하고, d=gcd(a,b)d=gcd(a,b) 라 놓자.

da,  dbcd \mid a,~~ d \mid bc 이므로 gcd(a,bc)dgcd(a,bc) \ge d 임을 의미하고, gcd(a,bc)=1gcd(a,bc)=1 이므로 d=1d=1 임을 강제한다.

gcd(a,c)=1gcd(a,c)=1 도 동일하게 유도할 수 있다.

역 증명

gcd(a,b)=1,gcd(a,c)=1gcd(a,b)=1, gcd(a,c)=1 일 때, gcd(a,bc)=d1>1gcd(a,bc)=d_1>1 이라 가정하자.

d1d_1이 가지는 소인수 pppa,  pbcp \mid a, ~~ p \mid bc 이므로 pbp \mid b 혹은 pcp \mid c 여야 한다.

이 때, gcd(a,b)gcd(a,b) 혹은 gcd(a,c)gcd(a,c)pp가 되므로 모순이다.

즉, gcd(a,bc)=1gcd(a,bc)=1 이다. \square

Theorem 7.2Permalink

ϕ\phi는 승법 함수이다.

증명

mnm \perp n 일 때, ϕ(mn)=ϕ(m)ϕ(n)\phi(mn)=\phi(m)\phi(n) 임을 보이자.

다음과 같은 수들의 격자식 배열을 고려한다.

12rmm+1m+2m+r2m2m+12m+22m+r3m(n1)m+1(n1)m+2(n1)m+rnm \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 \\ (n-1)m+1 & (n-1)m+2 & \cdots & (n-1)m+r & \cdots & nm \end{matrix}

nnmm열을 갖는다.

유클리드 호제법으로 gcd(qm+r,m)=gcd(r,m)gcd(qm+r,m)=gcd(r,m)이므로 어떤 rr열의 수들이 mm과 서로소일 조건은 gcd(r,m)=1gcd(r,m)=1 이다.

또한 해당 열의 모든 수들은 모두 mm과 서로소이다.

따라서 ϕ(m)\phi(m)개의 열들이 이러한 경우에 해당된다.

gcd(r,m)=1gcd(r,m)=1 인 어떤 rr열을 보자.

r,m+r,2m+r,    ,(n1)m+r r,m+r,2m+r, ~~\dots ~~ ,(n-1)m+r

의 수들은 법 nn에 대해 완전잉여계를 이룬다. 그렇지 않다면

r+amr+bm(modn)  (0a,b<n) r+am \equiv r + bm \pmod n ~~ (0 \le a,b < n)

이 되어 (ab)m0(modn)ab0(modn)(a-b)m \equiv 0 \pmod n \Longrightarrow a-b \equiv 0 \pmod n 이 되어 모순이다.

따라서 ϕ(m)\phi(m)개의 각 열에 있는 nn개의 수 중에 ϕ(n)\phi(n)개가 mnmn과 서로소이므로, nmnm에 서로소인 수의 개수는 ϕ(m)ϕ(n)\phi(m)\phi(n)이다.

즉, ϕ(mn)=ϕ(m)ϕ(n)  \phi(mn)=\phi(m)\phi(n)~~ \square

오일러 ϕ\phi함수의 값을 구하는 법Permalink

이는 PS에서 나오는 문제 중 하나이다.

Theorem 7.3 ⭐️Permalink

정수 n>1n > 1이 소인수분해되어 n=p1k1p2k2prkrn=p_1^{k_1}p_2^{k_2} \cdots p_r^{k_r}이면,

ϕ(n)=(p1k1p1k11)(prkrprkr1) \phi(n)=\Bigl( p_1^{k_1}-p_1^{k_1-1} \Bigr)\cdots \Bigl( p_r^{k_r}-p_r^{k_r-1} \Bigr)

증명 생략

오일러 ϕ\phi함수의 짝수성Permalink

Theorem 7.4Permalink

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

증명

nn22의 거듭제곱이라고 하자.

n=2k (k>1) n=2^k~(k > 1)

Theorem 7.3에 의해 ϕ(n)=2k2k1=(21)2k1\phi(n)=2^k-2^{k-1}=(2-1)\cdot 2^{k-1} 는 짝수이다.

22가 아닌 다른 소인수를 포함한다고 할 때, ϕ(n)=(p1)pk1\phi(n)=(p-1) \cdot p^{k-1} \cdots 처럼 되기때문에, (p1)(p-1) 이 짝수라서 짝수이다.

ϕ\phi는 승법함수라서 ϕ(n)=ϕ(p1k1p2k2prkr)=ϕ(p1k1)ϕ(p2k2)ϕ(prkr)\phi(n)=\phi(p_1^{k_1}p_2^{k_2} \cdots p_r^{k_r})=\phi(p_1^{k_1}) \phi(p_2^{k_2}) \cdots \phi(p_r^{k_r}) 이 되어 결국 ϕ(n)\phi(n)은 짝수이다. \square

소수의 무한성과 오일러 ϕ\phi함수Permalink

이를 이용해 소수의 무한성을 증명해보자.

소수가 유한개 존재한다고 할 때, 그 집합을 {p1,p2,,pr}\{p_1, p_2, \dots, p_r\} 이라 하자.

n=p1p2prn=p_1p_2 \cdots p_r 을 고려하자.

1<k<n1 < k < n 인 모든 kk에 대해 gcd(k,n)>1gcd(k,n) > 1 이다.

kk가 가지는 어떤 소인수는 pip_i에 포함되므로 pin, pikp_i \mid n,~ p_i \mid k 이기 때문에 gcd(n,k)>1gcd(n,k) > 1 이다.

그러면 ϕ(n)=1\phi(n)=1 이 되고 이는 Theorem 7.4에 모순이다.

따라서 소수는 무한하다. \square

Comments