[Algorithm] 오일러의 피함수 ( Euler's Phi-Function )

정의

phi(N)

- N보다 작고 N과 서로소들인 수의 갯수.

 

ex)

phi(10) = 10보다 작고 10과 서로소인 수

= {1, 3, 7, 9}

 

* pi(N)과는 다름. pi(N)은 N보다 작은 소수의 갯수!!

* 곱셈역을 배웠다면...Zn*의 크기와 phi(N)은 같다 

피함수의 성질

1. phi(1) = 0

2. phi(P) = p-1

3. m,n이 서로소이면 phi(m * n) = phi(m) * phi(n) 

4. phi(p^e) = p^e - p^(e-1) (p가 소수이면, e가 양의 정수이면)

 

m,n이 서로소이면 phi(m * n) = phi(m) * phi(n)  증명하기

원래 성질은 서로소이면 다 되는데 여기서 증명은 간단하게 m, n 모두 소수일 때만 한다. 

 

phi(m * n)은 m*n보다 작고 m*n과 서로소여야 한다. 따라서 1, 2, ..., m*n-1 에서 m, 2*m, ....(n-1)*m을 빼고, n, 2*n, ..., (m-1)*n도 빼준다. 

그러면 m*n -1 - (n-1) - (m-1) 이여서 (m-1)(n-1)개 이다. phi(m)은 m-1이니까 성립한다.