유클리드의 정리
유클리드의 정리는 수학, 특히 정수론 분야의 기본적인 정리 중 하나로, 소수의 개수는 무한히 많다는 것을 증명하는 정리이다. 이 정리는 고대 그리스의 수학자 유클리드가 그의 저서 《원론》(Elements) 제9권 명제 20에서 처음으로 증명하였다.
정리의 내용
유클리드의 정리는 소수(1과 자기 자신 외에는 양의 약수를 가지지 않는 1보다 큰 자연수)의 집합이 무한 집합임을 명확히 밝힌다. 즉, 아무리 큰 소수를 찾더라도 그보다 더 큰 소수가 항상 존재한다는 것을 의미한다.
증명 (귀류법)
유클리드는 귀류법을 사용하여 이 정리를 증명하였다. 증명의 핵심 아이디어는 다음과 같다.
- 소수의 개수가 유한하다고 가정한다. 즉, 세상에 존재하는 소수는 유한하며, 이를 $p_1, p_2, \dots, p_n$으로 모두 나열할 수 있다고 가정한다. 여기서 $p_n$은 가장 큰 소수이다.
- 이 유한 개의 소수 모두를 곱한 후 1을 더한 새로운 수 $N$을 생각한다. 즉, $N = (p_1 \times p_2 \times \dots \times p_n) + 1$ 이다.
- 자연수 $N$은 1보다 크므로, 소수이거나 합성수이다. 어떤 경우든 $N$은 반드시 소인수를 가져야 한다. (정수론의 기본 정리)
- $N$의 소인수를 $q$라고 하자. 가정에 따르면 세상의 모든 소수는 $p_1, p_2, \dots, p_n$뿐이므로, $q$는 이 소수들 중 하나와 같아야 한다. 즉, $q$는 ${p_1, p_2, \dots, p_n}$ 집합에 속해야 한다.
- 만약 $q$가 $p_i$ (여기서 $i$는 1부터 $n$까지의 어떤 정수)와 같다고 하자. 그러면 $q$는 $p_1 \times p_2 \times \dots \times p_n$의 약수이다.
- 그런데 $N = (p_1 \times p_2 \times \dots \times p_n) + 1$ 이므로, $N$을 $p_i$로 나누면 나머지가 1이 된다. 따라서 $p_i$는 $N$의 약수가 될 수 없다. 즉, $q$는 $p_i$와 같을 수 없다.
- 이는 $q$가 ${p_1, p_2, \dots, p_n}$ 집합에 속한다는 가정과 모순된다.
- 따라서 소수의 개수가 유한하다는 처음의 가정이 틀렸음이 증명된다.
결론적으로 소수의 개수는 무한히 많다.
의의
유클리드의 정리는 수학사에서 가장 오래되고 중요한 증명 중 하나로 꼽히며, 정수론 연구의 기초가 되었다. 이 정리는 소수가 특정 패턴 없이 무한히 나타난다는 것을 보여주며, 소수의 분포와 관련된 후속 연구들(예: 소수 정리)에 영감을 주었다. 이 증명은 또한 귀류법이라는 강력한 증명 기법의 고전적인 예시로 자주 인용된다.