오일러 피 함수란?
오일러 피 함수(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과 서로소입니다.
자주 묻는 질문
\(\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)\)가 성립합니다. 서로 다른 소수에 대한 곱 공식이 성립하는 이유가 바로 이것입니다.
