← 목록으로 돌아가기
목차
- 카마이클 함수 (Carmichael's Lambda Function)
- p-adic 분석 (p-adic Valuation)
- 중국인의 나머지 정리 (Chinese Remainder Theorem)
- 연습문제
1. 카마이클 함수 (Carmichael's Lambda Function)
1.1 정의와 기본 개념
정의: 카마이클 함수
카마이클 함수 $\lambda(n)$은 다음을 만족하는 가장 작은 양의 정수입니다:
$$a^{\lambda(n)} \equiv 1 \pmod{n} \quad \text{for all } \gcd(a,n) = 1$$
이는 군론에서 말하는 $(\mathbb{Z}/n\mathbb{Z})^*$의 지수(exponent)입니다.
오일러 함수와의 관계
오일러 정리는 다음을 말합니다:
$$a^{\phi(n)} \equiv 1 \pmod{n} \quad \text{for } \gcd(a,n) = 1$$
카마이클 함수는 이것의 개선된 버전입니다:
$$\lambda(n) \mid \phi(n) \quad \text{and} \quad \lambda(n) \leq \phi(n)$$
즉, 카마이클 함수는 1이 되는 최소 지수를 제공합니다.
1.2 계산 공식
규칙 1: 소수 거듭제곱
2의 거듭제곱 (특수 케이스):
- $\lambda(1) = 1$
- $\lambda(2) = 1$
- $\lambda(4) = 2$
- $\lambda(2^k) = 2^{k-2}$ for $k \geq 3$
홀수 소수 $p$의 거듭제곱:
$$\lambda(p^k) = \phi(p^k) = p^{k-1}(p-1)$$
규칙 2: 서로소인 수들의 곱
$\gcd(m,n) = 1$일 때:
$$\lambda(mn) = \text{lcm}(\lambda(m), \lambda(n))$$
예제: $\lambda(100)$ 계산
$100 = 4 \times 25 = 2^2 \times 5^2$
단계 1: 각 소수 거듭제곱에 대해:
$$\begin{align}
\lambda(4) &= \lambda(2^2) = 2 \\
\lambda(25) &= \lambda(5^2) = \phi(5^2) = 5^{2-1} \cdot (5-1) = 5 \cdot 4 = 20
\end{align}$$
단계 2: LCM 계산:
$$\lambda(100) = \text{lcm}(2, 20) = 20$$
오일러 함수와의 비교:
$$\phi(100) = \phi(4) \cdot \phi(25) = 2 \cdot 20 = 40$$
결과:
- $\lambda(100) = 20$ ← 더 작음!
- $\phi(100) = 40$
이것은 $\gcd(a, 100) = 1$인 모든 $a$에 대해:
$$a^{20} \equiv 1 \pmod{100}$$
둘 다 맞지만, 20이 최소 지수입니다.
1.3 더 많은 예시
| $n$ |
소인수분해 |
$\lambda(n)$ |
$\phi(n)$ |
| 12 |
$2^2 \times 3$ |
lcm(2, 2) = 2 |
4 |
| 15 |
$3 \times 5$ |
lcm(2, 4) = 4 |
8 |
| 20 |
$2^2 \times 5$ |
lcm(2, 4) = 4 |
8 |
| 21 |
$3 \times 7$ |
lcm(2, 6) = 6 |
12 |
| 24 |
$2^3 \times 3$ |
lcm(2, 2) = 2 |
8 |
| 30 |
$2 \times 3 \times 5$ |
lcm(1, 2, 4) = 4 |
8 |
패턴 관찰:
- 2의 거듭제곱 때문에 $\lambda(n)$이 $\phi(n)$보다 훨씬 작을 수 있습니다.
- $n$이 홀수이고 제곱 없는 수(square-free)이면 $\lambda(n) = \phi(n)/2$
2. p-adic 분석 (p-adic Valuation)
2.1 정의와 기본 개념
정의: p-adic valuation
$p$-adic valuation $v_p(n)$은 정수 $n$을 나누는 소수 $p$의 최대 거듭제곱 지수입니다.
수학적으로:
$$n = p^{v_p(n)} \cdot m \quad \text{where } \gcd(p, m) = 1$$
p-adic valuation 계산 예시
- $v_2(24) = ?$
- $24 = 2^3 \times 3$
- $v_2(24) = 3$
- $v_5(250) = ?$
- $250 = 2 \times 5^3$
- $v_5(250) = 3$
- $v_3(100) = ?$
- $100 = 2^2 \times 5^2$
- $v_3(100) = 0$ (3으로 나누어지지 않음)
2.2 기본 성질
p-adic valuation의 성질
- 곱셈: $v_p(ab) = v_p(a) + v_p(b)$
- 거듭제곱: $v_p(a^k) = k \cdot v_p(a)$
- 나눗셈: $v_p(a/b) = v_p(a) - v_p(b)$ (단, $b \neq 0$)
- 덧셈 (삼각 부등식): $v_p(a + b) \geq \min(v_p(a), v_p(b))$
2.3 르장드르 공식 (Legendre's Formula)
정리: 르장드르 공식
$N!$에서 소수 $p$의 거듭제곱:
$$v_p(N!) = \sum_{i=1}^{\infty} \left\lfloor \frac{N}{p^i} \right\rfloor$$
실제로는 $p^i > N$이면 항이 0이므로 유한 합입니다.
예제: $v_5(100!)$ 계산
$$\begin{align}
v_5(100!) &= \left\lfloor \frac{100}{5} \right\rfloor + \left\lfloor \frac{100}{25} \right\rfloor + \left\lfloor \frac{100}{125} \right\rfloor + \cdots \\
&= 20 + 4 + 0 + \cdots = 24
\end{align}$$
따라서 $100! = 5^{24} \times (\text{5와 서로소인 수})$
직관적 이해:
- $\lfloor 100/5 \rfloor = 20$: 5의 배수 개수
- $\lfloor 100/25 \rfloor = 4$: 25의 배수 개수 (추가로 5를 하나 더)
- $\lfloor 100/125 \rfloor = 0$: 125의 배수 개수
3. 중국인의 나머지 정리 (Chinese Remainder Theorem)
3.1 정의와 정리
정리: 중국인의 나머지 정리
$m_1, m_2, \ldots, m_k$가 쌍으로 서로소인 양의 정수들이고 (즉, $\gcd(m_i, m_j) = 1$ for $i \neq j$),
$a_1, a_2, \ldots, a_k$가 임의의 정수들일 때, 다음 연립 합동식:
$$\begin{cases}
x \equiv a_1 \pmod{m_1} \\
x \equiv a_2 \pmod{m_2} \\
\vdots \\
x \equiv a_k \pmod{m_k}
\end{cases}$$
은 $\bmod M = m_1 \cdot m_2 \cdot \cdots \cdot m_k$에서 유일한 해를 가집니다.
역사적 배경
이 정리는 중국 수학자 손자(孫子, Sun Tzu, 4세기경)의 저서 『손자산경(孫子算經)』에 처음 등장했습니다.
원래 문제:
"물건의 개수를 3으로 나누면 2가 남고, 5로 나누면 3이 남고, 7로 나누면 2가 남는다. 물건은 몇 개인가?"
$$\begin{cases}
x \equiv 2 \pmod{3} \\
x \equiv 3 \pmod{5} \\
x \equiv 2 \pmod{7}
\end{cases}$$
답: $x \equiv 23 \pmod{105}$ (최소 양수 해는 23)
3.2 두 개 합동식의 경우
예제: 간단한 2개 합동식
$$\begin{cases}
x \equiv 2 \pmod{5} \\
x \equiv 3 \pmod{7}
\end{cases}$$
$M = 5 \times 7 = 35$
$M_1 = 35/5 = 7$, $M_2 = 35/7 = 5$
$y_1$ 찾기: $7 \cdot y_1 \equiv 1 \pmod{5}$
- $7 \equiv 2 \pmod{5}$
- $2 \cdot y_1 \equiv 1 \pmod{5}$
- $y_1 = 3$ (왜냐하면 $2 \times 3 = 6 \equiv 1 \pmod{5}$)
$y_2$ 찾기: $5 \cdot y_2 \equiv 1 \pmod{7}$
- $y_2 = 3$ (왜냐하면 $5 \times 3 = 15 \equiv 1 \pmod{7}$)
해 구성:
$$\begin{align}
x &= 2 \cdot 7 \cdot 3 + 3 \cdot 5 \cdot 3 = 42 + 45 = 87 \\
87 &\bmod 35 = 17
\end{align}$$
답: $x \equiv 17 \pmod{35}$
검증:
- $17 = 3 \times 5 + 2 \equiv 2 \pmod{5}$ ✓
- $17 = 2 \times 7 + 3 \equiv 3 \pmod{7}$ ✓
3.3 세 개 이상 합동식의 경우
예제: 손자의 원래 문제
$$\begin{cases}
x \equiv 2 \pmod{3} \\
x \equiv 3 \pmod{5} \\
x \equiv 2 \pmod{7}
\end{cases}$$
$M = 3 \times 5 \times 7 = 105$
$M_1 = 105/3 = 35$, $M_2 = 105/5 = 21$, $M_3 = 105/7 = 15$
$y_1$ 찾기: $35 \cdot y_1 \equiv 1 \pmod{3}$
- $35 = 11 \times 3 + 2 \equiv 2 \pmod{3}$
- $2 \cdot y_1 \equiv 1 \pmod{3}$
- $y_1 = 2$ (왜냐하면 $2 \times 2 = 4 \equiv 1 \pmod{3}$)
$y_2$ 찾기: $21 \cdot y_2 \equiv 1 \pmod{5}$
- $21 = 4 \times 5 + 1 \equiv 1 \pmod{5}$
- $y_2 = 1$
$y_3$ 찾기: $15 \cdot y_3 \equiv 1 \pmod{7}$
- $15 = 2 \times 7 + 1 \equiv 1 \pmod{7}$
- $y_3 = 1$
해 구성:
$$\begin{align}
x &= 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \\
&= 140 + 63 + 30 = 233
\end{align}$$
$233 = 2 \times 105 + 23$
답: $x \equiv 23 \pmod{105}$
검증:
- $23 = 7 \times 3 + 2 \equiv 2 \pmod{3}$ ✓
- $23 = 4 \times 5 + 3 \equiv 3 \pmod{5}$ ✓
- $23 = 3 \times 7 + 2 \equiv 2 \pmod{7}$ ✓
최소 양의 정수 해는 23입니다!
3.4 응용과 활용
- 큰 수의 모듈러 연산: 큰 모듈러스 $n = p_1 \cdot p_2 \cdot \cdots \cdot p_k$ (소인수분해)에 대한 계산을 각 소인수별로 분리하여 계산 후 결합
- 달력 문제: 여러 주기가 있는 현상들의 동시 발생 시점 찾기
- 수 이론 문제: 여러 나머지 조건을 만족하는 수 찾기
- 암호학: RSA 암호 시스템의 핵심 도구
4. 연습문제
연습문제 1: $\lambda(360)$ 계산
$\lambda(360)$을 계산하시오.
풀이
단계 1: 소인수분해
$$360 = 8 \times 45 = 2^3 \times 3^2 \times 5$$
단계 2: 각 소수 거듭제곱에 대한 카마이클 함수
$$\begin{align}
\lambda(2^3) &= 2^{3-2} = 2 \\
\lambda(3^2) &= \phi(3^2) = 3^{2-1}(3-1) = 3 \times 2 = 6 \\
\lambda(5) &= \phi(5) = 4
\end{align}$$
단계 3: LCM 계산
$$\lambda(360) = \text{lcm}(2, 6, 4) = 12$$
답: $\lambda(360) = 12$
검증: $\phi(360) = \phi(2^3) \times \phi(3^2) \times \phi(5) = 4 \times 6 \times 4 = 96$
$\lambda(360) = 12$는 $\phi(360) = 96$의 약수입니다. ($96 = 12 \times 8$) ✓
연습문제 2: 팩토리얼의 끝자리 0의 개수
$1000!$의 끝자리에 0이 몇 개 붙는가?
풀이
끝자리 0의 개수 = $\min(v_2(1000!), v_5(1000!))$
일반적으로 $v_5(n!) < v_2(n!)$이므로 $v_5(1000!)$만 계산하면 됩니다.
르장드르 공식:
$$v_5(1000!) = \sum_{i=1}^{\infty} \left\lfloor \frac{1000}{5^i} \right\rfloor$$
계산:
$$\begin{align}
\left\lfloor \frac{1000}{5} \right\rfloor &= 200 \\
\left\lfloor \frac{1000}{25} \right\rfloor &= 40 \\
\left\lfloor \frac{1000}{125} \right\rfloor &= 8 \\
\left\lfloor \frac{1000}{625} \right\rfloor &= 1 \\
\left\lfloor \frac{1000}{3125} \right\rfloor &= 0
\end{align}$$
합계:
$$v_5(1000!) = 200 + 40 + 8 + 1 = 249$$
답: $1000!$의 끝자리에는 249개의 0이 붙습니다.
연습문제 3: 연립 합동식 풀기
다음 연립 합동식을 풀어라.
$$\begin{cases}
x \equiv 3 \pmod{8} \\
x \equiv 5 \pmod{13}
\end{cases}$$
풀이
$\gcd(8, 13) = 1$이므로 중국인의 나머지 정리를 적용할 수 있습니다.
$M = 8 \times 13 = 104$
$M_1 = 104/8 = 13$, $M_2 = 104/13 = 8$
$y_1$ 찾기: $13 \cdot y_1 \equiv 1 \pmod{8}$
- $13 = 1 \times 8 + 5 \equiv 5 \pmod{8}$
- $5 \cdot y_1 \equiv 1 \pmod{8}$
- 시행착오: $5 \times 5 = 25 \equiv 1 \pmod{8}$
- $y_1 = 5$
$y_2$ 찾기: $8 \cdot y_2 \equiv 1 \pmod{13}$
- 확장 유클리드: $8 \times 5 = 40 = 3 \times 13 + 1$
- $y_2 = 5$
해 구성:
$$\begin{align}
x &= 3 \cdot 13 \cdot 5 + 5 \cdot 8 \cdot 5 \\
&= 195 + 200 = 395 \\
395 &= 3 \times 104 + 83
\end{align}$$
답: $x \equiv 83 \pmod{104}$
검증:
- $83 = 10 \times 8 + 3 \equiv 3 \pmod{8}$ ✓
- $83 = 6 \times 13 + 5 \equiv 5 \pmod{13}$ ✓
최소 양의 정수 해: $x = 83$
5. 핵심 요약
카마이클 함수
- 정의: $a^{\lambda(n)} \equiv 1 \pmod{n}$을 만족하는 최소 지수
- 계산: $\lambda(p^k)$ 공식 + LCM
- 활용: 거듭제곱 계산 최적화, 주기 분석
p-adic 분석
- 정의: $v_p(n)$ = $n$을 나누는 $p$의 최대 거듭제곱 지수
- 성질: 곱셈, 거듭제곱, 나눗셈 규칙
- 르장드르 공식: $v_p(N!) = \sum_{i \geq 1} \lfloor N/p^i \rfloor$
- 활용: 나누어떨어짐 분석, 조합론 문제
중국인의 나머지 정리
- 정의: 서로소인 모듈러스에 대한 연립 합동식의 유일해 존재
- 2개 합동식: 직접 대입 또는 구성적 방법
- 3개 이상: 순차적 해결 또는 일반 공식
- 활용: 큰 수의 모듈러 연산, RSA 암호화
결합 사용
- 세 기법을 함께 사용하여 복잡한 문제 해결
- 각 소수별로 독립적 분석 (p-adic) 후 결합 (CRT)
- 거듭제곱 최적화 (카마이클 함수)