07. 오일러의 파이함수(Euler's Totient Function)

● 목적

- 임의의 자연수 n을 선택 했을 때, 1~n사이에 있는 수 중에서 n과 서로소인 수의 개수를 쉽게 구한다. (ex. RSA에서 사용)

● 용어정의

- ф(p): 1~p사이에 있는 수 중에서 p와 서로소인 수의 개수. (p는 양의 자연수)

● 공식

1) p가 소수일 때, ф(p^k)=p^k*(1-1/p)
2) p와 q가 서로 다른 소수 일때, ф(p*q)=ф(p)*ф(q)

2) p와 q가 서로소 일때, ф(p*q)=ф(p)*ф(q)*(d/ф(d)), 단, d=gcd(p,q)

3) m=p1^k1*p2^k2*p3^k3.... 라고 가정 할 때 ф(m)=m*(1-1/p1)*(1-1/p2)....... (단, p1,p2...는 서로 다른 소수)

● 증명 1) [ф(p^k)=p^k*(1-1/p)]

① p가 소수일 때, 1~p의 수 중에서 p와 서로소인 수의 개수는 p-1이다. 즉, ф(p) = p-1

② 1~p^k의 수 중에서 p^k와 서로소가 아닌 수는 소수p의 배수 뿐이다. (ex. 1~3^5의 수 중에서 3^5와 서로소가 아닌 수는 3, 6, 9, 12, 15 이다.)

③ 1~p^k의 수 중에서 p^k와 서로소가 아닌 수는 p, p*2, p*3, p*4... p^k이다.

④ p^k개의 수 중에서 p^k와 서로소가 아닌 수의 개수는 p^(k-1)개이다.

∵ p*1 [1개], p*2 [2개], p*3 [3개], p*4 [4개]... p*p^(k-1) [p^(k-1)개]

⑤ ф(p^k)=p^k-p^(k-1)=p^k*(1-1/p)

∴ ф(p^k)=p^k*(1-1/p)

● 증명 2) [ф(p*q)=ф(p)*ф(q)]

① 1~p*q의 수의 개수는 p*q이다.

② 1~p*q의 수 중에서 p와 서로소가 아닌 수의 개수는 q개 이다.

∵ p*1 [1개], p*2 [2개]. p*q [q개]

③ 1~p*q의 수 중에서 q와 서로소가 아닌 수의 개수는 p개 이다.

∵ q*1 [1개], q*2 [2개]. q*p [p개]

④ 1~p*q의 수 중에서 p와 q가 공통으로 갖게되는 공배수는 p*q으로 1개이다.

∵ p*q [1개]

⑤ 전체 수 에서 서로소가 아닌 수를 뺀다면, p*q-(p+q-1)=(p-1)(q-1)

⑥ p가 소수일 때, ф(p)=p-1 이었다는 것을 상기시켜보자.

⑦ ф(p*q)=(p-1)(q-1)=ф(p)ф(q)

∴ ф(p*q)=ф(p)*ф(q), (단 p와 q는 소수?????????????????????????????????????, 원래는 p와q는 서로소 여야만 한다. 하지만 p가 소수라는 가정을 하지 않으면 ф(p)=p-1 라는 가정을 사용할 수 없다. )

● 증명 3) [ф(m)=m*(1-1/p1)*(1-1/p2)....... ]

● 예제

① 36보다 작은 수 중에서 36과 서로소인 수의 개수 구하라.??????????????????

ф(36)

=ф(2^2*3^2)

=ф(2^2)*ф(3^2)

=2^2(1-1/2)*3^2(1-1/3)

=12

② ф(x)=12 를 만족하는 모든 수를 구하라.??????????????????????????????????

ф(x)=1*12

=(2-1)*(13-1)

=ф(2)*ф(13)

=ф(26)

ф(x)=2*6

=(3-1)*(7-1)

=ф(3)*ф(7)

=ф(21)

ф(x)=3*4

=(4-1)*(5-1)

=ф(4)*ф(5)

=ф(20)

ф(x)=2*2*3

=(3-1)*(3-1)*(4-1)

=ф(3)*ф(3)*ф(4)

=ф(36)

x=20, 21, 26, 36