← 목록으로 돌아가기
1. 오일러 파이 함수의 정의
정의: 오일러 파이 함수 (Euler's Phi Function 또는 Totient Function)
양의 정수 $n$에 대하여, $\phi(n)$은 1부터 $n$까지의 정수 중에서 $n$과 서로소인 수의 개수입니다.
$$\phi(n) = |\{k : 1 \leq k \leq n, \gcd(k, n) = 1\}|$$
오일러 파이 함수는 레온하르트 오일러(Leonhard Euler)가 도입한 함수로,
정수론에서 가장 중요한 함수 중 하나입니다.
이 함수는 $\phi(n)$ 또는 $\varphi(n)$으로 표기하며,
토션트 함수(totient function)라고도 불립니다.
1.1 작은 값들의 예시
| $n$ |
$n$과 서로소인 수 |
$\phi(n)$ |
| 1 |
1 |
1 |
| 2 |
1 |
1 |
| 3 |
1, 2 |
2 |
| 4 |
1, 3 |
2 |
| 5 |
1, 2, 3, 4 |
4 |
| 6 |
1, 5 |
2 |
| 7 |
1, 2, 3, 4, 5, 6 |
6 |
| 8 |
1, 3, 5, 7 |
4 |
| 9 |
1, 2, 4, 5, 7, 8 |
6 |
| 10 |
1, 3, 7, 9 |
4 |
2. 오일러 파이 함수의 기본 성질
성질 1: 소수에 대한 값
$p$가 소수이면
$$\phi(p) = p - 1$$
이유: 1부터 $p-1$까지 모든 수가 $p$와 서로소
성질 2: 소수의 거듭제곱
$p$가 소수이고 $k \geq 1$이면
$$\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1) = p^k\left(1 - \frac{1}{p}\right)$$
이유: $p^k$ 이하에서 $p$의 배수는 $p, 2p, 3p, \ldots, p^{k-1}p$로 $p^{k-1}$개
예제 1
$\phi(8) = \phi(2^3)$를 계산하시오.
풀이:
$$\phi(2^3) = 2^3 - 2^2 = 8 - 4 = 4$$
또는
$$\phi(2^3) = 2^2(2-1) = 4 \times 1 = 4$$
검증: 1, 3, 5, 7이 8과 서로소 → 4개
3. 곱셈적 성질
정리: 오일러 파이 함수는 곱셈적 함수
$\gcd(m, n) = 1$이면
$$\phi(mn) = \phi(m) \cdot \phi(n)$$
3.1 증명 개요
중국인의 나머지 정리를 사용합니다.
$\gcd(m, n) = 1$일 때, $\gcd(k, mn) = 1$인 $k$ (단, $1 \leq k \leq mn$)는
다음과 같은 연립 합동식의 해와 일대일 대응됩니다:
$$\begin{cases}
k \equiv a \pmod{m}, & \gcd(a, m) = 1 \\
k \equiv b \pmod{n}, & \gcd(b, n) = 1
\end{cases}$$
이러한 $(a, b)$ 쌍은 $\phi(m) \times \phi(n)$개이므로,
$\phi(mn) = \phi(m) \cdot \phi(n)$입니다.
4. 일반 공식
정리: 오일러 파이 함수의 일반 공식
$n$의 소인수분해가 $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$이면
$$\phi(n) = n \prod_{p|n} \left(1 - \frac{1}{p}\right) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right)$$
또는
$$\phi(n) = p_1^{a_1-1}(p_1-1) \cdot p_2^{a_2-1}(p_2-1) \cdots p_k^{a_k-1}(p_k-1)$$
예제 2
$\phi(36)$을 계산하시오.
풀이:
$36 = 2^2 \times 3^2$
방법 1: 곱셈적 성질 이용
$$\phi(36) = \phi(4) \times \phi(9)$$
- $\phi(4) = \phi(2^2) = 2^1(2-1) = 2$
- $\phi(9) = \phi(3^2) = 3^1(3-1) = 6$
- $\phi(36) = 2 \times 6 = 12$
방법 2: 일반 공식 이용
$$\phi(36) = 36 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 12$$
검증: 36과 서로소인 수는 1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 → 12개
5. 중요한 항등식
항등식 1: 약수 합 공식
모든 양의 정수 $n$에 대하여
$$\sum_{d|n} \phi(d) = n$$
여기서 합은 $n$의 모든 양의 약수 $d$에 대한 것입니다.
예제 3: 항등식 검증
$n = 12$일 때 항등식을 검증하시오.
풀이:
12의 약수: 1, 2, 3, 4, 6, 12
- $\phi(1) = 1$
- $\phi(2) = 1$
- $\phi(3) = 2$
- $\phi(4) = 2$
- $\phi(6) = 2$
- $\phi(12) = 4$
$$\sum_{d|12} \phi(d) = 1 + 1 + 2 + 2 + 2 + 4 = 12$$ ✓
6. 연습문제
문제 1
다음 값들을 계산하시오:
- $\phi(100)$
- $\phi(72)$
- $\phi(1000)$
풀이 1
1) $\phi(100)$
$100 = 2^2 \times 5^2$
$$\phi(100) = 100 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 100 \times \frac{1}{2} \times \frac{4}{5} = 40$$
2) $\phi(72)$
$72 = 2^3 \times 3^2$
$$\phi(72) = 72 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right) = 72 \times \frac{1}{2} \times \frac{2}{3} = 24$$
3) $\phi(1000)$
$1000 = 2^3 \times 5^3$
$$\phi(1000) = 1000 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 1000 \times \frac{1}{2} \times \frac{4}{5} = 400$$
문제 2
$\phi(n) = 12$를 만족하는 모든 양의 정수 $n$을 구하시오.
풀이 2
$\phi(n) = 12$가 되려면 다음 경우들을 고려해야 합니다:
경우 1: $n = 1, 2$인 경우
- $\phi(1) = 1 \neq 12$
- $\phi(2) = 1 \neq 12$
경우 2: $n = p$ (소수)인 경우
- $\phi(p) = p - 1 = 12$ → $p = 13$ ✓
경우 3: $n = 2p$ (p는 홀수 소수)인 경우
- $\phi(2p) = \phi(2) \times \phi(p) = 1 \times (p-1) = 12$ → $p = 13$
- $n = 2 \times 13 = 26$ ✓
경우 4: $n = p^2$ (소수의 제곱)인 경우
- $\phi(p^2) = p(p-1) = 12$
- $p = 3$일 때: $3 \times 2 = 6 \neq 12$
- $p = 4$는 소수가 아님
경우 5: $n = 2p^2$인 경우
- $\phi(2p^2) = \phi(2) \times \phi(p^2) = 1 \times p(p-1) = 12$
- 해 없음 (위에서 확인)
경우 6: $n = 3^a \times 2^b$ 형태
- $n = 3 \times 2^2 = 12$: $\phi(12) = \phi(3)\phi(4) = 2 \times 2 = 4 \neq 12$
- $n = 3^2 \times 2 = 18$: $\phi(18) = \phi(9)\phi(2) = 6 \times 1 = 6 \neq 12$
- $n = 3^2 \times 2^2 = 36$: $\phi(36) = \phi(9)\phi(4) = 6 \times 2 = 12$ ✓
경우 7: $n = 7 \times 2^b$ 형태
- $\phi(7 \times 2) = 6 \times 1 = 6 \neq 12$
- $\phi(7 \times 4) = 6 \times 2 = 12$ → $n = 28$ ✓
경우 8: $n = 13 \times 2^b$ 형태 (이미 확인함)
체계적으로 확인한 결과:
답: $n = 13, 21, 26, 28, 36, 42$
검증:
- $\phi(13) = 12$ ✓
- $\phi(21) = \phi(3 \times 7) = 2 \times 6 = 12$ ✓
- $\phi(26) = \phi(2 \times 13) = 1 \times 12 = 12$ ✓
- $\phi(28) = \phi(4 \times 7) = 2 \times 6 = 12$ ✓
- $\phi(36) = 12$ ✓ (위에서 계산)
- $\phi(42) = \phi(2 \times 3 \times 7) = 1 \times 2 \times 6 = 12$ ✓
7. 응용
7.1 오일러 정리
오일러 파이 함수는 오일러 정리의 핵심입니다:
$$\gcd(a, n) = 1 \Rightarrow a^{\phi(n)} \equiv 1 \pmod{n}$$
7.2 RSA 암호화
오일러 파이 함수는 RSA 암호 시스템의 핵심입니다.
두 큰 소수 $p, q$에 대해 $n = pq$일 때,
$\phi(n) = (p-1)(q-1)$을 사용하여 암호화와 복호화 키를 생성합니다.
8. 요약
- $\phi(n)$: $n$과 서로소인 $1 \leq k \leq n$의 개수
- $\phi(p) = p - 1$ (소수)
- $\phi(p^k) = p^{k-1}(p-1)$ (소수의 거듭제곱)
- $\phi(mn) = \phi(m)\phi(n)$ (곱셈적 함수, $\gcd(m,n)=1$일 때)
- 일반 공식: $\phi(n) = n \prod_{p|n} \left(1 - \frac{1}{p}\right)$
- 약수 합: $\sum_{d|n} \phi(d) = n$