[ 알고리즘 ] 오일러 피 함수(Euler's phi function)

오일러 피(파이) 함수(Euler's phi function)는 1부터 n까지의 정수 중 n과 서로소인 수의 개수를 구하는 함수이고, Ф(n)으로 표현합니다.

 

이때, 서로소는  1 이외에 공약수를 갖지 않는 둘 이상의 양의 정수를 말합니다. 이를테면 7과 13은 서로소입니다.

 

[ 동작 원리 ]

 

1. p가 소수인 경우

 

ϕ(p) = p - 1

 

소수인 경우 약수는 1과 자기 자신밖에 없으므로 자기 자신을 제외한 서로소의 개수는 p - 1입니다.

 

2. 소수 p의 거듭제곱인 경우

 

ϕ(p^k) = p^{k - 1}(p - 1)

 

소수 p의 거듭제곱과 서로소가 아닌 경우는 p의 배수일 경우입니다. p, 2p, 3p... p^{k - 1} * p 즉, p^{k - 1}개가 있습니다. 따라서 ϕ(p^k) 의 개수는 p^{k - 1}(p - 1)입니다.

 

3. a와 b가 서로소일 때

 

ϕ(ab) = ϕ(a)ϕ(b)

 

Ф(ab)는 1부터 ab - 1까지의 수 중에서 ab와 나누어 떨어지는 숫자를 세어보면 a는 b - 1개만큼, b는 a - 1개만큼 있습니다.

 

따라서,

ϕ(ab) = (ab - 1) - (a + b - 2)

= ab - a - b + 1

= (a - 1)(b - 1) 

= ϕ(a)ϕ(b)      

이 됩니다.

 

 

마지막으로 유도한 식들을 바탕으로 임의의 양의 정수 n에 대해 Ф(n)을 구해보겠습니다.

 

$ n = p_{1}^{k_{1}}p_{2}^{k_{2}}\cdot \cdot \cdot p_{n}^{k_{n}} $으로 나타낼 수 있습니다.

 

따라서,

 

$\phi (n) = \phi (p_{1}^{k_{1}})\phi (p_{2}^{k_{2}})\phi (p_{3}^{k_{3}})\cdot \cdot \cdot \phi (p_{n}^{k_{n}})$

             $=p_{1}^{k_{1}}(1 - \frac{1}{p_{1}})p_{2}^{k_{2}}(1 - \frac{1}{p_{2}})p_{3}^{k_{3}}(1 - \frac{1}{p_{3}})\cdot \cdot \cdot p_{n}^{k_{n}}(1 - \frac{1}{p_{n}})$

             $=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\cdot \cdot \cdot p_{n}^{k_{n}} (1 - \frac{1}{p_{1}})(1 - \frac{1}{p_{2}})(1 - \frac{1}{p_{3}})\cdot \cdot \cdot (1 - \frac{1}{p_{n}})$

             $=n(1 - \frac{1}{p_{1}})(1 - \frac{1}{p_{2}})(1 - \frac{1}{p_{3}})\cdot \cdot \cdot (1 - \frac{1}{p_{n}})$

 

이 됩니다.

 

이렇게 $\phi (n)$ 을 1부터 n - 1까지의 모든 숫자에 대해 최대공약수를 구할 필요 없이 깔끔하게 구할 수 있습니다.