1.2 소수와 산술의 기본정리 (Primes & FTA)
소수(Prime Number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 수입니다. 소수는 정수론의 가장 기초적인 원자이며, 모든 정수는 이들의 결합으로 설명됩니다.
1. 소수의 정의와 유클리드 보조정리
정수 $p > 1$이 소수일 때, 가장 중요한 성질 중 하나는 유클리드 보조정리(Euclid's Lemma)입니다.
$$p \mid ab \implies p \mid a \text{ 또는 } p \mid b$$
이 성질은 소수가 합성수와 구별되는 결정적인 특징이며, 소인수분해의 유일성을 증명하는 핵심 도구가 됩니다.
2. 소수의 무한성 (Infinitude of Primes)
유클리드는 귀류법을 통해 소수가 무한히 존재함을 증명했습니다.
Proof Sketch
- 소수가 유한개($p_1, p_2, \dots, p_n$)라고 가정합니다.
- 모든 소수의 곱에 1을 더한 수 $N = (p_1 p_2 \dots p_n) + 1$을 만듭니다.
- $N$은 기존의 어떤 소수로 나누어도 나머지가 1이 남습니다.
- 따라서 $N$ 자체가 소수이거나, 목록에 없는 새로운 소수를 약수로 가져야 합니다.
- 이는 가정에 모순이므로 소수는 무한합니다.
3. 산술의 기본정리 (Fundamental Theorem of Arithmetic)
1보다 큰 모든 정수는 소수들의 곱으로 나타낼 수 있으며, 이 표현은 소수들의 순서를 무시하면 유일(Unique)합니다.
$$n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$$
이 정리는 두 단계로 증명됩니다.
- 존재성(Existence): 강한 수학적 귀납법을 통해 증명.
- 유일성(Uniqueness): 위에서 언급한 유클리드 보조정리를 통해 증명.
[Image showing the prime factorization tree for a composite number]
4. 소수 정리 (Prime Number Theorem)
소수의 정확한 분포를 알 수는 없지만, $x$보다 작은 소수의 개수 $\pi(x)$의 근사적 분포는 다음과 같습니다.
$$\pi(x) \approx \frac{x}{\ln x}$$