콘텐츠로 이동

오일러 피 함수

피 함수(phi-function) $\phi (n)$라고도 불리는 오일러 피 함수는 1 이상 $n$ 이하의 정수 중 $n$과 서로소인 정수의 개수를 셉니다. 두 수의 최대공약수가 $1$이면 두 수는 서로소입니다($1$은 모든 수와 서로소로 간주합니다).

처음 몇 개의 양의 정수에 대한 $\phi(n)$의 값은 다음과 같습니다:

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \\\\ \hline \phi(n) & 1 & 1 & 2 & 2 & 4 & 2 & 6 & 4 & 6 & 4 & 10 & 4 & 12 & 6 & 8 & 8 & 16 & 6 & 18 & 8 & 12 \\\\ \hline \end{array}$$

성질

오일러 피 함수의 다음 성질들만 알면 어떤 수에 대해서든 함숫값을 계산할 수 있습니다:

  • $p$가 소수이면 모든 $1 \le q < p$에 대해 $\gcd(p, q) = 1$입니다. 따라서 다음이 성립합니다:
$$\phi (p) = p - 1.$$
  • $p$가 소수이고 $k \ge 1$이면, $1$과 $p^k$ 사이에 $p$로 나누어떨어지는 수는 정확히 $p^k / p$개입니다. 이로부터 다음을 얻습니다:
$$\phi(p^k) = p^k - p^{k-1}.$$

  • $a$와 $b$가 서로소이면 다음이 성립합니다:

    $$\phi(a b) = \phi(a) \cdot \phi(b).$$

    이 관계는 바로 알아보기 쉽지 않습니다. 이는 중국인의 나머지 정리로부터 유도됩니다. 중국인의 나머지 정리는 각 $0 \le x < a$와 각 $0 \le y < b$에 대해 $z \equiv x \pmod{a}$이고 $z \equiv y \pmod{b}$인 $0 \le z < a b$가 유일하게 존재함을 보장합니다. $z$가 $a b$와 서로소인 것은 $x$가 $a$와 서로소이고 $y$가 $b$와 서로소인 것과 동치임을 어렵지 않게 보일 수 있습니다. 따라서 $a b$와 서로소인 정수의 개수는 $a$와 $b$ 각각에 대한 개수의 곱과 같습니다.

  • 일반적으로, 서로소가 아닌 $a$와 $b$에 대해 다음 방정식은

    $$\phi(ab) = \phi(a) \cdot \phi(b) \cdot \dfrac{d}{\phi(d)}$$

    $d = \gcd(a, b)$일 때 성립합니다.

따라서 처음 세 가지 성질을 이용하면 $n$의 소인수분해($n$을 소인수들의 곱으로 분해하는 것)를 통해 $\phi(n)$을 계산할 수 있습니다. $n = {p_1}^{a_1} \cdot {p_2}^{a_2} \cdots {p_k}^{a_k}$이고 $p_i$가 $n$의 소인수라면,

$$\begin{align} \phi (n) &= \phi ({p_1}^{a_1}) \cdot \phi ({p_2}^{a_2}) \cdots \phi ({p_k}^{a_k}) \\\\ &= \left({p_1}^{a_1} - {p_1}^{a_1 - 1}\right) \cdot \left({p_2}^{a_2} - {p_2}^{a_2 - 1}\right) \cdots \left({p_k}^{a_k} - {p_k}^{a_k - 1}\right) \\\\ &= p_1^{a_1} \cdot \left(1 - \frac{1}{p_1}\right) \cdot p_2^{a_2} \cdot \left(1 - \frac{1}{p_2}\right) \cdots p_k^{a_k} \cdot \left(1 - \frac{1}{p_k}\right) \\\\ &= n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right) \end{align}$$

구현

다음은 소인수분해를 이용하여 $O(\sqrt{n})$에 동작하는 구현입니다:

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

$O(n \log\log{n})$에 $1$부터 $n$까지의 오일러 피 함수 구하기

$1$부터 $n$까지의 모든 수에 대한 오일러 피 함수 값이 필요하다면, $n$개의 수를 모두 인수분해하는 것은 효율적이지 않습니다. 에라토스테네스의 체와 같은 아이디어를 사용할 수 있습니다. 이 방법도 여전히 위에서 보인 성질에 기반하지만, 각 수마다 각 소인수에 대해 임시 결과를 갱신하는 대신, 모든 소수를 찾은 뒤 각 소수에 대해 그 소수로 나누어떨어지는 모든 수의 임시 결과를 갱신합니다.

이 방법은 에라토스테네스의 체와 사실상 동일하므로 복잡도도 $O(n \log \log n)$으로 같습니다.

void phi_1_to_n(int n) {
    vector<int> phi(n + 1);
    for (int i = 0; i <= n; i++)
        phi[i] = i;

    for (int i = 2; i <= n; i++) {
        if (phi[i] == i) {
            for (int j = i; j <= n; j += i)
                phi[j] -= phi[j] / i;
        }
    }
}

구간 체를 이용하여 $L$부터 $R$까지의 오일러 피 함수 값 구하기

$L$부터 $R$까지의 모든 수에 대한 오일러 피 함수 값이 필요하다면, 구간 체 방식을 사용할 수 있습니다.

이 알고리즘은 먼저 선형 체를 사용하여 $\sqrt{R}$ 이하의 모든 소수를 $O(\sqrt{R})$의 시간과 공간으로 미리 계산합니다. 그런 다음 구간 $[L, R]$의 각 수에 대해 이 소수들을 순회하며 소인수분해 기반의 $\phi$ 공식을 적용합니다. 각 수에서 아직 소인수분해되지 않은 부분을 추적하기 위해 나머지 배열을 유지합니다. 작은 소수들을 모두 처리한 뒤에도 나머지가 여전히 1보다 크다면, 이는 $\sqrt{R}$보다 큰 소인수가 있다는 뜻이며, 이 소인수는 마지막 단계에서 처리합니다. 구간 계산의 전체 복잡도는 $O((R - L + 1) \log \log R) + \sqrt{R}$입니다.

const long long MAX_RANGE = 1e6 + 6;
vector<long long> primes;
long long phi[MAX_RANGE], rem[MAX_RANGE];

vector<int> linear_sieve(int n) { 
    vector<bool> composite(n + 1, 0);
    vector<int> prime;

    // 0 and 1 are not composite (nor prime)
    composite[0] = composite[1] = 1;

    for(int i = 2; i <= n; i++) {
        if(!composite[i]) prime.push_back(i);
        for(int j = 0; j < prime.size() && i * prime[j] <= n; j++) {
            composite[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
    return prime;
}

// To get the value of phi(x) for L <= x <= R, use phi[x - L].
void segmented_phi(long long L, long long R) { 
    for(long long i = L; i <= R; i++) {
        rem[i - L] = i;
        phi[i - L] = i;
    }

    for(long long i : primes) {
        for(long long j = max(i * i, (L + i - 1) / i * i); j <= R; j += i) {
            phi[j - L] -= phi[j - L] / i;
            while(rem[j - L] % i == 0) rem[j - L] /= i;
        }
    }

    for(long long i = 0; i < R - L + 1; i++) {
        if(rem[i] > 1) phi[i] -= phi[i] / rem[i];
    }
}

약수 합 성질

이 흥미로운 성질은 Gauss가 밝혔습니다:

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

여기서 합은 $n$의 모든 양의 약수 $d$에 대해 취합니다.

예를 들어 10의 약수는 1, 2, 5, 10입니다. 따라서 $\phi{(1)} + \phi{(2)} + \phi{(5)} + \phi{(10)} = 1 + 1 + 4 + 4 = 10$입니다.

약수 합 성질을 이용하여 1부터 $n$까지의 오일러 피 함수 값 구하기

약수 합 성질을 이용해서도 1부터 $n$까지의 모든 수에 대한 오일러 피 함수 값을 계산할 수 있습니다. 이 구현은 앞서 살펴본 에라토스테네스의 체 기반 구현보다 조금 더 간단하지만, 복잡도는 약간 더 나쁩니다: $O(n \log n)$

void phi_1_to_n(int n) {
    vector<int> phi(n + 1);
    phi[0] = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
        phi[i] = i - 1;

    for (int i = 2; i <= n; i++)
        for (int j = 2 * i; j <= n; j += i)
              phi[j] -= phi[i];
}

오일러 정리에서의 활용

오일러 피 함수의 가장 유명하고 중요한 성질은 오일러 정리로 표현됩니다:

$$a^{\phi(m)} \equiv 1 \pmod m \quad \text{if } a \text{ and } m \text{ are relatively prime.}$$

$m$이 소수인 특수한 경우, 오일러 정리는 페르마의 소정리가 됩니다:

$$a^{m - 1} \equiv 1 \pmod m$$

오일러 정리와 오일러 피 함수는 실제 응용에서 꽤 자주 등장하며, 예를 들어 둘 다 모듈러 곱셈 역원을 계산하는 데 사용됩니다.

이로부터 바로 다음과 같은 동치 관계도 얻습니다:

$$a^n \equiv a^{n \bmod \phi(m)} \pmod m$$

이를 이용하면 매우 큰 $n$에 대해서도 $x^n \bmod m$을 계산할 수 있습니다. $n$을 모듈로 아래에서 계산할 수 있게 해 주므로, 특히 $n$이 다른 계산의 결과인 경우에 유용합니다.

군론

$\phi(n)$은 법 n에 대한 곱셈군의 위수입니다. 이 곱셈군 $(\mathbb Z / n\mathbb Z)^\times$는 가역원(곱셈 역원을 갖는 원소)들로 이루어진 군입니다. 곱셈 역원을 갖는 원소는 정확히 $n$과 서로소인 원소들입니다.

법 $n$에 대한 원소 $a$의 곱셈 위수는 $\operatorname{ord}_n(a)$로 표기하며, $a^k \equiv 1 \pmod n$을 만족하는 가장 작은 $k>0$입니다. $\operatorname{ord}_n(a)$는 $a$가 생성하는 부분군의 크기이므로, 라그랑주 정리에 의해 임의의 $a$의 곱셈 위수는 반드시 $\phi(n)$을 나누어야 합니다. $a$의 곱셈 위수가 가능한 최댓값인 $\phi(n)$이라면, $a$는 원시근이며 정의에 따라 이 군은 순환군입니다.

일반화

마지막 동치 관계에는 덜 알려진 형태가 있는데, 이를 이용하면 $x$와 $m$이 서로소가 아닌 경우에도 $x^n \bmod m$을 효율적으로 계산할 수 있습니다. 임의의 $x, m$과 $n \geq \log_2 m$에 대해 다음이 성립합니다:

$$x^{n}\equiv x^{\phi(m)+[n \bmod \phi(m)]} \mod m$$

증명:

$p_1, \dots, p_t$를 $x$와 $m$의 공통 소수 약수라 하고, $k_i$를 $m$에서의 그 지수라 합시다. 이들을 이용해 $a = p_1^{k_1} \dots p_t^{k_t}$로 정의하면, $\frac{m}{a}$는 $x$와 서로소가 됩니다. 그리고 $k$를 $a$가 $x^k$를 나누는 가장 작은 수라 합시다. $n \ge k$라고 가정하면, 다음과 같이 쓸 수 있습니다:

$$\begin{align}x^n \bmod m &= \frac{x^k}{a}ax^{n-k}\bmod m \\ &= \frac{x^k}{a}\left(ax^{n-k}\bmod m\right) \bmod m \\ &= \frac{x^k}{a}\left(ax^{n-k}\bmod a \frac{m}{a}\right) \bmod m \\ &=\frac{x^k}{a} a \left(x^{n-k} \bmod \frac{m}{a}\right)\bmod m \\ &= x^k\left(x^{n-k} \bmod \frac{m}{a}\right)\bmod m \end{align}$$

세 번째 줄과 네 번째 줄이 동치인 것은 $ab \bmod ac = a(b \bmod c)$라는 사실에서 따라 나옵니다. 실제로 $r < c$인 $b = cd + r$이면, $ab = acd + ar$이고 $ar < ac$입니다.

$x$와 $\frac{m}{a}$는 서로소이므로, 오일러 정리를 적용하여 다음과 같은 효율적인($k$가 매우 작기 때문입니다. 실제로 $k \le \log_2 m$입니다) 공식을 얻을 수 있습니다:

$$x^n \bmod m = x^k\left(x^{n-k \bmod \phi(\frac{m}{a})} \bmod \frac{m}{a}\right)\bmod m.$$

이 공식은 적용하기 어렵지만, $x^n \bmod m$의 동작을 분석하는 데 사용할 수 있습니다. 거듭제곱의 수열 $(x^1 \bmod m, x^2 \bmod m, x^3 \bmod m, \dots)$은 처음 $k$개(또는 그 이하)의 원소 이후에 길이가 $\phi\left(\frac{m}{a}\right)$인 사이클에 들어감을 알 수 있습니다. $\phi\left(\frac{m}{a}\right)$는 $\phi(m)$을 나누므로($a$와 $\frac{m}{a}$가 서로소이므로 $\phi(a) \cdot \phi\left(\frac{m}{a}\right) = \phi(m)$이 성립합니다), 주기의 길이가 $\phi(m)$이라고도 말할 수 있습니다. 그리고 $\phi(m) \ge \log_2 m \ge k$이므로, 원하던 훨씬 더 간단한 공식을 결론으로 얻을 수 있습니다:

$$ x^n \equiv x^{\phi(m)} x^{(n - \phi(m)) \bmod \phi(m)} \bmod m \equiv x^{\phi(m)+[n \bmod \phi(m)]} \mod m.$$

연습 문제