오일러 피 함수(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)을 알면 모든 양의 정수에 대해서 함수를 풀 수 있다는 뜻이다. 그 맥락을 알고 다시 생각해보면 좀 더 와 닿는 풀이가 될 것 같다.