오일러 파이 함수(Euler's totient function), 또는 약칭하여 파이 함수라고 불리는 이 함수는 정수론에서 매우 중요한 역할을 합니다. 간단히 말해, 오일러 파이 함수 $\phi(n)$은 1부터 n까지의 자연수 중에서 n과 서로소인 자연수의 개수를 나타냅니다. 여기서 '서로소'란 두 개 이상의 정수의 최대공약수(GCD)가 1인 경우를 의미합니다. 예를 들어, 10과 서로소인 수는 1, 3, 7, 9로 총 4개입니다. 따라서 $\phi(10) = 4$입니다.
오일러 파이 함수의 계산 방법
오일러 파이 함수를 계산하는 방법은 크게 두 가지로 나눌 수 있습니다. 첫 번째는 정의에 따라 직접 개수를 세는 방법이고, 두 번째는 n의 소인수분해를 이용하는 공식적인 방법입니다. 작은 수의 경우에는 직접 세는 것이 가능하지만, 수가 커질수록 비효율적이므로 공식적인 방법을 사용하는 것이 일반적입니다.
1. 직접 개수 세기 (작은 수의 경우)
예를 들어 $\phi(12)$를 계산해 봅시다. 1부터 12까지의 수 중에서 12와 서로소인 수를 찾아야 합니다. 12의 약수는 1, 2, 3, 4, 6, 12입니다. 12와 서로소가 되려면 해당 수가 2나 3을 공약수로 가지지 않아야 합니다. 1부터 12까지의 수 중에서 2의 배수나 3의 배수가 아닌 수는 1, 5, 7, 11입니다. 따라서 $\phi(12) = 4$입니다.
2. 소인수분해를 이용한 공식
n이 다음과 같이 소인수분해된다고 가정해 봅시다. n = $p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$
여기서 $p_1, p_2, \cdots, p_k$는 서로 다른 소수이고, $a_1, a_2, \cdots, a_k$는 양의 정수입니다. 이때 오일러 파이 함수는 다음과 같이 계산할 수 있습니다.
$\phi(n) = n \times (1 - \frac{1}{p_1}) \times (1 - \frac{1}{p_2}) \times \cdots \times (1 - \frac{1}{p_k})$
이 공식은 다음과 같이 변형하여 사용할 수도 있습니다.
$\phi(n) = n \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \times \cdots \times \frac{p_k - 1}{p_k}$
또는
$\phi(n) = p_1^{a_1-1}(p_1-1) p_2^{a_2-1}(p_2-1) \cdots p_k^{a_k-1}(p_k-1)$
예시: $\phi(12)$ 계산
12를 소인수분해하면 $12 = 2^2 \times 3^1$입니다. 여기서 서로 다른 소인수는 2와 3입니다.
공식을 이용하면: $\phi(12) = 12 \times (1 - \frac{1}{2}) \times (1 - \frac{1}{3})$ $\phi(12) = 12 \times \frac{1}{2} \times \frac{2}{3}$ $\phi(12) = 12 \times \frac{2}{6} = 12 \times \frac{1}{3} = 4$
이 결과는 앞에서 직접 개수를 세어 얻은 결과와 일치합니다.
오일러 파이 함수의 중요한 성질
오일러 파이 함수는 몇 가지 흥미로운 성질을 가지고 있습니다. 첫째, p가 소수일 때, $\phi(p) = p-1$입니다. 이는 소수 p 자신을 제외한 1부터 p-1까지의 모든 수가 p와 서로소이기 때문입니다. 둘째, p가 소수이고 k가 양의 정수일 때, $\phi(p^k) = p^k - p^{k-1} = p^k(1 - \frac{1}{p})$입니다. 셋째, 서로소인 두 자연수 m과 n에 대해 $\phi(mn) = \phi(m)\phi(n)$이라는 곱셈적 성질을 가집니다.
오일러 파이 함수의 활용
오일러 파이 함수는 암호학, 특히 RSA 암호 시스템에서 중요한 역할을 합니다. 또한 정수론의 다양한 문제, 예를 들어 페르마의 소정리나 오일러의 정리 등을 증명하는 데 기초가 됩니다. 이 함수를 이해하는 것은 현대 수학과 컴퓨터 과학의 여러 분야를 탐구하는 데 필수적입니다.