인류가 증명하려 했던 것들 · 유클리드 / 02

가장 큰 소수를
찾을 수 있을까?

소수를 아무리 많이 찾아도 끝에 닿을 수 있을까요? 유클리드는 『원론』 제9권 명제 20에서 어떤 유한한 소수 목록을 주어도 그 밖의 소수를 찾을 수 있다는 논증을 제시했습니다. 오늘의 “소수는 무한히 많다”는 정리는 이 명제를 현대적인 말로 옮긴 것입니다.

핵심 질문 · 모든 소수를 적었다고 생각한 목록을 언제나 넘어설 수 있을까?

유클리드
Euclid · 기원전 300년 무렵

수학자
알렉산드리아

현존하는 초상은 후대의 상상도입니다. 생애 기록은 매우 제한적입니다.

01 · 증명을 남긴 사람

생애 자료는 단편적이고,
『원론』의 증명 구조는 또렷하게 남았습니다.

전해지는 유클리드의 생애 자료는 단편적입니다. 후대의 프로클로스는 그를 프톨레마이오스 1세 무렵의 인물로 전합니다. 『원론』 제7–9권의 수론 전개를 따라가면 이 증명이 맡는 역할이 선명해집니다.

기원전 300년 무렵

알렉산드리아의 수학

활동 시기는 대체로 기원전 300년 무렵으로 잡습니다. 정확한 생몰년과 출생지는 확정하기 어렵습니다.

VII–IX

수론을 체계로 엮다

『원론』 제7–9권은 소수, 비, 최대공약수와 완전수까지 이어지는 수론의 흐름을 구성합니다.

IX.20

목록의 끝을 넘어서다

명제 20은 임의로 주어진 유한한 소수들보다 더 많은 소수가 있음을 보이며 아무리 많은 소수를 찾아 놓아도 목록을 더 늘릴 수 있음을 증명합니다.

VII.31

앞선 정리를 다시 쓰다

새 수가 합성수이면 “모든 합성수는 어떤 소수로 나누어진다”는 명제 31을 끌어와 논증을 완성합니다.

“어떤 소수의 무리를 정해도, 소수는 그보다 더 많이 존재한다.”유클리드, 『원론』 제9권 명제 20 · 한국어 옮김

02 · 증명을 따라가다

목록을 정하고,
그 바깥으로 나가는 수를 만듭니다.

원문은 A, B, C라는 소수들이 모두 나누는 가장 작은 수에 1을 더합니다. 아래에서는 같은 구조를 현대 기호로 일반화합니다.

출발임의의 목록

유한한 소수 목록을 하나 잡습니다.

출발

p₁, p₂, …, pₙ

목록은 원하는 만큼 길어도 됩니다. 핵심은 유한하다는 점입니다.

모든 목록 원소와 관계있는 수를 만듭니다

새 수 만들기하나를 더한 수

모두 곱하고 1을 더합니다.

M=p₁p₂···pₙ

M은 모든 pᵢ로 나누어집니다.

N=M+1

목록 전체에서 한 칸 벗어난 수를 만듭니다.

원전의 표현 유클리드는 A, B, C가 모두 나누는 가장 작은 수를 사용합니다. 서로 다른 소수에서는 그 최소공배수가 곱과 같습니다.

N을 기존 소수로 나누면 1이 남습니다

기존 목록과 구분나머지는 1

기존 목록의 모든 소수에서 나머지 1이 남습니다.

각 i에 대해

N ≡ 1 (mod pᵢ)

pᵢ가 M을 나누므로 M+1에서는 나머지 1이 남습니다.

N이 소수인지 합성수인지 두 경우를 봅니다

경우 나누기두 경우

어느 경우든 새 소수를 얻습니다.

N이 소수

N ∉ {p₁,…,pₙ}

N 자체가 목록 밖의 소수입니다.

N이 합성수

∃q(q는 소수 ∧ q∣N)

VII.31에 따라 소인수 q가 있습니다. 모든 기존 pᵢ에서 나머지 1이 남으므로 q는 목록 밖에 있습니다.

모든 유한 목록의 바깥에 새 소수가 이어집니다

결론 · 제9권 명제 20목록 밖의 소수

소수는 끝없이 이어집니다.

현대적인 표현

모든 유한한 소수 집합 P에 대해
∃ 소수 q : q ∉ P

어떤 유한한 소수 집합 P를 주어도 그 밖의 소수 q가 있습니다. 따라서 소수는 무한히 많습니다.

소수로 끝나는 예

2·3·5+1= 31

합성수여도 충분

3003159 × 509

2·3·5·7·11·13+1의 소인수도 시작 목록 밖에 있습니다.

03 · 무엇이 증명되었을까?

N이 합성수여도
증명은 그대로 성립합니다.

증명의 목적은 기존 목록 밖의 소수를 확보하는 데 있습니다. N=M+1이 합성수이면 그 소인수 가운데 하나가 새 소수의 역할을 맡습니다.

증명이 확정하는 것

모든 유한한 소수 목록에는 목록 밖의 소수가 있습니다. 그래서 소수 전체는 끝없이 이어집니다.

원전과 현대 설명

유클리드의 원문은 임의의 주어진 소수 목록을 넘어서는 구성입니다. “모든 소수가 유한하다고 가정한다”는 귀류식은 후대의 현대적 재구성입니다.

04 · 증명을 끝까지 생각해 보기

새 소수를 하나 찾았다면,
그다음에도 같은 방법이 통할까요?

소수를 열 개, 백 개 발견하는 일과 소수가 끝없이 있음을 증명하는 일은 다릅니다. 유클리드는 목록이 아무리 길어도 그 목록 밖의 소수를 얻는 방법을 보였습니다. 실제 예를 따라가면 처음에는 신기한 요령처럼 보이던 증명이 왜 모든 목록에 통하는지 알 수 있습니다.

새로 만든 수가 소수일 때

2, 3, 5를 적었다면 2×3×5+1=31입니다. 31은 소수이며 처음 목록에 없습니다. 세 수로 끝난다고 생각한 목록에 네 번째 소수가 추가됩니다.

30031

새로 만든 수가 합성수일 때

2×3×5×7×11×13+1=30031=59×509입니다. 30031 자체는 합성수입니다. 그래도 소인수 59와 509는 처음 목록에 없습니다. 합성수가 나와도 증명은 성공합니다.

386

새 소수가 더 작은 수여도 될까요?

목록을 5, 7, 11로 정하면 5×7×11+1=386=2×193입니다. 소인수 2는 5보다 작습니다. 이 정리가 찾아 주는 것은 '목록보다 큰 소수'보다 더 정확히 말해 목록에 없던 소수입니다. 이미 빠뜨린 작은 소수가 나타나도 됩니다.

원전 IX.20

『원론』은 어떤 수를 만들었을까요?

유클리드는 주어진 소수들의 최소공배수에 1을 더했습니다. 서로 다른 소수들의 최소공배수는 그 곱과 같으므로, 여기서는 곱셈식으로 나타냈습니다. 소인수가 기존 목록에 속할 수 없다는 논리는 그대로입니다.

처음 질문에 대한 답

어떤 유한한 소수 목록도 마지막 목록이 될 수 없습니다.

모든 소수를 적었다고 생각해도 그 소수들을 곱한 뒤 1을 더하면 목록에 없는 소인수를 발견하게 됩니다. 그래서 소수는 끝없이 많습니다.

그런데 이 정리는 소수가 어디에 나타나는지, 소수 사이의 간격이 얼마나 넓어질 수 있는지, 큰 소수를 얼마나 빠르게 찾을 수 있는지까지 알려 주지는 않습니다. 존재함을 보이는 일과 실제로 찾아내는 방법을 연구하는 일은 다음 문제로 이어집니다. 소수의 무한성은 끝이 아니라 수론을 시작하게 하는 토대입니다.

05 · 자료와 더 읽을거리

자료와 출처

유클리드, 『원론』 제9권 명제 20 · 데이비드 조이스 편집본 — 원전의 구성과 두 경우의 증명. 원문 보기 ↗
유클리드, 『원론』 제7권 명제 31 — 합성수의 소인수 존재. 원문 보기 ↗
맥튜터 수학사 자료실 · 유클리드 — 활동 시기와 생애 자료의 한계. 자료 보기 ↗
초상 — 위키미디어 공용의 퍼블릭 도메인 표시 자료인 후대 상상도. 사진 정보 ↗

편집 안내 · IX.20의 원전 흐름을 우선하고 현대 기호를 함께 사용했습니다.