오일러 피 함수(Euler's phi function)

Euler's phi function

오일러 피(파이) 함수 $\phi (n)$ 란 1과 n까지의 정수 중 n과 서로소인 개수를 뜻한다. 거부감 없이 정의는 매우 쉽다.

 

int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a%b);
}
int getEulerPhiFunc(int n){
    int cnt = 0;
    for(int i = 1; i < n; i++){
        if(gcd(n, i) == 1) cnt++;
    }
    return cnt;
}

 

대충 예외 생각 안 하고 구현하면 위와 같이 구하면 된다. 이 방법은 $ \phi (n) $ 의 성질을 하나도 안 따져보고 구했으니, 더 좋은 방법을 위해 성질을 알아보자.

 

일단 가장 간단하게 유추할 수 있는 것이 있다.
$$ \phi(p) = p - 1 (단,\ p는\ 소수) $$

소수의 정의를 생각하면 소수 정의 그 자체다.

 

이번엔 $ p ^{m} $ 를 보자.
$ p ^{m} $ 을 소인수 분해하면 $ p $ 로만 이루어져 있고, 따라서 $ p $의 배수인 $ \alpha p $ 에 대해서 $ gcd(p ^{m}, \alpha p) != 1 $ 이 된다.

그리고 임의의 다른 수 $ \beta $ 에 대해 $ gcd(p ^{m}, \beta) != 1 $ 는 절대 성립하지 않는다.

 

$ \alpha $ 의 개수는 $ \frac{p ^{m}}{p} = p ^{m-1} $ 이다.

 

이 말을 반대로 해석하면 $ \phi (p ^{m}) $ 을 재해석할 수 있다.

$$ \begin{align} \phi(p ^{m} ) & = p ^{m} - p ^{m-1} \\
& = p ^{m} (1 - \frac{1}{p} ) \end{align} $$

 

이렇게 소수의 특성을 가지고 수식 하나를 완성했다. 다른 식을 또 유도해보자.

 

서로소 관계인 $ \alpha $ 와 $ \beta $ 가 있을 때 $ \phi(\alpha \beta) $ 를 생각해보자.

1부터 $ \alpha \beta - 1 $ 까지의 수 중에서 $ \alpha \beta $ 와 나누어 떨어지는 숫자를 세어보면 $ \alpha $ 가 $ \beta -1 $ 개만큼, $ \beta $ 가 $ \alpha -1 $ 개만큼 있다.

 

식으로 다시 계산하면
$$ \frac{\alpha \beta}{\alpha} + \frac{\alpha \beta}{\beta} - 2 = \alpha + \beta - 2$$

만큼 존재한다.

 

그러면 역시 이번에도 반대로 생각해서 $ \phi(\alpha \beta) $ 를 다시 정리해보면 아래와 같다.
$$ \begin{align} \phi(\alpha \beta) & = (\alpha \beta - 1) - (\alpha + \beta - 2) \\
& = \alpha \beta - \alpha - \beta + 1 \\
& = (\alpha - 1)(\beta - 1) \\
& = \phi({\alpha})\ \phi({\beta}) \end{align} $$

 

유도한 두 개의 식을 가지고 임의의 양의 정수 $ n = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} p_{3}^{\alpha_{3}} \cdots p_{n}^{\alpha_{n}} $ 을 풀어보자.
$$ \begin{align} \phi(n) & = \phi(p_{1}^{\alpha_{1}})\ \phi(p_{2}^{\alpha_{2}})\ \phi(p_{3}^{\alpha_{3}})\ \cdots \phi(p_{n}^{\alpha_{n}}) \\
& = p_{1}^{\alpha_{1}}(1 - \frac{1}{p_{1}}) p_{2}^{\alpha_{2}}(1 - \frac{1}{p_{2}}) p_{3}^{\alpha_{3}}(1 - \frac{1}{p_{3}}) \cdots p_{n}^{\alpha_{n}}(1 - \frac{1}{p_{n}}) \\
& = p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} p_{3}^{\alpha_{3}} \cdots p_{n}^{\alpha_{n}} (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) (1 - \frac{1}{p_{3}}) \cdots (1 - \frac{1}{p_{n}}) \\
& = n (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) (1 - \frac{1}{p_{3}}) \cdots (1 - \frac{1}{p_{n}}) \end{align} $$

 

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

 

정리

모든 양의 정수는 결국 소인수 분해를 통해 소수의 곱으로 바꿀 수 있다.
다시 말하면 특정 함수에 대해서 소수의 멱수를 표현하는 방법(1)과 서로소를 표현하는 방법(2)을 알면 모든 양의 정수에 대해서 함수를 풀 수 있다는 뜻이다. 그 맥락을 알고 다시 생각해보면 좀 더 와 닿는 풀이가 될 것 같다.