소수는 끝이 없다
모든 소수를 다 모았다고 해 보세요
2, 3, 5, 7, 11, 13... 더 이상 쪼개지지 않는 소수를 크기순으로 찾아 공책에 적어나갑니다. 수가 커질수록 소수는 점점 드물게 나타납니다.
세상에 존재하는 모든 소수를 다 모아서 거대한 상자에 담았다고 상상해 보세요. 단 한 줄의 곱셈으로 상자 밖의 새로운 소수가 튀어나옵니다. 왜 소수는 영원히 끝나지 않고 이어질까요?
이야기
?
Public domain · 위키미디어 공용
기원전 300년쯤 알렉산드리아. 에우클레이데스가 『원론』 아홉째 권에 이 증명을 적었습니다. 스무 번째 명제입니다.
그런데 그는 「소수는 무한히 많다」고 쓰지 않았습니다. 그리스 사람들은 「무한」이라는 말을 함부로 쓰지 않았기 때문입니다. 그가 적은 문장은 「소수는 어떤 정해진 개수보다도 많다」였습니다. 무한을 말하지 않고 무한을 증명한 것입니다.
까닭은 이렇습니다. 소수를 다 모아 곱하고 1을 더한 수를 N이라 합시다. N을 그 소수들 가운데 어느 것으로 나누어도 반드시 1이 남습니다. 모든 소수의 곱에 1을 더했기 때문입니다.
그러면 N은 그 목록에 없는 소수를 약수로 가지거나, N 자신이 새 소수입니다. 어느 쪽이든 목록 밖에 소수가 또 있습니다. 그래서 목록은 결코 완성될 수 없습니다.
⭐ 두 줄짜리 이 논증은 2300년이 지난 지금도 한 글자도 고칠 데가 없습니다.
암호가 마르지 않는 근거입니다. 소수가 끝이 없으니 새 열쇠를 언제까지나 만들 수 있습니다.
은행과 메신저가 매일 수억 개의 새 소수를 뽑아 쓰는데, 그것이 가능한 까닭이 이천삼백 년 전 두 줄짜리 증명입니다.
계단 넷 — 같은 사실을 네 깊이로
소수를 찾아 늘어놓는다·체로 거른다
2부터 시작해 소수들을 하나씩 찾아봅니다. 소수 몇 개를 골라 모두 곱한 다음 1을 더해 봅니다.
2×3+1=7(소수), 2×3×5+1=31(소수), 2×3×5×7+1=211(소수)입니다. 우리가 모은 소수들로는 절대 나누어떨어지지 않고 늘 1이 남는 수가 태어납니다. 새로운 소수가 나타날 수밖에 없습니다.
다 곱하고 하나 더해 보세요
31 은 2 로도 3 으로도 5 로도 안 나뉩니다 — 나머지가 늘 1 이니까요.
귀류법 한 줄 증명
소수가 으로 유한 개뿐이라고 가정합니다. 이 소수들을 몽땅 곱하고 1을 더한 큰 수 을 만듭니다.
을 어떤 기존 소수로 나누어도 나머지가 항상 1이 됩니다. 따라서 자신이 새로운 소수이거나, 기존 목록에 없는 또 다른 소수를 약수로 가져야 합니다. 이는 소수가 유한하다는 가정과 정면으로 부딪칩니다.
나머지가 늘 1 입니다
곱+1 이 소수가 아니어도 좋습니다. 그 약수가 새 소수이면 됩니다.
소수의 분포·간격
기원전 300년 유클리드가 『원론』 제9권 명제 20에 남긴 이 증명은 인류 역사상 가장 우아한 귀류법 증명으로 꼽힙니다.
오일러는 조화급수의 발산과 오일러 곱 공식 을 통해 소수의 무한성을 해석학적으로 재증명했습니다. 임도 밝혀져 소수가 제곱수보다 훨씬 조밀하게 무한히 분포함을 보였습니다.
소수 사이의 틈
드물어질 뿐, 끊기지 않습니다.
소수 정리
소수의 분포는 가우스가 추측하고 아다마르와 드 라 발레 푸생이 증명한 소수 정리(Prime Number Theorem) 로 정량화되었습니다.
소수 간격의 무한성을 다루는 쌍둥이 소수 추측, 장이탕의 유계 간격 정리, 그리고 소수 분포의 오차항을 지배하는 리만 가설(Riemann Hypothesis)은 현대 해석적 정수론의 가장 깊은 심장부입니다.
역수를 더하면 발산합니다
∑1/n² 는 π²/6 로 모이는데, 소수의 역수는 끝없이 커집니다 — 소수가 그만큼 빽빽하다는 뜻입니다.
풀어 보기
유클리드의 소수 무한성 증명. 소수 이 있다.
(1) 의 값을 계산하고 이 수가 소수인지 판정하시오.
(2) 은 소수가 아니다. 일 때, 두 소인수 59와 509가 기존 소수 목록(2~13)에 포함되지 않는 까닭을 쓰시오.
(3) 연속한 100개의 자연수 이 모두 합성수임을 설명하시오.
(1) 31(소수), (3) 는 로 나누어떨어지므로 합성수입니다.
답과 풀이 보기
(1) 이고 소수입니다.
이므로 2, 3, 5 로만 나눠 보면 되는데 모두 1 이 남습니다.
(2) 을 2 부터 13 까지 어느 소수로 나누어도 1 이 남기 때문입니다.
이므로 괄호 안은 그 여섯 소수로 모두 나누어떨어지고, 거기에 1 을 더했으니 나머지가 언제나 1 입니다.
그러므로 의 소인수는 목록 밖의 것이어야 하고, 실제로 와 는 13 보다 큽니다.
⭐ 바로 이것이 증명의 심장입니다 — 이 소수가 아니어도 상관없습니다. 새 소수가 반드시 나온다는 것만으로 충분합니다. 그러니 소수 목록은 결코 완성될 수 없습니다.
(3) 에 대해
은 를 인수로 갖습니다.
그러므로 — 로 나누어떨어집니다.
이므로 그 100 개는 모두 합성수입니다.
(2) 는 소수가 끝없이 있다고 말하고, (3) 은 소수가 없는 벌판이 얼마든지 넓을 수 있다고 말합니다.
둘 다 참입니다. 소수는 끝없이 있으면서 점점 드물어집니다.
1000 개든 100 만 개든, 소수가 하나도 없는 구간을 원하는 만큼 길게 만들 수 있습니다. 그런데도 그 너머에는 반드시 또 소수가 있습니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
「무한히 많다」를 두 줄로 보인 고전입니다.
- 귀류법 — 아니라고 가정하고 모순을 끌어냅니다
- 소수 정리 — 소수가 얼마나 자주 나오는지도 밝혀졌습니다
- 확인해 보기 — 2×3×5×7+1 = 211 은 소수입니다. 2×3×5×7×11×13+1 = 30031 은 59×509 입니다
이어지는 장
소수가 무한히 많다는 유클리드의 증명 위에 서면 자연스럽게 다음 물음이 떠오릅니다. 차이가 2에 불과한 소수 쌍도 무한히 이어질까요? — 제99장 에서 끝없는 수의 바다에 흩어진 소수들의 간격을 따라가 보세요.
영감을 받은 곳
기원전 300년경 유클리드의 『원론』(Elements) 제9권 명제 20에서 유한개의 소수 곱에 1을 더해 모순을 이끌어내는 귀류법으로 기록되었습니다.