소수가 무한히 많다는 유클리드의 증명

기원전 300년경, 유클리드는 단 한 단락에 들어맞는 논증을 써 내려갔습니다. 그것은 개선된 적이 없고, 개선될 수도 없습니다. 주장은 소수가 영원히 계속된다는 것이고, 증명은 구성입니다. 소수의 유한 목록을 주면, 그 목록에 없는 소수를 하나 내어 드리겠습니다.

2000년이 지난 지금도 이 논증은 좋은 마술처럼 느껴집니다. 모든 단계가 명확하게 보이고, 어떻게 끝날지도 정확히 압니다. 그래도 여전히 강렬하게 와 닿습니다.

소수란 무엇이며 왜 이 질문이 중요한가

소수는 1보다 큰 자연수 중 약수가 1과 자기 자신뿐인 수입니다. 첫 몇 개는 2, 3, 5, 7, 11, 13입니다. 자연수 안에 원자처럼 박혀 있습니다. 다른 모든 자연수는 소수들을 곱해서 만들어집니다. 예를 들어 30은 2 곱하기 3 곱하기 5로 분해되며, 그 인수분해 방법은 본질적으로 하나뿐입니다.

소수가 모든 자연수의 구성 요소라는 점을 감안하면, 자연스럽게 묻게 됩니다. 소수는 바닥나는가? 가장 큰 소수가 있고, 그 너머에는 우물이 말라 있는가? 유클리드의 답은 아니오이며, 그가 택하는 경로는 한 번의 앉음으로 따라갈 수 있을 만큼 우아합니다.

준비: 목록이 완전하다고 가정하기

논증은 귀류법 증명입니다. 상대방이 원하는 모든 것을 허용하는 것에서 시작합니다.

이제 존재하는 모든 소수를 그 목록에 모은 뒤, 그로부터 새로운 수를 만듭니다.

목록을 깨는 수 구성하기

이것이 핵심 이동이며, 무슨 일을 하는지 천천히 볼 만합니다. 목록의 모든 소수를 곱하면 목록의 모든 소수가 균등하게 나누어지는 수가 나옵니다. 1을 더하면 그것들을 한꺼번에 흔들어 버립니다.

N을 p1으로 나누면 나머지가 1이 됩니다. (p1 곱하기 p2 곱하기 ... 곱하기 pk)가 p1으로 나누어지고, 1을 더하면 나머지가 1이 되기 때문입니다. 같은 논리가 p2에도, p3에도, 목록의 모든 소수에도 적용됩니다. 그 중 어느 것도 N을 균등하게 나누지 못합니다.

모순

증명을 정직하게 만드는 반례

많은 유클리드 증명의 대중적 설명이 여기서 빗나갑니다. N 자체가 항상 소수라고 주장합니다. 그렇지 않으며, 이 구별은 중요합니다.

목록 13을 취합니다. 곱은 2 곱하기 3 곱하기 5 곱하기 7 곱하기 11 곱하기 13이며 30030입니다. 1을 더하면 N = 30031이 됩니다.

30031이 소수인가요? 아닙니다.

30031 = 59 곱하기 509.

59와 509는 모두 소수이며, 목록 13에 없습니다. 이것이 바로 증명이 예측하는 것입니다. N이 소수라는 것이 아니라, N의 소인수들이 목록에 없다는 것입니다. 이 경우 소인수들은 59와 509, 즉 유한 목록에서 빠진 두 소수입니다. 논증이 입증되었지만, 입증은 N 자체에서가 아니라 그 인수들에서 옵니다.

증명이 실제로 말하는 것

논증의 형태를 잠시 살펴볼 만합니다. 유난히 깔끔하기 때문입니다.

빠진 소수를 명시적으로 구성하지 않습니다. 찾아 헤매지도 않습니다. 반대를 가정하면 논리적 막다른 길로 이어진다는 것을 보임으로써 그것이 반드시 존재해야 한다는 것을 증명합니다. N의 인수에 숨어 있는 소수 q는 찾기 쉬울 수도 있고(30031의 작은 약수 몇 개를 시도하면 59와 509가 나오듯이), 거대할 수도 있습니다. 증명은 신경 쓰지 않습니다. 힘은 필연성에서 나옵니다. 어떤 목록을 건네든, 구성이 빈틈을 찾습니다.

이것은 "반대를 가정하고 무너지는 것을 지켜보라"는 같은 정신으로 진행되는 다른 증명들과 자연스럽게 이어집니다. 칸토어의 대각선 논증은 더 큰 규모에서 같은 구조를 사용합니다. 실수의 완전한 목록이 존재한다고 가정하고, 그 목록에 없는 실수를 구성합니다. 유클리드의 메아리가 뚜렷합니다.

소수가 결코 완전히 희박해지지 않는 이유

증명이 알려 주지 않는 한 가지는 소수들이 얼마나 멀리 떨어져 있을 수 있는지, 또는 어떤 주어진 소수 다음 소수가 얼마나 클 수 있는지입니다. 유클리드의 논증은 존재만을 보장합니다. 어떤 유한 모음을 넘어서도 어딘가에 소수가 있습니다. 수직선 위의 소수 분포는 훨씬 어려운 문제이며, 오늘날에도 수학의 가장 깊은 미해결 분야 중 하나입니다.

증명이 알려 주는 것은 구조적입니다. 소수는 어떤 유한한 수단으로도 소진될 수 없습니다. 평생 소수를 나열하는 데 바칠 수 있고, 여전히 무한한 나머지 안으로 나열하고 있을 것입니다. 찾은 모든 소수는 실재했지만, 앞에 있는 소수들도 마찬가지로 실재했고, 마찬가지로 많았으며, 유한 목록으로는 마찬가지로 도달할 수 없었습니다.

곱셈과 지수로 수를 만들 때 얼마나 빠르게 커질 수 있는지 느껴 보려면, 지수를 직관적으로 이해하는 글이 자연스러운 동반자입니다. p1 곱하기 p2 곱하기 ... 곱하기 pk의 곱은 예상보다 빠르게 커지며, 그 성장이 N이 그토록 빨리 커지는 이유의 일부입니다.

그 속의 선(禪)

유클리드의 증명은 2000년이 넘었고, 수학자들은 그 이후 같은 결과의 증명을 수백 개 찾아냈습니다. 그 어느 것도 이 증명을 낡은 것으로 만들지 않았습니다. 가장 영리하거나 가장 일반적이어서가 아니라, 가장 투명하기 때문에 자리를 지킵니다.

한 번의 통독으로 논증 전체가 보입니다. 구성이 자연스럽습니다. 모순이 날카롭습니다. 어떤 복잡한 기계가 자신이 주장하는 것을 하고 있다고 믿어야 하는 단계가 없습니다.

이 증명이 마음에 간직하도록 요청하는 것은 하나의 아이디어입니다. 소수의 어떤 유한 목록도 이미 불완전합니다. 목록이 잘못 선택되어서가 아니라, 소수는 어떤 유한한 수로도 담을 수 없는 종류의 것이기 때문입니다. 소수는 정수가 그렇듯, 분수가 그렇듯, 직선의 점들이 그렇듯 무한에 속합니다. 증명은 다음 소수가 어디 있는지 알려 주지 않습니다. 다음 소수가 항상 거기 있다고 알려 줍니다.

그것으로 충분합니다. 그것은 언제나 충분했습니다.

같은 필연성의 정신을 공유하는 다른 결과들로는 굿스타인 정리가 있습니다. 이것은 쓸 수 있는 모든 것을 넘어 성장하면서도 항상 0으로 돌아오는 수열을 보여 주며, "다른 것은 불가능하기 때문에 무언가가 일어나야 한다"는 같은 논리를 사용합니다. 이 논증들의 가족은 알 만합니다. 각각은 같은 근본적인 사실에 대한 다른 각도입니다. 수학에는 탈출구가 없습니다. 구조는 유지됩니다.