1.2 소수와 산술의 기본정리 (Primes & FTA)
모든 정수는 소수의 곱으로 유일하게 표현됩니다. 이 성질을 증명하고 응용하는 10가지 핵심 예제를 통해 정수의 근본 구조를 파헤쳐 봅니다.
Ex 1. 유클리드 보조정리 (Euclid's Lemma)
문제: $p$가 소수이고 $p \mid ab$이면, $p \mid a$ 또는 $p \mid b$임을 증명하시오.
$p \nmid a$라고 가정하자. $p$는 소수이므로 $\gcd(p, a) = 1$이다.
베주 항등식에 의해 $px + ay = 1$인 정수 $x, y$가 존재한다.
양변에 $b$를 곱하면 $pbx + aby = b$이다.
$p \mid pbx$이고 $p \mid aby$ (가정에 의해) 이므로, $p$는 그 합인 $b$를 나눈다. $\therefore p \mid b$
Ex 2. 소수의 무한성 (Euclid's Proof)
문제: 소수가 무한히 존재함을 귀류법으로 증명하시오.
소수가 유한개 $\{p_1, p_2, \dots, p_n\}$이라 가정하자.
$P = (p_1 p_2 \dots p_n) + 1$이라는 수를 생각한다.
$P$는 1보다 크므로 산술의 기본정리에 의해 최소 하나 이상의 소수 약수를 가져야 한다.
그러나 $P$를 임의의 $p_i$로 나누면 나머지가 항상 1이다.
즉, 어떤 $p_i$도 $P$를 나누지 못하므로 이는 모순이다. $\therefore$ 소수는 무한하다.
Ex 3. FTA 응용 - 무리수 증명
문제: 산술의 기본정리를 이용하여 $\sqrt{2}$가 무리수임을 보이시오.
$\sqrt{2} = a/b$ (기약분수)라 가정하면 $2b^2 = a^2$이다.
좌변 $2b^2$을 소인수분해했을 때 소인수 2의 지수는 홀수($2k+1$)이다.
우변 $a^2$을 소인수분해했을 때 모든 소인수의 지수는 짝수($2m$)여야 한다.
소인수분해의 유일성에 의해 지수의 홀짝이 다를 수 없으므로 모순이다.
Ex 4. 소인수분해와 GCD/LCM
문제: $n = p_1^{a_1} \dots p_k^{a_k}$, $m = p_1^{b_1} \dots p_k^{b_k}$일 때 $\gcd(n, m)$을 표현하시오.
$\gcd(n, m) = p_1^{\min(a_1, b_1)} p_2^{\min(a_2, b_2)} \dots p_k^{\min(a_k, b_k)}$
(참고: $LCM(n, m)$은 $\min$ 대신 $\max$를 사용한다.)
Ex 5. 약수 함수 ($\tau$)
문제: $n = p_1^{e_1} p_2^{e_2} \dots p_k^{e_k}$일 때, $n$의 양의 약수의 개수를 구하시오.
$n$의 약수 $d$는 $d = p_1^{f_1} \dots p_k^{f_k}$ ($0 \le f_i \le e_i$) 꼴이어야 한다.
각 $f_i$를 선택하는 방법은 $(e_i + 1)$가지이다.
곱의 법칙에 의해 약수의 개수는 $(e_1+1)(e_2+1)\dots(e_k+1)$이다.
Ex 6. 특수 형태의 소수
문제: $4n+3$ 꼴의 소수가 무한히 많음을 증명하시오.
유한하다고 가정하고 $\{p_1, \dots, p_k\}$라 하자.
$Q = 4(p_1 p_2 \dots p_k) - 1 = 4(p_1 \dots p_k - 1) + 3$ 을 생각한다.
$Q$의 소인수들이 모두 $4n+1$ 꼴이라면 $Q$도 $4n+1$ 꼴이어야 하는데, $Q$는 $4n+3$ 꼴이다.
따라서 $Q$는 적어도 하나의 $4n+3$ 꼴 소인수를 가져야 하며 이는 목록에 없는 소수이다.
Ex 7. 완전제곱수의 조건
문제: $n$이 완전제곱수일 필요충분조건은 소인수분해 시 모든 지수가 짝수임을 보이시오.
$n = m^2$이고 $m = p_1^{a_1} \dots p_k^{a_k}$이면, $n = (p_1^{a_1} \dots p_k^{a_k})^2 = p_1^{2a_1} \dots p_k^{2a_k}$이다.
모든 지수가 $2a_i$로 짝수임이 명백하다. 역도 성립한다.
Ex 8. 페르마 수와 소수
문제: $2^n + 1$이 소수이면 $n$은 2의 거듭제곱 꼴($2^k$)임을 증명하시오.
$n$이 홀수 약수 $m > 1$을 가진다면($n = mt$), $2^n + 1 = (2^t)^m + 1$이다.
이는 $(2^t + 1)$을 인수로 갖게 되어 합성수가 된다.
따라서 $n$은 홀수 약수를 가질 수 없으며, 오직 2의 거듭제곱이어야 한다.
Ex 9. 소수 사이의 간격
문제: 임의의 $k$에 대해 $k$개의 연속된 합성수가 존재함을 보이시오.
$(k+1)! + 2, (k+1)! + 3, \dots, (k+1)! + (k+1)$ 이라는 $k$개의 수를 생각하자.
첫 번째 수는 2의 배수, 두 번째는 3의 배수, ..., 마지막은 $(k+1)$의 배수이다.
모두 자기 자신보다 큰 약수를 가지므로 합성수이다.
Ex 10. 조합론과 소수
문제: 소수 $p$와 $1 \le k \le p-1$인 $k$에 대해, $p \mid \binom{p}{k}$임을 증명하시오.
$\binom{p}{k} = \frac{p!}{k!(p-k)!} \implies k!(p-k)! \binom{p}{k} = p!$
우변은 $p$의 배수이다. 좌변에서 $k < p$이고 $p-k < p$이므로 $k!(p-k)!$의 어떤 소인수도 $p$가 될 수 없다.
유클리드 보조정리에 의해 $\gcd(k!(p-k)!, p) = 1$이므로, 반드시 $p \mid \binom{p}{k}$여야 한다.