오일러 피 함수 (Euler's Totient Function)

정의

오일러 피 함수 φ(n) 는 1 이상 n 이하의 자연수 중 n 과 서로소인 수의 개수. 1763년 레온하르트 오일러가 도입. φ(1) = 1, 소수 p 에 대해 φ(p) = p - 1.

φ(n) = n · Π_{p|n} (1 - 1/p)
     = n · Π_{p|n} (p - 1) / p

문제 상황과 동기

n 이하의 자연수 중 n 과 서로소인 수를 세시오 (n ≤ 10^12).

• naive (1..n 순회, gcd): O(n log n). n=10^12 면 영원.
• 소인수분해 후 오일러 곱 공식: O(√n). n=10^12 에서 10^6 단계.
• 체 (sieve) 로 전처리 + φ 배열: O(N log log N). N 개 전부 필요할 때 효율.

핵심 통찰: φ 는 곱셈적 함수 (multiplicative function). gcd(m, n) = 1 이면 φ(mn) = φ(m)·φ(n). 소인수분해 결과만 알면 O(√n) 에 계산 가능.

시각화

핵심 아이디어

오일러 곱 공식

n 이 소인수분해: n = p_1^{e_1} · p_2^{e_2} · ... · p_k^{e_k}

φ(n) = n · (1 - 1/p_1) · (1 - 1/p_2) · ... · (1 - 1/p_k)
     = n · Π (p_i - 1) / p_i

소수 p 의 거듭제곱

φ(p^k) = p^k - p^(k-1) = p^(k-1) · (p - 1)

p^k 와 서로소가 아닌 수는 p 의 배수 (p^(k-1) 개) 뿐이므로 전체에서 뺀다.

곱셈성 증명 스케치

gcd(m, n) = 1. CRT 에 의해 Z_mn ≅ Z_m × Z_n. (a mod mn) 이 서로소일 필요충분조건은 (a mod m) 과 (a mod n) 각각 서로소. 따라서 φ(mn) = φ(m)·φ(n).

알고리즘

euler_phi(n):
    result = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            while n % i == 0:
                n /= i
            result -= result / i
        i += 1 (또는 i += 1, 2, 2..)
    if n > 1:          # 남은 소인수
        result -= result / n
    return result

구현

// O(√n) 오일러 피 함수
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
ll euler_phi(ll n) {
  ll result = n;
  for (ll p = 2; p * p <= n; p++) {
      if (n % p == 0) {
          while (n % p == 0) n /= p;
          result -= result / p;
      }
  }
  if (n > 1) result -= result / n;
  return result;
}
​
int main() {
  ll n; cin >> n;
  cout << "phi(" << n << ") = " << euler_phi(n) << "\n";
  return 0;
}

# O(√n) 오일러 피 함수
import sys
input = sys.stdin.readline
​
def euler_phi(n: int) -> int:
  result = n
  p = 2
  while p * p <= n:
      if n % p == 0:
          while n % p == 0:
              n //= p
          result -= result // p
      p += 1 if p == 2 else 2  # 2 이후 홀수
  if n > 1:
      result -= result // n
  return result
​
n = int(input())
print(f"phi({n}) = {euler_phi(n)}")

// O(√n) 오일러 피 함수
import java.util.*;
import java.io.*;
public class Main {
  static long eulerPhi(long n) {
      long result = n;
      for (long p = 2; p * p <= n; p++) {
          if (n % p == 0) {
              while (n % p == 0) n /= p;
              result -= result / p;
          }
      }
      if (n > 1) result -= result / n;
      return result;
  }
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      long n = Long.parseLong(br.readLine());
      System.out.println("phi(" + n + ") = " + eulerPhi(n));
  }
}

36

phi(36) = 12

체 (sieve) 로 1..N 전부 구하기

O(N log log N) 으로 1..N 모든 φ(n) 을 한 번에 계산:

vector<ll> phi(N + 1);
iota(phi.begin(), phi.end(), 0);
for (int i = 2; i <= N; i++)
    if (phi[i] == i)            // i 는 소수
        for (int j = i; j <= N; j += i)
            phi[j] -= phi[j] / i;

복잡도

변형 / 활용

함정

1. n = 1

φ(1) = 1. 관습적으로 1과 1은 서로소로 간주.

2. 나누기 순서

result -= result / p 에서 result 가 먼저 p 로 나누어떨어짐 (정수 연산). 정확함.

3. 큰 n 소인수분해

n = 10^12 이면 √n = 10^6. 루프 10^6 회는 PS 에서 OK. √n 까지만 반복 후 남은 n > 1 처리 필수.

4. 곱셈적 함수 착각

gcd(m, n) ≠ 1 이면 φ(mn) = φ(m)·φ(n) 이 아님. φ(2·2) = φ(4) = 2 ≠ φ(2)·φ(2) = 1·1 = 1.

BOJ 연습 문제

참고

• 모듈러 역원
• 유클리드 호제법
• 중국인의 나머지 정리
• 에라토스테네스의 체