최종 업데이트: 2026-07-13

정의

오일러 파이 함수 $\varphi(n)$은 $1$부터 $n$까지의 정수 중 몇 개가 $n$과 서로소인지—즉 $n$과 $1$ 외에 공약수가 없는지—를 셉니다. 두 정수의 최대공약수가 $1$일 때 두 수는 서로소입니다.

예를 들어 $\varphi(9) = 6$입니다. $1, 2, \dots, 9$ 중 $1, 2, 4, 5, 7, 8$은 $9$와 서로소이지만 $3, 6, 9$는 그렇지 않습니다.

이 함수는 1763년에 이를 도입한 레온하르트 오일러의 이름을 따랐습니다. $\phi(n)$으로도 쓰며 파이 함수라고 부릅니다.

곱 공식

$n$ 이하의 모든 정수를 일일이 확인할 필요는 없습니다. $n$을 서로 다른 소인수로 분해하고 나면 파이 함수 값이 곧바로 나옵니다.

$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$

곱은 $n$을 나누는 서로 다른 소수에 대해 이루어지며, 지수는 나타나지 않습니다. 각 소수 $p$는 전체의 $1/p$에 해당하는 수($p$의 배수)를 제거하고, 소수들이 서로 독립적으로 작용하므로 이 비율들이 곱해집니다.

예제 — n = 36. 소인수분해는 $36 = 2^2 \cdot 3^2$이므로 서로 다른 소수는 $2$와 $3$입니다.

$\varphi(36) = 36\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12$

$36$과 서로소인 열두 개의 정수는 $1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35$입니다.

소수와 소수의 거듭제곱

두 가지 기본 경우가 공식을 이해하기 쉽게 해 줍니다.

• 소수 $p$: $1$부터 $p - 1$까지의 모든 정수가 $p$와 서로소이므로 $\varphi(p) = p - 1$입니다. 예를 들어 $\varphi(7) = 6$.
• 소수의 거듭제곱 $p^k$: $p^k$과 서로소가 아닌 정수는 $p$의 배수뿐이며 그 개수는 $p^{k-1}$입니다. 따라서

$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$

그러므로 $\varphi(8) = \varphi(2^3) = 2^2(2 - 1) = 4$, $\varphi(27) = \varphi(3^3) = 3^2(3 - 1) = 18$입니다.

곱셈성

파이 함수는 곱셈적입니다. $m$과 $n$이 서로소이기만 하면

$\varphi(mn) = \varphi(m)\,\varphi(n)$

이 성립합니다. 곱 공식이 작동하는 이유가 바로 이것입니다—$n$을 소수 거듭제곱의 곱으로 쓰고, 각 항에 $\varphi(p^k) = p^{k-1}(p-1)$을 적용한 뒤 곱하면 됩니다. 예를 들어 $36 = 4 \cdot 9$이고 $\gcd(4, 9) = 1$이므로 $\varphi(36) = \varphi(4)\,\varphi(9) = 2 \cdot 6 = 12$입니다.

서로소 조건에 유의하세요. $m$과 $n$이 공약수를 가지면 $\varphi(mn) = \varphi(m)\varphi(n)$이 성립하지 않을 수 있습니다. 예를 들어 $\varphi(2 \cdot 2) = \varphi(4) = 2$이며 $\varphi(2)\varphi(2) = 1$이 아닙니다.

오일러 정리

파이 함수는 모듈러 거듭제곱을 지배합니다. 오일러 정리는 $\gcd(a, n) = 1$이면

$a^{\varphi(n)} \equiv 1 \pmod{n}$

이 성립한다고 말합니다. 이는 페르마의 소정리(소수 $p$에 대한 $a^{p-1} \equiv 1 \pmod p$)를 일반화한 것으로, 페르마의 소정리는 $\varphi(p) = p - 1$인 $n = p$의 특수한 경우입니다.

예제. $a = 3$, $n = 10$을 택합니다. 여기서 $\varphi(10) = 4$이므로 $3^4 = 81 \equiv 1 \pmod{10}$이고, 실제로 $81$의 일의 자리는 $1$입니다. 이 정리를 이용하면 계산 전에 거대한 지수를 $\varphi(n)$으로 나눈 나머지로 줄일 수 있습니다.

RSA에의 응용

RSA 공개키 암호는 파이 함수 위에 직접 세워져 있습니다. 두 개의 큰 소수로부터 법 $n = p \cdot q$를 만들면

$\varphi(n) = (p - 1)(q - 1)$

이 됩니다. 공개 지수 $e$와 비밀 지수 $d$는 $e \cdot d \equiv 1 \pmod{\varphi(n)}$을 만족하도록 선택됩니다. 그러면 오일러 정리가 복호화가 암호화를 되돌린다는 것을 보장합니다: $(m^e)^d \equiv m \pmod n$.

안전성은 하나의 간극에 있습니다. 누구나 $n$을 공개할 수 있지만 $\varphi(n) = (p-1)(q-1)$을 계산하려면 $p$와 $q$를 알아야 합니다. $n$만으로 이를 복원하는 것은 큰 반소수를 소인수분해하는 일이며, 충분히 큰 소수에 대해서는 계산적으로 실행 불가능하다고 여겨집니다. 실제로 $\varphi(n)$을 아는 것은 $n$을 소인수분해하는 것과 동등합니다.

예제

$n$	소인수분해	곱 형태	$\varphi(n)$
$10$	$2 \cdot 5$	$10\,(1 - \tfrac12)(1 - \tfrac15)$	$4$
$12$	$2^2 \cdot 3$	$12\,(1 - \tfrac12)(1 - \tfrac13)$	$4$
$36$	$2^2 \cdot 3^2$	$36\,(1 - \tfrac12)(1 - \tfrac13)$	$12$
$100$	$2^2 \cdot 5^2$	$100\,(1 - \tfrac12)(1 - \tfrac15)$	$40$
$101$	$101$ (소수)	$101\,(1 - \tfrac{1}{101})$	$100$

특수한 경우

• $n = 1$: 관례상 $\varphi(1) = 1$입니다. 범위 안의 유일한 정수 $1$은 자기 자신과 서로소입니다.
• $n$이 소수: $\varphi(n) = n - 1$로, 그 크기에서 가능한 최댓값입니다—소수는 서로소인 나머지가 가장 많습니다.
• $n$이 짝수: 인수 $(1 - \tfrac12)$이 정수의 최소 절반을 제거하므로 $\varphi(n) \le n/2$입니다.
• 약수에 대한 합: $n$의 모든 약수의 파이 함수 값을 더하면 $n$ 자신이 됩니다: $\sum_{d \mid n} \varphi(d) = n$. $n = 12$의 경우: $\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12$.

빠른 참고

개념	공식
정의	$\varphi(n) = \#\{\, k : 1 \le k \le n,\ \gcd(k, n) = 1 \,\}$
곱 공식	$\varphi(n) = n \prod_{p \mid n} (1 - 1/p)$
소수	$\varphi(p) = p - 1$
소수의 거듭제곱	$\varphi(p^k) = p^{k-1}(p - 1)$
곱셈성	$\gcd(m, n) = 1$이면 $\varphi(mn) = \varphi(m)\varphi(n)$
오일러 정리	$\gcd(a, n) = 1$이면 $a^{\varphi(n)} \equiv 1 \pmod n$
약수의 합	$\sum_{d \mid n} \varphi(d) = n$

자주 묻는 질문 (FAQ)

오일러 파이 함수란 무엇인가요?

오일러 파이 함수 φ(n)은 n 이하의 양의 정수 중 n과 서로소인 것—즉 n과 1 외에 공약수가 없는 것—의 개수를 셉니다. 예를 들어 φ(9) = 6인데, 1, 2, 4, 5, 7, 8은 각각 9와 서로소이지만 3, 6, 9는 그렇지 않기 때문입니다. 관례상 φ(1) = 1입니다.

φ(n)은 어떻게 계산하나요?

n을 서로 다른 소수 p₁, p₂, …, pₖ로 분해한 뒤, 그 소수들에 대해 φ(n) = n · ∏(1 − 1/p)를 적용합니다. n = 36 = 2² · 3²이면 φ(36) = 36 · (1 − 1/2) · (1 − 1/3) = 36 · 1/2 · 2/3 = 12입니다. 지수가 아니라 서로 다른 소수만이 영향을 줍니다.

소수의 파이 함수 값은 얼마인가요?

소수 p에 대해 1부터 p − 1까지의 모든 정수가 p와 서로소이므로 φ(p) = p − 1입니다. 소수의 거듭제곱 pᵏ에 대해서는 공식이 φ(pᵏ) = pᵏ − pᵏ⁻¹ = pᵏ⁻¹(p − 1)을 줍니다. 예를 들어 φ(7) = 6, φ(8) = φ(2³) = 8 − 4 = 4입니다.

RSA와 오일러 정리에서 파이 함수가 왜 중요한가요?

오일러 정리는 gcd(a, n) = 1이면 a^φ(n) ≡ 1 (mod n)이 성립한다는 것으로, 페르마의 소정리를 일반화합니다. RSA 암호는 여기에 기반합니다. 두 소수의 곱 n = p·q에 대해 φ(n) = (p − 1)(q − 1)이며, 공개 지수와 비밀 지수는 e·d ≡ 1 (mod φ(n))을 만족하도록 선택됩니다. φ(n)을 아는 것은 n을 소인수분해하는 것과 동등하며, 이것이 RSA의 안전성을 뒷받침합니다.