오일러 피 함수(φ(n))는 정수론에서 매우 중요한 함수로, 어떤 양의 정수 n에 대해 1부터 n까지의 자연수 중에서 n과 서로소인 수의 개수를 나타냅니다. 이 개념은 RSA 암호체계, 모듈러 연산, 수론의 여러 정리에 폭넓게 사용됩니다. 이번 글에서는 오일러 피 함수와 서로소 개념을 쉽게 이해할 수 있도록 설명합니다.
1. 서로소(coprime)의 개념
두 수 a, b가 있을 때, 그들의 최대공약수(GCD)가 1이면 서로소(coprime)라고 합니다.
예:
- 8과 15: GCD(8,15) = 1 → 서로소
- 6과 9: GCD(6,9) = 3 → 서로소 아님
2. 오일러 피 함수 φ(n)의 정의
오일러 피 함수 φ(n)은 다음을 의미합니다:
$$ \phi(n) = \text{1부터 } n \text{까지의 정수 중에서 } n \text{과 서로소인 수의 개수} $$
예: – φ(1) = 1 (1과 자기 자신) – φ(5) = 4 → {1, 2, 3, 4}는 모두 5와 서로소 – φ(6) = 2 → {1, 5}만 6과 서로소
3. 오일러 피 함수의 계산 공식
n이 소수일 경우: $$ \phi(p) = p – 1 $$
n이 서로소인 소수들의 곱으로 표현될 수 있다면:
$$ \phi(n) = n \left(1 – \frac{1}{p_1}\right)\left(1 – \frac{1}{p_2}\right)\cdots $$
예: n = 12 = \(2^2 \cdot 3\)
$$ \phi(12) = 12\left(1 – \frac{1}{2}\right)\left(1 – \frac{1}{3}\right) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} = 4 $$
→ 12와 서로소인 수: 1, 5, 7, 11
4. 오일러 피 함수의 성질
- φ(p) = p – 1 (p는 소수)
- 만약 a, b가 서로소라면, $$\phi(ab) = \phi(a) \cdot \phi(b)$$
- φ(n)은 항상 n보다 작거나 같다.
5. RSA 암호와의 연관성
RSA 암호화 알고리즘은 큰 소수 두 개 \(p, q\)를 곱해 \(n = pq\)를 만들고, φ(n) = (p−1)(q−1)을 이용해 공개키/개인키를 생성합니다.
이처럼 φ(n)은 정보 보안의 핵심 계산에 사용됩니다.
결론
서로소: 두 수의 최대공약수가 1이면 서로소이며, 오일러 피 함수는 이 개수를 세는 함수입니다.
오일러 피 함수 φ(n): 1부터 n까지의 자연수 중 n과 서로소인 수의 개수로, 정수론과 암호이론에서 매우 중요합니다.
계산 공식: 소인수 분해를 통해 효율적으로 φ(n)을 구할 수 있으며, RSA 알고리즘 등 실생활 암호 기술에 사용됩니다.
이처럼 φ(n)은 수학적 흥미뿐 아니라, 실제 디지털 보안 기술에서도 중심적인 역할을 하는 함수입니다.