오일러 피 함수란?
오일러 피 함수(Euler's totient function)는 \(\varphi(n)\)으로 표기하며, 1부터 n까지의 양의 정수 중에서 n과 1 이외의 공약수를 갖지 않는 수, 즉 n과 서로소인 정수가 몇 개인지를 세는 함수입니다. 예를 들어 1, 2, 4, 5, 7, 8이 모두 9와 서로소이므로 \(\varphi(9) = 6\)입니다. 이 함수는 정수론의 기초 개념이면서 암호학 전반에 등장하는데, 특히 RSA 알고리즘에서 키 생성에 쓰이는 모듈러 역원을 결정하는 핵심 역할을 합니다.
계산기 사용법
양의 정수 n을 입력하고 계산 버튼을 누르기만 하면 됩니다. 이 도구는 n을 서로 다른 소인수로 분해한 뒤 곱셈 공식을 적용해 \(\varphi(n)\)을 즉시 구하고, 찾아낸 서로 다른 소수 목록까지 함께 보여줍니다. 작은 수는 물론 10억까지의 아주 큰 수도 문제없이 처리합니다.
공식 풀이
피 함수를 효율적으로 구하는 방법은 다음의 곱셈 공식입니다.
$$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$
여기서 \(p\)는 n을 나누는 모든 서로 다른 소수를 의미합니다.
소인수의 지수(중복도)는 필요 없고, 서로 다른 소수만 알면 됩니다. 각 항 \(\left(1 - \frac{1}{p}\right)\)는 해당 소수로 나누어떨어지는 수의 비율을 덜어내는 역할을 합니다.
예제로 풀어보기
n = 36을 생각해 봅시다. 36의 소인수분해는 \(2^2 \times 3^2\)이므로 서로 다른 소수는 2와 3입니다. 그러면:
$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}$$
따라서 1부터 36까지의 정수 중 정확히 12개가 36과 서로소입니다.
더 많은 풀이 예시
예시 1: 소수, φ(13)
13은 소수이므로 소인수는 13 자신뿐입니다:
\(\varphi(13) = 13\left(1-\frac{1}{13}\right) = 13 \cdot \frac{12}{13} = \)12. 이는 소수 공식 \(\varphi(p) = p-1\)과 일치합니다.
예시 2: 소수의 거듭제곱, φ(32)
인수분해: \(32 = 2^5\). 서로 다른 소인수는 2뿐입니다.
\(\varphi(32) = 32\left(1-\frac{1}{2}\right) = 32 \cdot \frac{1}{2} = \)16.
소수 거듭제곱 형태로 표현하면: \(\varphi(p^k) = p^k - p^{k-1}\), 따라서 \(\varphi(2^5) = 2^5 - 2^4 = 32 - 16 = 16\). 이 값은 1부터 31까지의 홀수들과 정확히 같습니다.
예시 3: 세 개 이상의 서로 다른 소수, φ(210)
인수분해: \(210 = 2 \cdot 3 \cdot 5 \cdot 7\).
- \(210\)에서 시작합니다.
- \(1-\frac{1}{2} = \frac{1}{2}\)을 곱합니다: \(210 \cdot \frac{1}{2} = 105\).
- \(1-\frac{1}{3} = \frac{2}{3}\)을 곱합니다: \(105 \cdot \frac{2}{3} = 70\).
- \(1-\frac{1}{5} = \frac{4}{5}\)을 곱합니다: \(70 \cdot \frac{4}{5} = 56\).
- \(1-\frac{1}{7} = \frac{6}{7}\)을 곱합니다: \(56 \cdot \frac{6}{7} = 48\).
따라서 \(\varphi(210) = \)48. 곱셈 규칙에서는 각 서로 다른 소수를 한 번씩만 사용한다는 점에 유의하세요. 예를 들어 \(60 = 2^2 \cdot 3 \cdot 5\)이면 \(60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16\)입니다.
φ(n)의 해석과 활용
- 소수성과의 관계: \(n \ge 2\)일 때, \(\varphi(n) = n-1\)은 \(n\)이 소수인 경우에만 성립합니다. \(n\)보다 작은 모든 수는 \(n\)과 서로소입니다. \(n\)이 합성수이면 그보다 작은 수 중 적어도 하나가 공통 인수를 가지므로 \(\varphi(n) < n-1\)입니다.
- 단위군: \(\varphi(n)\)은 법 \(n\)에 대한 단위군의 원소 개수, 즉 법 \(n\)에서 곱셈에 대한 역원을 갖는 잉여류의 개수입니다. \(n = 15\)일 때 이들은 1, 2, 4, 7, 8, 11, 13, 14이며, 원소는 8개입니다.
- 오일러 정리: \(\gcd(a, n) = 1\)이면 \(a^{\varphi(n)} \equiv 1 \pmod{n}\)입니다. 예: \(a = 2\), \(n = 15\), \(\varphi(15) = \)8, 그리고 \(2^8 = 256 = 17 \cdot 15 + 1 \equiv 1 \pmod{15}\). 페르마의 소정리는 \(n = p\)(소수)인 특수한 경우입니다.
- RSA: \(n = pq\)(서로 다른 소수 \(p\), \(q\))이면 \(\varphi(n) = (p-1)(q-1)\)입니다. \(n = 15 = 3 \cdot 5\)일 때 \(\varphi(15) = 2 \cdot 4 = 8\)입니다. 공개 지수 \(e\)는 \(\varphi(n)\)과 서로소여야 하며, 비밀 지수 \(d\)는 \(ed \equiv 1 \pmod{\varphi(n)}\)을 만족합니다. 실제 RSA는 수백 자리의 소수를 사용합니다. \(n\)을 인수분해할 수 있는 사람은 \(\varphi(n)\)을 계산할 수 있으므로, 보안은 인수분해가 어렵다는 사실에 기반합니다.
- 비율은 서로 다른 소수에만 의존합니다: \(\dfrac{\varphi(n)}{n} = \prod_{p \mid n}\left(1-\frac{1}{p}\right)\)입니다. 지수는 영향을 주지 않습니다. 예를 들어 6과 12는 모두 소인수 집합이 {2, 3}이므로, \(\varphi(6)/6 = 2/6 = 1/3\)이고 \(\varphi(12)/12 = 4/12 = 1/3\)입니다.
자주 묻는 질문
\(\varphi(1)\)은 얼마인가요? 관례상 \(\varphi(1) = 1\)입니다. 1은 자기 자신과 서로소로 보기 때문입니다.
소수 p의 φ 값은? 임의의 소수 p에 대해 \(\varphi(p) = p - 1\)입니다. 1부터 \(p-1\)까지의 모든 정수가 p와 서로소이기 때문이죠.
피 함수는 곱셈적(multiplicative)인가요? 네. \(\gcd(a, b) = 1\)이면 \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\)가 성립합니다. 서로 다른 소수에 대한 곱 공식이 성립하는 이유가 바로 이것입니다.