Infinitely many primes — and infinitely many proofs.
소수가 무한히 많다는 건 유클리드가 2300년 전 한 줄로 끝낸 사실입니다. 그런데 수학자들은 그 뒤로도 전혀 다른 길로 같은 결론에 끝없이 다시 도달했어요 — 페르마 수로, 제타 함수로, 세는 일로, 위상수학으로, 심지어 \(\pi^2\)과 \(e\)의 무리수성으로. 메슈트로비치의 한 조사 논문은 그런 증명을 200개 가까이 모았죠. 그중 가장 아름다운 길들을 골라 걸어 봅니다.
모든 것의 시작. 소수가 \(p_1,\dots,p_k\) 유한개뿐이라고 합시다. 그 곱에 1을 더한 \(N=p_1p_2\cdots p_k+1\)을 보면 — \(N\)을 어느 \(p_i\)로 나눠도 나머지가 1입니다. 그러니 \(N\)의 소인수는 목록에 없는 새 소수여야 하고, 이는 "모든 소수를 적었다"는 가정과 모순. 따라서 소수는 무한히 많습니다.
유클리드가 "곱+1"로 새 소수를 불러냈다면, 골드바흐는 서로소인 무한 수열이라는 더 일반적인 아이디어를 씁니다. 페르마 수 \(F_n=2^{2^n}+1\)을 보죠. 다음 항등식이 열쇠예요:
$$ F_n-2 = 2^{2^n}-1 = \bigl(2^{2^{n-1}}+1\bigr)\bigl(2^{2^{n-1}}-1\bigr) = F_{n-1}(F_{n-1}-2). $$이걸 반복하면 \(F_n-2=F_0F_1\cdots F_{n-1}\). 즉 \(F_n\)은 자기보다 작은 모든 페르마 수의 곱에 2를 더한 수입니다. 페르마 수는 전부 홀수이므로, \(i\lt n\)이면 \(\gcd(F_n,F_i)\)는 \(\gcd(F_n,2)=1\)을 나눠 — 서로소! 그러니 각 \(F_n\)의 소인수를 하나씩 고르면 모두 다른 소수가 되어, 소수가 무수히 많습니다.
덤으로 — \(F_5=2^{32}+1\)은 페르마의 예상과 달리 소수가 아닙니다(오일러가 \(641\times6700417\)로 분해). 그래도 증명엔 흠집 하나 없죠. 이렇게 "쌍마다 서로소인 수열"을 만드는 방식은 변주가 많습니다.
위 증명들은 "유한하다고 치자"로 시작하는 귀류법입니다. 그런데 사이다크는 모순 없이, 곧장 무한히 많은 소수를 만들어 냅니다. 연속한 두 수 \(n\)과 \(n+1\)은 항상 서로소라는 사실 하나로요.
\(n_1=2\)에서 출발해 \(n_{j+1}=n_j(n_j+1)\)로 사슬을 만듭니다. \(n_j\)와 \(n_j+1\)은 서로소이므로 \(n_{j+1}=n_j(n_j+1)\)은 \(n_j\)보다 서로 다른 소인수를 적어도 하나 더 갖습니다. 그러니 \(n_1,n_2,n_3,\dots\)의 소인수 종류는 단계마다 늘어 — \(2 \to 6=2\cdot3 \to 42=2\cdot3\cdot7 \to 1806=2\cdot3\cdot7\cdot43 \to\cdots\) — 끝없이 새 소수가 등장합니다. \(\blacksquare\)
"~라면 모순"도 없이, 그냥 소수가 영원히 솟는 샘을 직접 보여 준 거죠. 가장 현대적이고 깔끔한 증명으로 꼽힙니다.
오일러는 소수를 무한급수로 끌고 들어왔습니다. 등비급수로 \(\frac{1}{1-p^{-s}}=1+p^{-s}+p^{-2s}+\cdots\)이니, 이걸 모든 소수에 대해 곱해 전개하면 — 소인수분해의 유일성 덕분에 — 임의의 자연수 \(n\)에 대한 \(n^{-s}\)가 정확히 한 번씩 나타납니다. 즉 오일러 곱:
$$ \zeta(s)=\sum_{n\ge1}\frac{1}{n^s}=\prod_{p\ \text{소수}}\frac{1}{1-p^{-s}}. $$그런데 \(s\to1^+\)에서 좌변은 조화급수 \(\sum 1/n=+\infty\)로 발산합니다. 만약 소수가 유한하다면 우변은 유한 개 인수의 곱이라 \(s\to1\)에서 유한한 값으로 수렴해야 하죠 — 모순. 해석학이 정수론의 문을 연 순간이고, 훗날 리만 제타 함수로 이어집니다.
에르되시는 도구 없이 세는 것만으로 끝냅니다. 소수가 \(p_1,\dots,p_k\) 유한개라고 합시다. 모든 자연수는 제곱수 × 제곱없는수로 \(n=a^2 b\)처럼 쪼개집니다(\(b\)는 같은 소수를 두 번 안 쓰는 수).
제곱없는 부분 \(b\)는 \(k\)개 소수의 부분집합이라 많아야 \(2^k\)가지. 제곱 부분은 \(a\le\sqrt{n}\le\sqrt{N}\)이라 많아야 \(\sqrt{N}\)가지. 그러니 \(N\) 이하의 모든 자연수의 개수가 \[ N \le 2^k\sqrt{N}\quad\Rightarrow\quad \sqrt{N}\le 2^k. \] 그런데 \(N\)은 얼마든지 크게 잡을 수 있으니(\(N>4^k\)), 모순. \(\blacksquare\)
같은 셈을 조금 더 밀면 4장의 \(\sum_p 1/p=\infty\)까지 나옵니다. 에르되시다운, 군더더기 없는 한 방이죠.
가장 의외의 길. 무한히 많은 소수를 무리수 하나로 증언하게 만듭니다.
오일러 곱에 \(s=2\)를 넣으면 \(\zeta(2)=\prod_p\frac{1}{1-p^{-2}}\). 소수가 유한하다면 우변은 유리수들의 유한 곱 = 유리수예요. 그런데 오일러가 푼 바젤 문제 \(\zeta(2)=\tfrac{\pi^2}{6}\)(1735)에, 르장드르가 보인 \(\pi^2\)의 무리수성(1794)을 합치면 — \(\zeta(2)\)는 무리수. 모순!
1943년 벨이 던진 문제. 뫼비우스 함수 \(\mu\)에 대해 \(|x|\lt1\)에서
$$ \prod_{n\ge1}(1-x^n)^{\mu(n)/n}=e^{-x} $$가 성립합니다(로그를 취하면 \(\sum_{d\mid N}\mu(d)=[N{=}1]\)로 깔끔히 \(-x\)가 나오죠). 여기 \(x=-\tfrac12\)을 넣고 제곱하면 우변은 \(e\). 그런데 소수가 유한하면 제곱없는수가 유한해 \(\mu(n)\ne0\)인 \(n\)도 유한 — 좌변은 유리수의 (유리수 거듭제곱) 유한 곱, 즉 대수적 수가 됩니다. 하지만 \(e\)는 초월수 (에르미트 1873)라 대수적일 수 없으니 모순. "소수 무한"이 \(e\)에 새겨져 있던 셈이죠.
투에는 순전히 세는 것으로 갑니다. 소수가 \(p_1,\dots,p_r\)뿐이라고 합시다. \(1\le m\le 2^n\)인 자연수 \(m\)은 \(m=p_1^{e_1}\cdots p_r^{e_r}\)로 유일하게 쪼개지고, \(p_i^{e_i}\le 2^n\)이라 각 지수는 \(e_i\le n\). 그러니 지수벡터 \((e_1,\dots,e_r)\)의 가짓수는 많아야 \((n+1)^r\)이고, 서로 다른 \(m\)은 서로 다른 벡터를 주므로
$$ 2^n \le (n+1)^r. $$이제 \(n=2k^2\)으로 잡으면 \(2k^2+1\lt 4^k\)이라 \((n+1)^k=(2k^2+1)^k\lt (4^k)^k=2^{2k^2}=2^n\). 만약 \(r\le k\)라면 \(2^n\le(n+1)^r\le(n+1)^k\lt2^n\) — 모순! 그러니 어떤 \(k\)에 대해서도 \(r\gt k\), 즉 소수는 무한히 많습니다.
가장 기묘하고 사랑받는 증명. 정수 \(\mathbb{Z}\) 위에 등차수열 \(U_{a,b}=\{a+bk:k\in\mathbb{Z}\}\)들과 그 합집합을 열린집합으로 삼는 위상을 줍니다(두 열린집합의 교집합도 열린집합임을 확인할 수 있어요).
\(\pm1\)을 뺀 모든 정수는 어떤 소수의 배수이므로
$$ \mathbb{Z}\setminus\{-1,1\}=\bigcup_{p\ \text{소수}} U_{0,p}. $$소수가 유한하다면 우변은 닫힌집합의 유한 합집합이라 닫힌집합 → 여집합 \(\{-1,1\}\)은 열린집합이어야 합니다. 그런데 두 점짜리 유한집합이 열린집합일 수는 없죠(열린집합은 무한!). 모순. 위상수학이 소수의 무한성을 증언하는, 단 몇 줄의 마술입니다.
21세기에도 새 증명이 나옵니다. 메슈트로비치의 조사 논문이 200개 가까이 모을 만큼, 이 우물은 마르지 않아요.
유클리드의 곱셈, 골드바흐의 페르마 수, 사이다크의 사슬, 오일러의 발산, 에르되시의 세기, \(\pi^2\)과 \(e\)의 무리수성, 투에의 비둘기집, 퓌르스텐베르크의 위상, 반데르바르덴과 사인 곱까지 — 모두 "소수는 무한히 많다"는 단 하나의 진실로 흘러듭니다. 왜 이렇게 많은 길을 낼까요?
증명은 "참임을 확인하는 일"이 아니라 "왜 참인지 이해하는 서로 다른 방식"이기 때문입니다. 길마다 소수가 해석학·조합론·위상수학·무리수와 맺은 새로운 인연이 드러나죠. 소수가 무한하다는 사실은 하나지만, 그리로 가는 길은 — 소수만큼이나 — 무한합니다.