54. Euler's Totient Function

오일러 토션트 함수(Euler's Totient Function)는 모듈러 곱셈 역원이 존재하는 수의 개수를 구하는 함수이며, 기호로는 $\phi$를 사용한다. 즉, 임의의 양의 정수 $n$에 대해 $\phi(n)$은 $n$ 이하의 양의 정수 중 $n$과 서로소인 것의 개수와 같다. 오일러 피(파이) 함수(Euler's Phi Function)라고도 한다.

 

오일러 토션트 함수의 결과값은 다음과 같은 두 가지 공식을 이용하여 구할 수 있다.

• $p$가 소수이고 $n = p^k$일 때, $\phi(n)=p^{k-1}(p-1)$이다.
• $n$과 $m$이 서로소일 때, $\phi(nm) = \phi(n) \phi(m)$이다.

$n$의 소인수를 중복 없이 나열한 결과가 $p_1, p_2, \ldots, p_k$일 때, $\phi(n)$을 다음과 같이 구할 수도 있다.

$$\phi(n)=n\times\frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times\ldots\times\frac{p_k-1}{p_k}$$

이 식을 오일러 곱 공식(Euler Product Formula)이라고 한다. 이를 이용하여 오일러 토션트 함수를 구현하면 다음과 같다.

int phi(int n)
{
    int s = n;
    for(int i = 2; i * i <= n; i++)
    {
        if(n % i == 0)
        {
            while(n % i == 0)n /= i;
            s = s / i * (i - 1);
        }
    }
    if(n > 1)s = s / n * (n - 1);
    return s;
}

오일러 토션트 함수는 다음과 같은 두 가지 성질을 갖는다.

$$\sum_{d|n}\phi(d)=n$$

$$\gcd(a,n)=1\to a^{\phi(n)}\equiv 1\pmod{n}$$

두 번째 성질은 모듈러 곱셈 역원을 구할 때 유용하게 사용할 수 있다. 그밖에 정다각형의 작도 가능 여부를 오일러 토션트 함수로 판별할 수 있다. $\phi(n)$이 $2$의 거듭제곱일 경우 눈금 없는 자와 컴퍼스만으로 정$n$각형을 작도할 수 있다.

 

[연습문제]

 

BOJ 11689. GCD(n, k) = 1 (Gold I)

$n$을 소인수분해한 다음 오일러 곱 공식을 이용하여 오일러 토션트 함수의 결과값을 구한다.

 

→ solved.ac tag: euler_phi