소수⁠(prime number)⁠를 세는 사람들

소수는 제멋대로 흩어져 있는 것 같다. 그런데 멀리서 세어 보면 로그가 보인다.

점선이 그어진 숫자는 좌우로 끌 수 있고(키보드 ←/→도 됩니다), 밑줄 친 말에 마우스를 올리면 그림에서 그 부분이 빛납니다. 그림 속 점 가운데 일부는 직접 끌 수 있습니다. 색이 칠해진 선택지는 눌러서 바꿀 수 있습니다. 휴대폰에서는 마우스를 올리는 대신 누르면 됩니다.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, … 1보다 큰 자연수⁠(natural number)⁠ 가운데 1과 자기 자신으로만 나누어떨어지는 수, 소수입니다. 늘어놓고 보면 규칙이 잘 보이지 않습니다. 2와 3은 바로 붙어 있는데 89 다음 소수는 97이어서, 그 사이의 일곱 수는 모두 합성수입니다. 합성수⁠(composite number)⁠란 더 작은 수들의 곱으로 쪼개지는 수입니다(1은 소수로도 합성수로도 치지 않습니다). 1부터 100 사이에는 소수가 25개 있지만, 1000부터 1100 사이에는 16개뿐입니다. 100만 아래에서 가장 긴 빈틈은 492,113과 492,227 사이로, 113개의 수가 연달아 합성수입니다.

다음 소수가 어디에 나올지 알려 주는 간단한 공식은 지금도 없습니다. 그렇다면 소수에는 아무 법칙도 없는 걸까요? 이 글은 이 질문을 2,000년 넘게 붙든 사람들의 이야기입니다. 답은 뜻밖의 방향에서 왔습니다. 소수를 하나씩 쫓지 않고 세어 보면, 그 개수는 매끄러운 법칙을 따릅니다. 그리고 그 법칙에는 원주율⁠(pi)⁠도 제곱근도 아닌 자연로그⁠(natural logarithm)⁠가 들어 있습니다. 로그가 무엇인지 잊었어도 괜찮습니다. 필요한 만큼은 4절에서 처음부터 다시 설명합니다.

길잡이를 먼저 적어 둡니다. 1–2절은 소수가 끝없이 있다는 것과 소수를 찾는 법, 3–4절은 소수를 한꺼번에 다루는 오일러의 공식, 5–6절은 소수의 개수를 어림하는 법칙, 7절은 그 법칙이 증명되기까지와 아직 남은 질문(리만 가설⁠, Riemann hypothesis⁠), 8–9절은 수학 밖으로 이어지는 이야기입니다.

1 · 곱셈의 원자소수는 끝이 없다

이 절의 물음은 둘입니다. 소수는 왜 자연수 가운데 특별한 대접을 받을까? 그리고 소수는 어디선가 끝날까, 아니면 끝없이 나올까?

첫 물음부터 봅시다. 12 = 2 × 2 × 3, 360 = 2 × 2 × 2 × 3 × 3 × 5처럼 1보다 큰 자연수는 모두 소수들의 곱으로 쪼개집니다(7처럼 소수 자신은 소수 하나짜리 곱으로 칩니다). 쪼개는 방법은 순서만 빼면 하나뿐입니다. 12를 3 × 2 × 2로 적어도 같은 분해로 칩니다. 이렇게 소수의 곱으로 쪼개는 일을 소인수분해⁠(prime factorization)⁠라 하고, 분해가 늘 있고 하나뿐이라는 사실을 산술의 기본정리⁠(fundamental theorem of arithmetic)⁠라고 부릅니다.

1을 소수에서 빼는 까닭도 여기 있습니다. 1을 소수로 치면 12 = 2 × 2 × 3 = 1 × 2 × 2 × 3 = 1 × 1 × 2 × 2 × 3처럼 1을 몇 개든 끼워 넣을 수 있어서 쪼개는 방법이 하나가 아니게 됩니다. 정리하면, 소수는 곱셈의 원자이고, 모든 자연수는 이 원자들로 지은 분자인 셈입니다.

쪼개는 방법이 하나뿐이라는 증명의 핵심은 "소수 $p$가 곱 $ab$를 나누면 $a$나 $b$ 중 하나를 나눈다"는 성질입니다($ab$는 a × b를 줄여 쓴 것입니다). 예를 들어 소수 3은 4 × 15 = 60을 나누고, 실제로 15를 나눕니다. 1보다 큰 수 가운데 이 성질은 소수에만 있습니다. 소수가 아닌 6은 4 × 9 = 36을 나누지만 4도 9도 나누지 못합니다. 6의 두 원자 2와 3이 4와 9에 나뉘어 들어 있기 때문입니다. 소수는 더 쪼개지지 않으니 이렇게 나뉘어 숨을 수 없습니다.

유클리드는 『원론』 7권에서 이 성질을 증명했고, 같은 권의 첫머리에는 두 수의 최대공약수⁠(greatest common divisor)⁠를 나눗셈의 되풀이로 구하는 방법, 곧 오늘날의 유클리드 호제법⁠(Euclidean algorithm)⁠이 실려 있습니다. 요즘 교과서는 이 호제법으로 그 성질을 증명합니다.

이제 둘째 물음입니다. 원자의 종류는 몇 가지일까요? 소수가 어느 크기에서 끝난다면, 모든 자연수는 유한한 몇 개의 원자로만 지어지는 셈입니다. 유클리드는 『원론』 9권에서 짧게 답합니다.

소수는 주어진 어떤 개수의 소수보다도 많다.— 유클리드, 『원론』 9권 명제 20 (기원전 300년 무렵)

논증은 이렇습니다. 누군가 소수를 모두 모았다며 목록을 내밀었다고 합시다. 목록이 2, 3, 5라고 해 봅시다. 목록의 소수를 전부 곱하고 1을 더하면 2 × 3 × 5 + 1 = 31입니다.

31은 목록의 어느 소수로 나누어도 1이 남습니다. 31 = 2 × 15 + 1 = 3 × 10 + 1 = 5 × 6 + 1이기 때문입니다. 까닭은 간단합니다. 30은 목록의 소수를 모두 곱한 수라서 2로도 3으로도 5로도 나누어떨어지고, 거기에 1을 더했으니 나머지가 1입니다. 이렇게 '나눈 나머지⁠(remainder)⁠'만 보고 계산하는 방법을 모듈러 연산⁠(modular arithmetic)⁠이라 부릅니다.

이제 31을 소인수분해합니다(31은 그 자체로 소수이니 분해는 31 하나입니다). 분해에 나오는 소수를 q라고 합시다. q가 목록에 있었다면 q는 31을 나누면서 동시에 31을 나눌 때 1을 남겨야 하니 모순입니다. 그러니 q는 목록에 없던 소수입니다. 목록이 무엇이든 같은 논증이 됩니다. 곱하고 1을 더한 수는 목록의 어느 소수로도 나누어떨어지지 않고, 그 수의 소인수는 목록 밖에 있습니다.

처음 $k =$ 개의 소수로 직접 해 봅시다(k는 목록에 넣을 소수의 개수입니다). 숫자를 끌어 k를 바꾸거나 버튼을 누르세요. 아래 식의 왼쪽이 목록의 곱에 1을 더한 수이고, 오른쪽이 그 수의 소인수분해입니다. 볼 것은 하나입니다. 오른쪽에 나온 소수가 매번 목록의 마지막 소수보다 큰가. ▶ k를 1부터 12까지

흔히 이 '곱하고 1을 더한 수'가 늘 소수라고 생각하지만, 그렇지 않습니다. $k = 6$이면 2 × 3 × 5 × 7 × 11 × 13 + 1 = 30,031이고, 30,031 = 59 × 509입니다. 중요한 것은 어느 경우든 목록 밖의 소수가 튀어나온다는 점입니다. 59도 509도 목록의 마지막 소수 13보다 큽니다. 어떤 유한한 목록도 완전할 수 없으니 소수는 끝이 없습니다.

소수는 끝이 없다는 것을 알았으니, 이번에는 소수 사이를 봅시다. 소수 사이의 빈틈은 얼마든지 길어질 수 있습니다. 먼저 기호 하나를 읽어 둡니다. $n! = 1 \times 2 \times \cdots \times n$은 'n 팩토리얼⁠(factorial)⁠'이라 읽고, 1부터 n까지를 모두 곱한 수입니다. 예를 들어 $5! = 1 \times 2 \times 3 \times 4 \times 5 = 120$입니다.

$n!$은 2부터 $n$까지의 모든 수로 나누어떨어집니다. 곱 안에 그 수들이 모두 들어 있기 때문입니다. 그래서 $n! + 2,\ n! + 3,\ \dots,\ n! + n$은 각각 2, 3, …, $n$으로 나누어떨어지고, 연달아 $n-1$개의 합성수가 됩니다. 예를 들어 $n! + 3$은 3으로 나누어떨어지는 수 $n!$에 3을 더했으니 역시 3으로 나누어떨어집니다. $n = 5$이면 122, 123, 124, 125입니다. 차례로 122 = 2 × 61, 123 = 3 × 41, 124 = 4 × 31, 125 = 5 × 25이니 네 수 모두 합성수입니다. n을 키우면 빈틈은 원하는 만큼 길어집니다.

정리하면, 소수는 끝없이 나오지만 평균적으로는 점점 드물어집니다(1–100에 25개, 1000–1100에 16개). 그렇다면 얼마나 드물어질까요? 이 질문이 이 글 전체를 끌고 갑니다.

유클리드의 문장을 다시 보면 "소수는 무한히 많다"가 아니라 "주어진 어떤 개수보다도 많다"입니다. 아리스토텔레스는 『자연학』에서 무한을 끝없이 더 늘릴 수 있는 가능성으로만 인정하고, 다 모인 무한은 받아들이지 않았습니다. 유클리드의 증명도 완성된 무한 집합⁠(set)⁠을 다루지 않습니다. 어떤 유한한 목록이 오든 하나를 더 만드는 절차를 보여 줄 뿐입니다. 무한을 하나의 크기로 다루게 된 것은 19세기의 일입니다(「무한에도 크기가 있다」).

그런데 "쪼개는 방법이 하나뿐"이라는 문장 자체를 일반적인 정리로 적고 증명한 사람은 유클리드가 아닙니다. 『원론』에는 재료가 있습니다. 위의 성질인 7권 30번 명제와 9권 14번 명제입니다. 하지만 모든 자연수의 분해가 하나뿐이라는 명제는 없습니다. 그 사이에 이 명제에 다가간 사람이 있습니다. 9세기 바그다드의 지혜의 집 시대에 타비트 이븐 쿠라는 220과 284처럼 자기를 뺀 약수⁠(divisor)⁠의 합이 서로 상대가 되는 수의 쌍(친화수⁠, amicable numbers⁠)을 만드는 규칙을 찾았습니다. 220의 약수 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110을 더하면 284이고, 284의 약수 1, 2, 4, 71, 142를 더하면 220입니다. 1300년 무렵 페르시아 타브리즈의 학자 카말 앗딘 알파리시는 이 규칙을 새로 증명하려고, 약수의 합을 소인수분해로 계산하는 길을 택했습니다. 그래서 모든 수가 소수의 거듭제곱의 곱으로 쪼개진다는 것을 명제로 적고 증명했습니다. 다만 쪼개는 방법이 하나뿐이라는 부분까지 증명했는지는 수학사가들 사이에 의견이 갈립니다. 유일성까지 분명히 적고 증명한 첫 기록은 1801년 가우스의 『산술 연구』(16항)입니다. 너무 당연해 보이는 사실까지 증명해 둔 이 조심성이 옳았다는 것은 46년 뒤 파리에서 드러났습니다. 정수⁠(integer)⁠보다 넓은 수의 세계에서는 분해가 여러 가지일 수 있습니다. 이를 모른 채 페르마의 마지막 정리⁠(Fermat's Last Theorem)⁠를 증명했다고 발표한 일, 그리고 그 일을 수습하다 '아이디얼⁠(ideal)⁠'이라는 개념이 태어난 이야기는 「틀린 증명이 만든 수학」 2–3절에 있습니다.

그리스인들은 증명이 나오기 전부터 수에 관심을 두었습니다. 기원전 6세기 남이탈리아 크로톤의 피타고라스 학파는 수의 원리를 만물의 원리로 여겼다고 아리스토텔레스가 전합니다. 홀수와 짝수, 자기를 뺀 약수의 합이 자기와 같은 완전수(6 = 1 + 2 + 3) 같은 구분에는 종교적 의미가 얹혀 있었습니다. 『원론』은 이 전통을 정의에서 출발해 한 단계씩 증명하는 체계로 바꾸었습니다.

『원론』을 플라톤과 잇는 전언도 있습니다. 5세기 아테네의 철학자 프로클로스는 유클리드를 플라톤주의자로 소개했습니다. 플라톤은 『국가』 7권에서 수의 공부를 장사꾼처럼 사고팔기 위해서가 아니라 전쟁에 쓰고 영혼을 참된 것으로 돌리기 위해 하라고 권했습니다. 쓸모와 아름다움 사이의 이 긴장은 20세기까지 이어집니다(8절).

2 · 에라토스테네스의 체지우고 남은 것

이 절의 물음은 이것입니다. 어떤 범위의 소수를 하나도 빠짐없이 찾으려면 어떻게 할까? 수마다 일일이 나눠 보지 않고, 합성수를 한꺼번에 걸러 내는 방법이 있습니다.

그 방법은 기원전 3세기 알렉산드리아 도서관장 에라토스테네스의 이름으로 전해집니다. 지구의 둘레를 잰 것으로 유명한 바로 그 사람입니다. 에라토스테네스 자신의 수학 저작은 남아 있지 않습니다. 이 방법은 서기 100년 무렵 그리스의 수학자 니코마코스가 쓴 『산술 입문』에 그의 이름과 함께 실려 전해졌습니다.

방법은 간단합니다. 2부터 시작해 아직 지워지지 않은 가장 작은 수를 소수로 확정하고, 그 수의 배수⁠(multiple)⁠를 모두 지웁니다. 이것을 되풀이합니다. 2부터 30까지로 해 봅시다. 2를 소수로 확정하고 4, 6, 8, …, 30을 지웁니다. 남은 수 가운데 가장 작은 3을 확정하고 9, 15, 21, 27을 지웁니다(6, 12처럼 이미 지운 수는 건너뜁니다). 다음은 5이고 25를 지웁니다. 다음 7의 배수 가운데 아직 남은 것은 49부터인데 30을 넘으니 더 지울 것이 없습니다. 남은 2, 3, 5, 7, 11, 13, 17, 19, 23, 29가 30 이하의 소수 전부입니다. 지워지지 않고 남은 수는 자기보다 작은 어떤 소수의 배수도 아니니 소수입니다.

아래 그림은 같은 일을 1부터 180까지 합니다. 그림 아래의 '한 소수 체질하기' 버튼을 여러 번 눌러 보세요. 볼 것은 두 가지입니다. 한 번 누를 때마다 어떤 수들이 흐려지는지, 그리고 소수로 확정된 노란 칸이 어디까지 늘어나는지.

다음에 체질할 소수: . ▶ 한 소수 체질하기 ▶▶ 끝까지 처음부터 지금까지 체질한 소수는 개입니다.

체질할 때마다 초록 고리가 다음 소수 $p$를, 주황 고리가 그 제곱 $p^2$(p × p)을 가리킵니다. 눌러 보면 주황 고리보다 앞에 살아남은 수가 모두 노랗게, 곧 소수로 확정됩니다. 예를 들어 2와 3으로 체질한 뒤 다음 소수는 5이고 주황 고리는 25에 있습니다. 25보다 작은 수 가운데 2, 3 말고 살아남은 것은 5, 7, 11, 13, 17, 19, 23이고, 모두 소수입니다.

왜 그럴까요? 25보다 작은 합성수, 예를 들어 21 = 3 × 7을 봅시다. 두 약수 가운데 작은 쪽 3은 5보다 작습니다. 두 약수가 모두 5 이상이면 곱이 5 × 5 = 25 이상이 되어 버리기 때문입니다. 그러니 21은 5보다 작은 소수 3의 배수로 이미 지워졌습니다.

일반적으로 적으면 이렇습니다. $\sqrt n$('n의 제곱근')은 제곱해서 n이 되는 양수입니다. 합성수 $n = ab$($a, b \gt 1$)에서 두 약수가 모두 $\sqrt n$보다 크면 곱이 $n$보다 커지니, 합성수에는 1보다 크고 $\sqrt n$ 이하인 약수가, 따라서 그런 소인수가 반드시 있습니다(그 약수를 소인수분해해서 나오는 소수는 약수보다 크지 않습니다). 그래서 $p^2$보다 작은 합성수는 $p$보다 작은 소수의 배수로 이미 지워졌습니다.

이 덕분에 체질은 일찍 끝납니다. 180까지라면 13까지만 체질하면 끝납니다($13^2 = 169$, $17^2 = 289$). 17로 한 번 더 체질해 보세요. 새로 지워지는 수가 하나도 없습니다. 17의 배수 가운데 180 이하인 34, 51, …, 170은 모두 17보다 작은 소인수(2, 3, 5, 7)가 있어서 이미 지워졌기 때문입니다.

왜 몇몇 줄에만 모일까요? 줄이 곧 나머지이기 때문입니다. 6개씩 적었다면 한 줄에는 1, 7, 13, 19, …처럼 6씩 차이 나는 수가 놓이고, 이 수들은 6으로 나눈 나머지가 모두 같습니다. 나머지가 4인 줄을 봅시다. 4, 10, 16, 22, …는 모두 짝수이니 2 말고는 소수가 없고, 2는 이 줄에 없습니다. 나머지가 3인 줄의 3, 9, 15, 21, …은 모두 3의 배수이니 소수는 3 하나뿐입니다. 나머지 0, 2인 줄도 마찬가지로 6의 배수, 짝수뿐입니다. 5 이상의 소수가 살 수 있는 줄은 나머지 1과 5인 두 줄만 남습니다.

일반적으로 적으면 이렇습니다. 한 열에 $w$개씩 적으면 같은 줄의 수들은 $w$로 나눈 나머지가 같습니다. 나머지와 $w$에 1보다 큰 공약수 $d$가 있으면(6개씩이면 나머지 0, 2, 3, 4), 그 줄의 수는 모두 $d$의 배수입니다. 그러니 이런 줄에 들 수 있는 소수는 많아야 하나, $d$가 소수일 때의 $d$ 자신뿐입니다(6개씩이면 나머지 2 줄의 2와 나머지 3 줄의 3).

남는 줄의 개수에는 이름이 있습니다. $w$보다 큰 소수가 살 수 있는 줄의 개수는 $w$와 서로소⁠(coprime)⁠인(1 말고는 공약수가 없는) 나머지의 개수, 곧 오일러 피 함수⁠(Euler's totient function)⁠ $\varphi(w)$입니다('피 w'라 읽습니다). 6과 서로소인 나머지는 1과 5이니 φ(6) = 2이고, 10과 서로소인 나머지는 1, 3, 7, 9이니 φ(10) = 4입니다. 그림에서 10개씩 적으면 소수가 네 줄에 모이는 것, 곧 2와 5를 빼면 모든 소수의 끝자리가 1, 3, 7, 9인 것이 이 때문입니다.

남은 줄들에는 소수가 얼마나 들어 있을까요? 1837년 디리클레는 이런 줄 하나하나에 소수가 끝없이 나온다는 것을 증명했습니다. 1896년에는 드 라 발레 푸생이 더 나아가, 길게 보면 각 줄이 소수를 똑같이 $1/\varphi(w)$씩 나눠 가진다는 것을 보였습니다. 끝자리로 말하면, 충분히 멀리까지 세었을 때 끝자리가 1, 3, 7, 9인 소수가 각각 전체의 약 4분의 1씩입니다.

이제 체로 남는 수의 개수를 계산해 봅시다. 180 이하에서 2, 3, 5 어느 것으로도 나누어지지 않는 수는 몇 개일까요? 이런 셈에 쓰는 방법이 포함배제 원리⁠(inclusion–exclusion principle)⁠입니다. 먼저 식을 보고, 한 항씩 읽겠습니다.

180 이하에서 2의 배수는 180/2 = 90개, 3의 배수는 60개, 5의 배수는 36개입니다. 이것을 모두 빼면 180 − 186이 되어 너무 많이 뺍니다. 6의 배수(2와 3의 공배수)는 2의 배수로 한 번, 3의 배수로 또 한 번, 두 번 빠졌기 때문입니다. 그래서 두 번 빠진 6, 10, 15의 배수 30 + 18 + 12 = 60개를 한 번씩 되돌려 놓습니다. 그러면 30의 배수는 세 번 빠지고 세 번 돌아와 한 번도 빠지지 않은 셈이 되니, 180/30 = 6개를 마지막으로 뺍니다. 180 − 186 + 60 − 6 = 48입니다.

같은 48을 곱으로도 얻습니다. 180개 가운데 2의 배수가 아닌 것은 절반인 90개, 그 가운데 3의 배수가 아닌 것은 3분의 2인 60개, 다시 그 가운데 5의 배수가 아닌 것은 5분의 4인 48개입니다. 식의 오른쪽 끝, $180 \cdot \tfrac{1}{2} \cdot \tfrac{2}{3} \cdot \tfrac{4}{5}$가 이 계산입니다.

이 곱을 눈여겨보세요. 소수 $p$로 체질할 때마다 남은 수의 약 $1 - \tfrac1p$만 살아남습니다. 소수 하나하나가 독립적으로 제 몫을 걸러 내는 것처럼 보입니다. 이 "소수마다 곱하기"라는 생각이 다음 절의 주인공입니다.

흔히 이 곱으로 소수의 개수도 정확히 어림할 수 있다고 생각하지만, 그렇지 않습니다. 180이 30의 배수여서 이 계산이 딱 맞았을 뿐, 체질할 소수가 많아지면 나누어떨어지지 않는 몫의 오차가 쌓입니다. 실제로 $\sqrt x$ 이하의 모든 소수로 이 곱을 만들어 $x$에 곱하는 식으로 소수의 개수를 어림하면, $x$가 커질수록 참값과의 비가 1이 아니라 $2e^{-\gamma} \approx 1.123$으로 다가갑니다. 여기서 e ≈ 2.718은 4절에서 볼 자연로그의 밑이고, $\gamma \approx 0.5772$는 오일러 상수⁠(Euler–Mascheroni constant)⁠라는 고정된 수입니다. 어림이 12%쯤 넘치는 것입니다.

정리하면, 체는 소수를 찾는 데는 훌륭하지만, 소수가 몇 개인지 말해 주는 법칙은 주지 않습니다. 그래도 "소수마다 하나씩 곱한다"는 생각은 남습니다.

디리클레의 증명에는 파동의 수학이 숨어 있습니다. 그는 1820년대 중반 파리에 머물며 푸리에의 곁을 드나들었고, 1829년에는 푸리에 급수(복잡한 파형을 사인파⁠(sinusoid)⁠들의 합으로 쓰는 방법)가 수렴⁠(convergence)⁠하는 조건을 처음으로 엄밀하게 증명했습니다(「원에서 파동으로」). 1837년 그가 풀어야 했던 문제는 한 줄의 소수만 따로 세는 일이었습니다. 3절에서 볼 오일러의 곱은 모든 소수를 한꺼번에 셉니다. 디리클레는 이 곱의 소수 $p$ 자리마다 $p$가 놓인 줄에 따라 정해지는 1의 거듭제곱근⁠(roots of unity)⁠을 붙여, 이런 곱을 여러 개 만들었습니다. 1의 거듭제곱근이란 몇 번 거듭제곱하면 1이 되는 수로, 시계바늘처럼 원 위의 눈금에 놓이는 복소수입니다. 그것들을 알맞게 더하면 다른 줄의 기여는 서로 지워지고 한 줄만 남습니다. 소리를 사인파로 쪼갠 뒤 원하는 진동수⁠(frequency)⁠만 골라내는 것과 같은 요령을 나머지의 시계 위에서 쓴 것입니다. 오늘날 이 함수⁠(function)⁠들을 디리클레 지표라 부르고, 이 논문을 해석적 정수론(수를 세는 문제를 극한⁠(limit)⁠과 무한급수⁠(infinite series)⁠의 도구로 푸는 분야)의 출발점으로 꼽습니다.

체가 우리에게 온 길도 따라가 볼 만합니다. 먼저 사람부터 봅시다. 에라토스테네스는 오늘날 리비아 동부인 키레네에서 태어나 아테네에서 공부했습니다. 기원전 245년 무렵에는 이집트를 다스리던 프톨레마이오스 왕조의 왕 프톨레마이오스 3세의 부름을 받아 알렉산드리아 도서관을 맡았습니다. 지리학, 역사 속 사건⁠(event)⁠의 연도를 정하는 연대학, 시까지 두루 손댄 그는 모든 분야에서 둘째라는 뜻의 '베타'로 불렸다고 전합니다(지구를 잰 이야기는 「원에서 파동으로」에 있습니다).

방법은 책을 따라 옮겨 다녔습니다. 체를 기록한 니코마코스는 로마 속주 도시 게라사, 곧 오늘날 요르단의 제라시 사람입니다. 500년 무렵 로마의 철학자 보에티우스가 그의 책을 라틴어로 옮겨 다듬었고, 이 라틴어 책이 중세 유럽 학교의 산술 교과서가 되었습니다. 『원론』은 다른 길을 걸었습니다. 9세기 바그다드에서 아랍어로, 12세기 톨레도 등지에서 다시 라틴어로 옮겨져 유럽에 돌아왔습니다.

노란 선은 에라토스테네스가 알렉산드리아로 온 길, 주황 선은 체와 『원론』이 책으로 옮겨 간 길입니다. 장소를 누르면 그곳에서 일어난 일이 나타납니다.

3 · 오일러의 곱모든 자연수를 소수로 다시 쓰기

이 절의 물음은 이것입니다. 소수가 몇 개인지 세려면, 소수 하나하나가 아니라 소수 전체를 한 번에 담는 공식이 필요합니다. 그런 공식이 있을까? 오일러가 찾은 답은 '자연수 전체에 대한 합'을 '소수 전체에 대한 곱'으로 바꿔 쓰는 공식이었습니다. 그 공식이 나온 곳부터 봅시다.

소수의 개수를 세는 일의 첫 돌파구는 소수와 전혀 상관없어 보이는 문제에서 나왔습니다. 1650년 이탈리아 볼로냐의 수학자 피에트로 멩골리는 제곱수⁠(perfect square)⁠의 역수⁠(inverse)⁠를 끝없이 더한 값을 물었습니다. 역수란 1을 그 수로 나눈 것이고(4의 역수는 1/4), 제곱수는 1, 4, 9, 16처럼 같은 수를 두 번 곱한 수입니다.

'끝없이 더한 값'은 더할수록 다가가는 값을 뜻합니다. 차례로 더하면 1, 1.25, 1.361…, 1.424…로 조금씩 커지지만, 커지는 폭이 빠르게 줄어 어떤 값에 다가갑니다. 합이 2보다 작다는 것은 쉽게 보입니다. $\tfrac14 \lt 1 - \tfrac12$, $\tfrac19 \lt \tfrac12 - \tfrac13$, $\tfrac1{16} \lt \tfrac13 - \tfrac14$, …처럼 첫 항 1 뒤의 각 항을 조금 더 큰 차이로 바꾸면, 바꾼 항들을 더할 때 중간이 서로 지워져 합이 1을 넘지 못하기 때문입니다. 그래서 전체는 1 + 1 = 2보다 작습니다.

그러나 정확한 값은 아무도 몰랐습니다. 바젤의 야코프 베르누이도 이 문제를 널리 알리며 도움을 청했을 만큼 어려웠고, 바젤 문제⁠(Basel problem)⁠라는 이름도 여기서 붙었습니다. 1734년 무렵 바젤 출신의 젊은 오일러가 답을 찾아 이듬해 발표했습니다. 답은 $\pi^2/6$, 곧 약 1.6449였습니다. 원주율 π가 원과 아무 상관 없어 보이는 합에서 나온 것입니다.

1737년 오일러는 이 합을 소수와 이었습니다. 재료는 등비급수⁠(geometric series)⁠, 곧 일정한 비율로 줄어드는 수들의 끝없는 합입니다. 가장 쉬운 예는 $1 + \tfrac12 + \tfrac14 + \tfrac18 + \cdots = 2$입니다. 일반적으로 비율이 r(−1과 1 사이)이면 $1 + r + r^2 + \cdots = \tfrac{1}{1-r}$이고, r = 1/2이면 1/(1 − 1/2) = 2입니다. 오일러는 소수 하나마다 이런 등비급수를 하나씩 씁니다.

기호부터 읽겠습니다. $2^{-s}$는 $1/2^s$와 같은 뜻입니다. 왼쪽 식은 비율이 $r = 1/2^s$인 등비급수입니다. 여기서 $s$는 1보다 큰 수이면 무엇이든 됩니다. $s = 2$로 두면 왼쪽 식은 $1 + \tfrac14 + \tfrac1{16} + \cdots = \tfrac{1}{1 - 1/4} = \tfrac43$이고, 분모에 제곱수만 나오니 바젤 문제의 합과 이어집니다.

이제 두 식을 곱해서 전개합니다. 왼쪽 괄호에서 한 항, 오른쪽 괄호에서 한 항을 골라 곱하는 모든 방법을 더하는 것입니다. 예를 들어 $\tfrac{1}{4^s}$과 $\tfrac{1}{3^s}$을 고르면 $\tfrac{1}{12^s}$이 나옵니다. 12 = 4 × 3 = 2 × 2 × 3이니까요. 그러면 $1/(2^a 3^b)^s$ 꼴의 항이 하나씩 나옵니다. 2와 3만으로 만들 수 있는 수 1, 2, 3, 4, 6, 8, 9, 12, …가 정확히 한 번씩 등장합니다. 12를 만드는 방법이 '2를 두 번, 3을 한 번' 하나뿐이니 $\tfrac{1}{12^s}$도 한 번만 나옵니다.

소수를 하나씩 더 곱해 넣을수록 만들 수 있는 수가 늘어나고, 모든 소수를 곱하면 소인수분해가 하나뿐이라는 사실 덕분에 모든 자연수가 정확히 한 번씩 나타납니다. 모든 자연수 n에 대해 $1/n^s$를 더한 합이 되는 것입니다. 이 결론을 식으로 적기 전에 기호 두 개를 읽어 둡니다. $\sum$(시그마)는 '모두 더하라', $\prod$(대문자 파이)는 $\sum$의 곱셈판으로 '모두 곱하라'는 기호입니다. 아래 식 왼쪽은 "n = 1부터 끝없이 $1/n^s$를 더하라", 오른쪽은 "모든 소수 p에 대해 $\tfrac{1}{1-p^{-s}}$를 곱하라"고 읽습니다.

왼쪽은 자연수 전체에 대한 합이고 오른쪽은 소수 전체에 대한 곱입니다. 산술의 기본정리를 해석학⁠(mathematical analysis)⁠, 곧 극한과 무한급수를 다루는 분야의 공식 한 줄로 옮긴 것입니다. 왼쪽을 오늘날 제타 함수⁠(zeta function)⁠ $\zeta(s)$라고 부릅니다('제타 s'라 읽습니다). s = 2일 때의 값 ζ(2)가 바젤 문제의 답 π²/6입니다.

직접 확인해 봅시다. 곱에 넣을 소수를 처음 개($P =$ 까지)로 정하고, 지수는 $s =$ 에서 시작합니다. 소수를 하나씩 늘려 가며 두 가지를 보세요. 왼쪽 그림에서 보라 칸, 곧 넣은 소수들만으로 만들 수 있는 수가 어떻게 늘어나는지. 오른쪽 그림에서 합(파랑)과 곱(보라)이 같은 점선으로 다가가는지. ▶ 소수를 하나씩 넣기

왼쪽 그림에 불이 들어온 수는 개입니다. 곱은 이 수들 전부의 $1/n^s$를, 120을 넘어서까지 끝없이 더한 것과 같습니다. $s = 2$에서는 합과 곱이 모두 π²/6 ≈ 1.6449로 다가갑니다. 곱 쪽이 조금 더 빨리 붙는데, 곱은 $P$보다 큰 수(64, 96처럼 작은 소수만으로 된 수)까지 미리 품고 있기 때문입니다.

이제 $s$를 1까지 끌어내려 보세요. 목표값이 위로 치솟다가 $s = 1$에서 사라집니다. s = 1이면 왼쪽 합은 $1 + \tfrac12 + \tfrac13 + \cdots$, 곧 조화급수⁠(harmonic series)⁠가 되는데, 이 합은 어떤 값에도 다가가지 않고 끝없이 커지기 때문입니다.

조화급수가 끝없이 커지는 까닭은 항을 묶어 보면 보입니다. $\tfrac13 + \tfrac14$는 $\tfrac14 + \tfrac14 = \tfrac12$보다 크고, $\tfrac15 + \tfrac16 + \tfrac17 + \tfrac18$은 $\tfrac18$ 네 개, 곧 $\tfrac12$보다 큽니다. 다음 여덟 항(1/9부터 1/16까지)도 1/2보다 큽니다. 이렇게 1/2보다 큰 묶음을 끝없이 만들 수 있으니 합에는 한계가 없습니다. 흔히 더하는 수가 0으로 줄어들면 합도 어떤 값에 멈추리라 생각하지만, 조화급수가 그 반례입니다.

여기서 오일러는 소수가 무한하다는 새 증명을 얻었습니다. 소수가 유한하다면 오른쪽 곱은 $\tfrac{1}{1-1/2} \times \tfrac{1}{1-1/3} \times \cdots$처럼 유한한 수들의 유한한 곱이니 유한한 값입니다. 그런데 이 곱을 전개하면 모든 자연수가 소수들의 곱이니 1, 1/2, 1/3, …이 빠짐없이 나오고, 그래서 곱은 조화급수를 어디까지 더한 값보다도 큽니다. 조화급수는 끝없이 커지니 유한한 값일 수 없습니다. 그러니 소수는 무한해야 합니다. 유클리드와 달리 이 증명은 셈으로 만든 증명입니다. 그리고 셈의 크기까지 알려 줍니다. 그것이 다음 절입니다.

정리하면, 오일러의 곱은 "모든 자연수는 소수들의 곱으로 한 가지 방법으로만 쪼개진다"는 사실을 "자연수 전체의 합 = 소수 전체의 곱"이라는 등식으로 바꿔 적은 것입니다. 이제 소수 전체를 한 식으로 다룰 수 있게 되었습니다.

같은 곱은 확률⁠(probability)⁠에서도 나타납니다. 자연수 전체에서 '고르게' 하나를 뽑을 수는 없으니, 1부터 $N$까지에서 두 수를 따로따로 고르게 뽑는다고 합시다. $N$이 $p$의 배수이면 둘 다 $p$의 배수일 확률은 정확히 $1/p^2$이고(p = 2이면 둘 다 짝수일 확률 1/2 × 1/2 = 1/4), 서로 다른 소수들에 대한 이 사건들은 서로 독립입니다($N$이 그 소수들의 곱의 배수일 때). 독립⁠(independence)⁠이란 두 수가 모두 2의 배수인지 아닌지가 둘 다 3의 배수일 확률을 바꾸지 않는다는 뜻입니다. 그래서 어느 소수도 둘을 함께 나누지 않을 확률, 곧 두 수의 최대공약수가 1일 확률은 $N$이 커질수록 $\prod_p (1 - p^{-2}) = 1/\zeta(2) = 6/\pi^2 \approx 0.608$로 다가갑니다(모든 소수를 한꺼번에 다루는 극한은 따로 증명이 필요하지만, 결과는 이 값입니다). "두 정수가 서로소일 확률"이란 이 극한값을 뜻합니다. 원과 아무 상관 없는 질문의 답에 $\pi$가 들어 있습니다.

곱을 전개해 세고 싶은 대상을 항으로 불러내는 오일러의 곱의 요령을, 오일러는 몇 해 뒤 분할수⁠(partition number)⁠를 세는 데에도 썼습니다. 분할수란 자연수를 순서와 상관없이 자연수의 합으로 쓰는 방법의 수입니다(생성함수⁠(generating function)⁠, 「세지 않고 세기」 5절).

4 · 역수의 합소수는 제곱수보다 많다

이 절의 물음은 이것입니다. 소수는 끝이 없지만, 제곱수 1, 4, 9, 16, …도 끝이 없습니다. 둘 가운데 어느 쪽이 더 촘촘할까? 3절에서 쓴 잣대를 그대로 씁니다. 제곱수의 역수를 끝없이 더하면 π²/6 ≈ 1.645에 멈췄습니다. 그렇다면 소수의 역수 $\tfrac12 + \tfrac13 + \tfrac15 + \tfrac17 + \tfrac1{11} + \cdots$는 어떤 값에 멈출까, 아니면 조화급수처럼 끝없이 커질까? 끝없이 커진다면 소수가 제곱수보다 훨씬 촘촘하다는 뜻입니다.

답에는 로그가 필요하니 먼저 로그를 되짚어 둡니다. $\log_{10} x$('로그 십 x')는 10을 몇 번 곱해야 x가 되는지를 묻는 수입니다. 10 × 10 × 10 = 1000이니 $\log_{10} 1000 = 3$이고, 100만이면 6입니다. 자릿수에서 1을 뺀 값과 비슷합니다. 자연로그 $\ln x$는 같은 질문을 10 대신 e ≈ 2.718이라는 특별한 수로 묻습니다. ln 10 ≈ 2.303, ln 1000 ≈ 6.908, ln 100만 ≈ 13.8입니다. 두 로그는 늘 같은 비율이어서 $\ln x \approx 2.303 \times \log_{10} x$입니다.

로그의 가장 중요한 성질은 곱을 합으로 바꾼다는 것입니다. $\ln(ab) = \ln a + \ln b$. 예를 들어 1000 = 10 × 100이니 ln 1000 = ln 10 + ln 100 ≈ 2.303 + 4.605 = 6.908입니다. 그리고 로그는 아주 느리게 자랍니다. x가 10배가 될 때마다 ln x는 겨우 2.303씩 늘어납니다.

로그가 쓰이는 첫 자리는 조화급수입니다. $1 + \tfrac12 + \cdots + \tfrac1x$는 끝없이 커지지만 아주 느려서, $\ln x$에 약 0.5772를 더한 값과 거의 같습니다. x = 100만까지 더하면 14.39이고, ln 100만 + 0.5772도 14.39입니다.

이제 오일러가 간 길을 네 걸음으로 따라갑니다. 첫째, 3절의 곱에 로그를 씌우면 곱이 합으로 바뀝니다. $\ln \prod \tfrac{1}{1-1/p}$는 소수마다 $-\ln(1 - 1/p)$를 더한 합입니다.

둘째, $y$가 작으면 $-\ln(1 - y) \approx y$이므로 $-\ln(1 - 1/p)$는 $1/p$와 거의 같습니다. p = 2이면 −ln(1/2) ≈ 0.693과 1/2 = 0.5로 차이가 꽤 나지만, p = 11이면 −ln(10/11) ≈ 0.0953과 1/11 ≈ 0.0909로 거의 같습니다. p가 커질수록 차이가 빠르게 줄어서, 차이를 모든 소수에 대해 더해도 유한합니다.

셋째, $x$ 이하의 소수에 대한 곱을 등비급수로 전개하면 1부터 $x$까지 모든 자연수의 역수가 빠짐없이 나오고 그보다 큰 수의 역수도 더 나오므로, 곱은 조화급수의 앞부분보다 큽니다. 3절 끝에서 쓴 것과 같은 까닭입니다. 넷째, 조화급수의 앞부분은 $\ln x$쯤이니 그 로그는 $\ln \ln x$쯤입니다. 네 걸음을 한 줄로 이으면 이렇습니다($\gtrsim$는 '대략 그 이상'이라 읽습니다).

왼쪽 끝 $\sum_{p \le x} \tfrac1p$는 'x 이하의 소수 p에 대해 1/p를 모두 더한 값'입니다. 여기서 두 $\approx$는 양쪽의 차이가 일정한 한도 안에 머문다는 뜻입니다. $\ln \ln x$는 로그를 두 번 씌운 것으로, x = 100만이면 ln x ≈ 13.8이고 ln 13.8 ≈ 2.63입니다. 정리하면, 소수의 역수 합은 적어도 $\ln \ln x$에서 상수를 뺀 만큼은 자랍니다. 느리지만 끝이 없습니다. 이 식은 아래쪽 한계만 주지만, 위쪽으로도 그 이상 자라지 않는다는 것이 곧 나올 메르텐스의 정리입니다.

숫자를 끌어 x를 바꿔 가며 세 값을 비교해 보세요. 가로축이 $\log_{10} x$라서, 숫자를 1 늘릴 때마다 x가 10배가 됩니다. $x =$ ($\log_{10} x =$ )까지 보면,

• 소수의 역수 합 $\sum_{p \le x} 1/p =$
• 어림값 $\ln \ln x + 0.2615 =$
• 조화급수 $\sum_{n \le x} 1/n =$

그림에서 조화급수는 곧은 직선으로 뻗어 곧 화면 위로 사라집니다. $\ln x$처럼 자라는 양은 가로축을 $\log_{10} x$로 잡으면 직선이 되기 때문입니다. 소수의 역수 합은 훨씬 굼뜨게, 점점 누우면서 오릅니다. 100만까지 더해도 3이 안 됩니다.

1874년 오스트리아의 수학자 프란츠 메르텐스가 증명한 대로, 이 합은 ln ln x + 0.2615와 거의 겹칩니다. 0.2615는 메르텐스가 계산한 보정 상수입니다. x = 100만이면 2.63 + 0.26 ≈ 2.89이고, 실제 합도 약 2.89입니다. 이 어림으로 치면 10¹⁰⁰(1 뒤에 0이 백 개 붙은 수)까지의 소수의 역수를 모두 더해도 약 5.70으로 6에 못 미칩니다. ln 10¹⁰⁰ ≈ 230.3이고 ln 230.3 ≈ 5.44이기 때문입니다. 그래도 멈추지는 않습니다. 반면 제곱수의 역수 합은 1.645를 넘지 못하고 그 값으로 모입니다.

흔히 둘 다 무한히 많으니 개수로는 비교할 수 없다고 생각합니다. 실제로 첫째 소수를 첫째 제곱수와, 둘째를 둘째와 짝짓는 식으로 하나씩 짝지어 세면, 소수와 제곱수는 둘 다 자연수와 같은 크기의 무한입니다. 그래도 역수 합이라는 잣대로 재면 차이가 드러납니다. 소수가 제곱수보다 훨씬 촘촘합니다. 100만 이하에 제곱수는 1,000개뿐이지만 소수는 78,498개입니다.

여기에 다음 이야기의 실마리가 숨어 있습니다. 수 $n$ 근처에서 소수가 나오는 비율이 $1/\ln n$쯤이라고 가정해 봅시다. 예를 들어 100만 근처라면 1/13.8, 곧 약 14개 중 하나가 소수라는 가정입니다. 그러면 소수의 역수 합은 수 n마다 '소수일 비율 × 1/n'을 더한 $\sum 1/(n \ln n)$과 비슷합니다.

이런 합은 적분⁠(integral)⁠으로 어림합니다. 적분은 곡선 아래의 넓이⁠(area)⁠이고, 폭 1짜리 막대를 쌓은 합을 매끄럽게 만든 것입니다. 곡선 $1/(t \ln t)$ 아래 2부터 x까지의 넓이를 계산하면 $\int_2^x dt/(t \ln t) = \ln \ln x - \ln \ln 2$입니다($\ln \ln t$가 t에 따라 늘어나는 빠르기가 정확히 $1/(t \ln t)$이기 때문입니다). 숫자로 확인해 볼 수 있습니다. t를 100에서 101로 1 늘리면 $\ln \ln t$는 약 1.5272에서 1.5293으로 0.0022쯤 늘고, $1/(100 \ln 100) = 1/460.5 \approx 0.0022$입니다. 오일러의 결과와 맞아떨어집니다.

정리하면, 소수의 역수 합은 $\ln \ln x$처럼 아주 느리지만 끝없이 자라고, 이것은 "x 근처에서 소수의 비율이 $1/\ln x$쯤"이라는 가정과 들어맞습니다. 오일러 자신은 이 밀도를 말하지 않았지만, 그와 들어맞는 단서는 이미 그의 공식 안에 있었습니다. 다만 역수 합만으로 밀도가 정해지지는 않으니, 단서는 어디까지나 단서입니다.

5 · 열다섯 살의 소수표가우스와 르장드르

이 절의 물음은 이것입니다. x 이하에 소수가 정확히 몇 개인지 일일이 세지 않고, 간단한 식으로 어림할 수 있을까? 어림한다면 어떤 식이 가장 정확할까? 4절의 끝에서 본 단서, "x 근처에서 소수의 비율은 약 $1/\ln x$"가 출발점입니다.

그 밀도를 표에서 읽어 낸 사람으로 가장 유명한 이는 가우스입니다. 다만 그는 이 짐작을 출판하지 않았고, 먼저 공식을 책에 실은 사람은 아래에 나오는 르장드르입니다. 가우스의 이야기는 50여 년 뒤 천문학자 엥케에게 보낸 편지로 전해집니다. 그 편지에서 가우스는 열다섯 살 무렵부터 소수의 빈도를 살폈다고 회고했습니다.

…그 첫 시작은 아주 먼 옛날, 1792년이나 1793년으로 거슬러 올라갑니다.— 카를 프리드리히 가우스, 요한 엥케에게 보낸 편지(1849년 12월 24일)

편지에 따르면 계기는 스위스 출신의 수학자 요한 하인리히 람베르트가 1770년 베를린에서 펴낸 로그표 부록을 손에 넣은 일이었습니다. 그 책에는 10만 남짓까지의 소수표가 로그표, 삼각함수표와 나란히 실려 있었습니다. 소수표는 천문학자와 측량사를 위한 계산 도구와 같은 책에 인쇄되던 물건이었습니다.

같은 편지에서 가우스는 한가한 15분이 생길 때마다 천 개씩 끊은 구간의 소수를 세었다고 적었습니다. 그렇게 쌓은 표를 보고 그는 수 $x$ 근처에서 소수가 나타나는 빈도가 대략 $1/\ln x$라고 짐작했습니다. 1000 근처라면 1/ln 1000 ≈ 1/6.9 ≈ 0.145, 곧 수 일곱 개에 하나꼴이고, 100만 근처라면 열네 개에 하나꼴입니다.

빈도를 알면 개수를 어림할 수 있습니다. 먼저 이름을 정합니다. $x$ 이하의 소수 개수를 $\pi(x)$라 적습니다($\pi$는 여기서 원주율이 아니라 소수의 개수를 뜻하는 기호입니다). 예를 들어 10 이하의 소수는 2, 3, 5, 7이니 π(10) = 4이고, π(100) = 25, π(1000) = 168입니다. 수 n마다 'n이 소수일 비율' $1/\ln n$을 2부터 x까지 차곡차곡 더하면 소수 개수의 어림값이 됩니다. 이 합을 매끄럽게 만든 것, 곧 밀도 곡선 $1/\ln t$ 아래 2부터 x까지의 넓이가 가우스의 어림입니다.

가운데 식 $\int_2^x \frac{dt}{\ln t}$는 "t가 2부터 x까지 갈 때 곡선 1/ln t 아래의 넓이"라고 읽습니다. 이것을 $\mathrm{Li}(x)$라 부르고, Li는 로그 적분(logarithmic integral)의 머리글자입니다. x = 1000이면 Li(1000) ≈ 177로 실제 개수 168보다 조금 많고, 오른쪽 끝의 더 간단한 식 1000/ln 1000 ≈ 145는 조금 모자랍니다.

합과 넓이가 거의 같은 까닭은 이렇습니다. 밀도 $1/\ln n$을 $n = 2, 3, 4, \dots$마다 더한 합은 폭 1짜리 막대를 쌓은 리만 합⁠(Riemann sum)⁠입니다. 막대 폭을 0으로 보내는 극한이 적분이지만, $1/\ln t$는 아주 천천히 줄어드는 함수라서 폭 1짜리 합도 적분 $\mathrm{Li}(x)$와 $1/\ln 2 \approx 1.44$ 넘게 차이 나지 않습니다(막대를 쌓아 넓이를 구하는 이야기는 「거리를 되찾기」에 있습니다).

위 식의 두 번째 $\approx$는 뜻이 약합니다. $\mathrm{Li}(x)$와 $x/\ln x$의 비는 1로 다가가지만, 차이는 $x$가 커질수록 벌어집니다. x = 1000에서 둘의 차이는 약 32, 100만에서는 약 6,200입니다. 비는 1.22에서 1.09로 1에 다가가는데도 차이는 커지는 것입니다.

거꾸로 보면 $\mathrm{Li}(x)$의 기울기⁠(slope)⁠, 곧 x가 1 늘 때 Li(x)가 늘어나는 양은 미적분의 기본정리⁠(fundamental theorem of calculus)⁠에 따라 정확히 $1/\ln x$입니다. 넓이를 오른쪽으로 폭 1만큼 늘리면 높이 $1/\ln x$짜리 띠가 더해지기 때문입니다. 가우스의 짐작을 그대로 옮긴 식인 셈입니다.

한편 프랑스의 르장드르는 독자적으로 1798년 『수론 시론』에서 $x/(A \ln x + B)$ 꼴의 공식을 제안했고, 1808년 판에서 이를 $x/(\ln x - 1.08366)$으로 구체화했습니다. A와 B는 표에 맞춰 고를 상수입니다. x/ln x의 분모에서 1.08366을 빼 조금 키운 식이라고 보면 됩니다.

넷을 나란히 놓아 봅시다. 숫자를 끌거나 버튼을 눌러 x를 키우세요. 왼쪽 그림에서는 노란 계단(실제 개수)과 세 곡선이 얼마나 붙어 있는지, 오른쪽 그림에서는 세 어림의 오차가 x에 따라 어떻게 자라는지를 봅니다. $x =$ ($\log_{10} x =$ ) ▶ x를 10부터 100만까지

• 실제 개수 $\pi(x) =$
• x / ln x $=$
• 가우스의 Li(x) $=$
• 르장드르의 공식 $=$

x가 작을 때 노란 계단은 울퉁불퉁합니다. 소수 하나마다 한 칸씩 오르고, 오르는 간격은 제멋대로입니다. 그런데 x를 키워 멀리서 보면 계단은 매끄러운 곡선으로 녹아들고, 세 근삿값이 그 곡선을 바짝 따라갑니다. 1절에서 본 무질서는 사라지지 않았습니다. 다만 개수를 세는 순간 무질서가 평균⁠(mean)⁠으로 뭉개질 뿐입니다.

오른쪽 그림은 누가 더 정확한지 보여 줍니다. 두 축이 모두 로그 눈금이어서, 세로로 한 칸 올라가면 오차가 10배라는 뜻입니다. x/ln x는 x가 17 이상이면 늘 조금 모자랍니다. 모자란 양은 x가 커지면 $x/(\ln x)^2$과 거의 같아집니다(둘의 비가 1로 다가갑니다). 그래서 실제 개수에 대한 오차의 비율, 곧 상대오차는 약 $1/\ln x$입니다. x = 100만이어도 1/13.8, 약 7%이니 1에 아주 느리게 다가갑니다.

100 남짓부터 100만까지는 르장드르의 공식이 셋 가운데 가장 정확합니다. 르장드르가 쓴 표에 맞춰 상수를 고른 결과이니 당연합니다. 그러나 500만 근처에서 Li(x)에 추월당하고, 그 뒤로 오차가 다시 불어나 결국 x/ln x와 같은 빠르기($x/(\ln x)^2$에 상수를 곱한 정도)로 자랍니다. 가장 오래 버티는 것은 가우스의 Li(x)입니다. 10¹⁶에서도 오차가 약 320만, 곧 실제 개수 279조의 1억분의 1 수준이고, 오차의 크기는 회색 점선 $\sqrt x$보다 아래에 머뭅니다. 이 $\sqrt x$가 왜 등장하는지는 7절에서 이야기합니다.

정리하면, 소수의 개수 $\pi(x)$는 "x 근처에서 소수의 비율은 $1/\ln x$"라는 짐작을 넓이로 쌓은 $\mathrm{Li}(x)$로 아주 잘 어림됩니다. 더 간단한 $x/\ln x$도 비율로는 맞지만 훨씬 느리게 맞습니다. 다만 이것은 표로 확인한 사실이지 증명이 아닙니다. 증명은 7절에서 봅니다.

가우스가 람베르트의 책 같은 책을 손에 넣을 수 있었던 데에는 후원자가 있었습니다. 가우스는 브라운슈바이크의 가난한 집에서 태어났지만, 1791년부터 브라운슈바이크 공작 카를 빌헬름 페르디난트가 학비를 대 주었습니다. 1801년의 『산술 연구』도 이 공작에게 바친 책입니다. 후원은 1806년 공작이 아우어슈테트 전투에서 나폴레옹의 군대에 맞서다 입은 상처로 죽으면서 끝났고, 가우스는 이듬해 괴팅겐 천문대장이 되었습니다(「잃어버린 소행성」).

그림의 범위에서는 늘 $\mathrm{Li}(x) > \pi(x)$입니다. 사람들은 오랫동안 이것이 언제나 성립하리라 여겼지만, 1914년 영국의 수학자 J. E. 리틀우드는 둘의 대소가 끝없이 여러 번 뒤바뀐다는 것을 증명했습니다. 처음 뒤바뀌는 곳은 아직 모릅니다. 10¹⁹보다 크고 10³¹⁷보다 작다는 것까지만 알려져 있습니다. 표를 아무리 길게 늘려도 드러나지 않는 법칙이 있다는 경고입니다.

6 · 가까이서는 동전, 멀리서는 법칙소수의 밀도

이 절의 물음은 이것입니다. 소수는 멀리서 보면 매끄러운 법칙을 따르는데, 가까이서 보면 왜 제멋대로일까? 그리고 그 '제멋대로'는 동전 던지기처럼 아무렇게나일까, 아니면 무언가 다를까?

가우스의 짐작을 확률의 말로 바꾸면 이렇습니다. $x$ 근처의 충분히 긴 구간에서 수 하나를 고르게 뽑으면, 그 수가 소수일 확률은 약 $1/\ln x$이다. '고르게 뽑는다'는 구간의 모든 수가 똑같은 확률로 뽑힌다는 뜻입니다. 구간이 너무 짧으면 아래 그림처럼 들쭉날쭉합니다. 지금 고른 $x =$ 근처라면 입니다(5절에서 끈 x를 그대로 씁니다).

100자리 수라면 약 230개 중 하나가 소수입니다. 100자리 수는 $10^{99}$과 $10^{100}$ 사이에 있고, ln 10¹⁰⁰ ≈ 230이기 때문입니다. 자릿수가 두 배가 되어도 소수의 비율은 절반으로만 줄어듭니다. 로그는 x를 제곱해도 두 배로만 커지기 때문입니다($\ln x^2 = 2 \ln x$). 200자리 수라면 약 460개 중 하나입니다.

이 사실 덕분에 RSA 암호⁠(RSA cryptosystem)⁠에 필요한 수백 자리 소수를 실제로 만들 수 있습니다. 큰 홀수를 무작위로 뽑아 소수인지 검사하기를 되풀이하면 평균 몇백 번 안에 하나가 걸리니까요(짝수를 빼면 확률이 두 배가 되어 100자리에서는 약 115번에 한 번입니다). 실제로 쓰는 검사는 동전 던지기를 섞어 아주 작은 확률로 틀릴 수 있는 방법입니다(「나머지로 지키는 비밀」 6절).

그렇다면 소수는 정말 "확률 $1/\ln n$로 던진 동전"처럼 행동할까요? 1936년 스웨덴의 수학자 하랄드 크라메르는 바로 이런 모형을 만들었습니다. 3 이상의 수 $n$마다 앞면이 나올 확률이 $1/\ln n$인 동전을 독립적으로 던져, 앞면이 나온 수를 '소수'라 부르는 것입니다. 독립적이란 한 수의 동전 결과가 다른 수의 결과에 아무 영향도 주지 않는다는 뜻입니다. 이렇게 만든 '가짜 소수'도 평균적으로는 진짜 소수와 같은 비율로 나옵니다.

진짜 소수와 비교해 봅시다. 수직선을 너비 $W =$ 인 구간 150개로 나누고(0부터 까지), 구간마다 소수의 비율을 막대로 그렸습니다. 보고 있는 것은 입니다. W를 끌어 구간의 너비를 바꾸고, 선택지를 눌러 진짜 소수와 가짜 소수를 번갈아 보세요. 볼 것은 막대가 청록 띠 밖으로 얼마나 자주 나가는가입니다.

W를 10으로 줄이면 막대는 들쭉날쭉합니다. W = 10이면 150개 구간 가운데 16개에 소수가 하나도 없습니다. 지금 고른 W에서는 소수가 없는 구간이 개입니다. 이것이 1절에서 본 "제멋대로"의 모습입니다. W를 키울수록 막대들은 곡선 1/ln x에 달라붙습니다. 동전을 많이 던질수록 앞면의 비율이 확률에 가까워지는 큰 수의 법칙⁠(law of large numbers)⁠과 같은 모습입니다(「도박판에서 온 편지」).

그럼 막대가 곡선에서 얼마나 벗어나야 '보통'일까요? 동전 모형에서는 이것을 계산할 수 있습니다. 구간 하나에 든 소수의 개수를 동전 모형으로 보면 거의 이항분포⁠(binomial distribution)⁠, 곧 '앞면 확률이 p인 동전을 W번 던졌을 때 앞면 개수'의 분포를 따릅니다(구간 안에서 $1/\ln n$이 조금씩 변하니 정확히는 아닙니다). 그 흔들림의 폭은 분산(값이 평균에서 흩어진 정도를 재는 양)으로 계산할 수 있습니다. 비율로 적으면 흔들림의 전형적인 크기(표준편차⁠, standard deviation⁠)는 $\sqrt{p(1-p)/W}$입니다. 예를 들어 p ≈ 0.1, W = 100이면 약 0.03입니다. 곡선 위아래로 이 크기의 두 배만큼 칠한 것이 청록 띠이고, 위 예라면 0.04에서 0.16 사이입니다. W를 키우면 흔들림이 줄어 띠도 좁아집니다.

지금 띠 밖으로 나간 막대는 개입니다. 크라메르의 가짜 소수로 바꾸면 W가 얼마이든 150개 중 대개 서너 개에서 아홉 개, 평균 여섯 개(약 4%)쯤이 띠를 벗어납니다. 흔들림이 정규분포(평균 근처에 많고 멀어질수록 드문 종 모양 분포)를 따른다면 약 4.6%가 띠 밖으로 나가야 하니 예상과 거의 같습니다. 동전을 많이 던진 합이 종 모양 분포에 가까워진다는 것이 중심극한정리⁠(central limit theorem)⁠입니다.

그런데 진짜 소수로 돌아오면 W가 30을 넘기만 해도 띠를 벗어나는 막대가 많아야 하나입니다. 흔히 소수가 동전 던지기처럼 아무렇게나 흩어져 있다고 생각하지만, 진짜 소수는 동전보다 더 고르게 퍼져 있습니다. 이유는 2절의 체에 있습니다. 진짜 소수는 2와 3 자신을 빼면 짝수나 3의 배수에 절대 떨어지지 않으니, 아무 데나 떨어지는 동전보다 덜 뭉칩니다. 그래서 요즘은 작은 소수의 배수를 먼저 걸러 낸 뒤 동전을 던지는 고친 모형도 씁니다.

정리하면, 소수는 짧은 구간에서는 들쭉날쭉하지만 구간을 넓히면 비율 $1/\ln x$에 달라붙고, 그 흔들림은 동전 모형이 예상하는 것보다도 작습니다.

멀리서 보면 법칙이 분명한데, 가까이서 묻는 질문은 여전히 어렵습니다. 차이가 2인 소수 쌍(11과 13, 17과 19, …)이 끝없이 있을까요? 이 쌍둥이 소수⁠(twin primes)⁠ 추측은 아직 풀리지 않았습니다. 추측이란 많은 사람이 참이라고 믿지만 아직 증명되지 않은 명제입니다. 2013년 중국계 미국 수학자 장이탕이 차이가 7,000만 이하인 소수 쌍이 무한히 많다는 것을 처음 증명했고, 곧 이어진 연구로 그 간격은 246까지 줄었습니다. 2까지는 아직 멉니다.

소수 판정⁠(primality test)⁠에도 긴 역사가 있습니다. 틀릴 여지가 없으면서도 자릿수의 다항식 정도 시간 안에 끝나는 판정법은 2002년에야 나왔습니다. 자릿수가 두 배가 될 때 걸리는 시간이 고정된 배수로만 늘어난다는 뜻입니다. 인도 칸푸르 공과대학의 마닌드라 아그라왈과 그의 두 학부생 니라지 카얄, 니틴 삭세나가 찾았습니다. "빨리 풀 수 있는 문제"가 정확히 무엇인지는 「기계가 풀 수 없는 문제」 7절에 있습니다.

이 돌파가 이루어진 과정도 20세기 수학과는 달랐습니다. 장이탕은 박사 학위를 받은 뒤 여러 해 동안 대학 밖에서 일하다가, 뉴햄프셔 대학의 강사로 있던 50대 후반에 이 결과를 『수학 연보』에 보냈습니다. 발표 몇 주 뒤 테런스 타오의 블로그에서, 누구나 댓글로 참여하는 인터넷 공동 연구 '폴리매스 8'이 시작되어 장의 논증을 한 단계씩 다듬었습니다. 그해 가을 영국의 젊은 수학자 제임스 메이너드는 전혀 다른 방법으로 간격을 600까지 줄였고, 두 흐름이 합쳐져 2014년 246에 이르렀습니다. 편지와 학술지로 몇 달씩 걸리던 일이 몇 주 단위로 오간 것입니다.

7 · 짐작에서 정리로체비쇼프, 리만, 그리고 1896년

이 절의 물음은 둘입니다. 5절의 어림이 옳다는 것을 어떻게 증명할까? 그리고 어림의 오차는 얼마나 작을까?

가우스와 르장드르의 짐작은 표에서 나온 것이었습니다. 표가 아무리 길어도 증명은 아닙니다. 리틀우드의 경고처럼 표는 속일 수 있으니까요. "$\pi(x)$와 $x/\ln x$의 비가 극한에서 1이 된다"는 짐작이 정리가 되기까지는 100년이 더 걸렸습니다. '극한에서 1이 된다'는 x를 한없이 키우면 비가 1에 원하는 만큼 가까워진다는 뜻입니다. x = 1000에서 비는 168/145 ≈ 1.16, 100만에서는 78,498/72,382 ≈ 1.08입니다.

크로톤의 피타고라스 학파에서 GIMPS까지, 소수를 붙든 사람들의 연표와 지도입니다. 1737년부터 1896년 사이에 수학 줄이 빽빽해지는 것, 그리고 그 사이 장소가 상트페테르부르크·파리·베를린·괴팅겐을 오가는 것을 보세요. 흐린 점은 같은 시대의 세계사입니다.

1850년 무렵 러시아의 파프누티 체비쇼프는 증명을 향한 첫 단단한 발판을 놓았습니다. 그는 충분히 큰 $x$에 대해 $\pi(x)$가 $x/\ln x$의 약 0.92배와 1.11배 사이에 있다는 것을 보였습니다. x = 100만이면 x/ln x ≈ 72,382이니 0.92배는 약 66,600, 1.11배는 약 80,300이고, 실제 개수 78,498이 그 사이에 있습니다. 이 한계는 비가 1이라는 것까지는 말하지 못하지만, 비가 0으로 줄거나 끝없이 커지지는 않는다는 것을 처음으로 증명했습니다.

체비쇼프는 또 비율이 어떤 값으로 수렴한다면(x가 커질 때 한 값에 다가간다면) 그 값은 1일 수밖에 없다는 것을 밝혔습니다. 같은 논증으로, 르장드르 공식 $x/(\ln x - B)$에서 길게 보아 가장 잘 맞는 B는 1.08366이 아니라 1이어야 합니다. 5절 그림에서 르장드르의 오차가 500만 근처부터 다시 불어나는 까닭이 여기 있습니다. 같은 무렵 그는 1보다 큰 모든 $n$에 대해 $n$과 $2n$ 사이에 늘 소수가 있다는, 프랑스의 수학자 조제프 베르트랑의 추측⁠(Bertrand's postulate)⁠도 증명했습니다. 예를 들어 10과 20 사이에는 11, 13, 17, 19가 있습니다.

리만의 생각을 따라가려면 복소수가 필요하니 먼저 짧게 되짚어 둡니다. 제곱하면 −1이 되는 새 수를 i라 하고, $3 + 2i$처럼 보통의 수(실수⁠, real number⁠) 두 개를 i로 묶은 수를 복소수라 합니다. 앞의 3을 실수부⁠(real part)⁠, 뒤의 2를 허수부라 부릅니다. 복소수 $a + bi$는 가로 a, 세로 b인 평면 위의 점으로 그릴 수 있고, 이 평면을 복소 평면이라 합니다. 실수는 가로축 위의 점입니다.

오일러의 합 $\sum 1/n^s$에는 s 자리에 복소수를 넣어도 됩니다. 이 합은 $s$의 실수부가 1보다 클 때만 유한한 값으로 모입니다. 리만은 합이 모이지 않는 곳까지 이 함수를 매끄럽게 이어 붙여 복소 평면 거의 전체(s = 1 한 점만 빼고)에서 정의했습니다. 이것을 해석적 연속⁠(analytic continuation)⁠이라 합니다.

비슷한 예를 들면, 합 $1 + x + x^2 + \cdots$은 $|x| \lt 1$에서만 값이 있지만 그곳에서 $\tfrac{1}{1-x}$과 같고, $\tfrac{1}{1-x}$은 x = 1만 빼면 어디서나 값이 있습니다($|x| \lt 1$은 x의 크기가 1보다 작다는 뜻입니다). x = 1/2이면 합은 1 + 1/2 + 1/4 + ⋯ = 2이고 1/(1 − 1/2)도 2입니다. x = 2이면 합 1 + 2 + 4 + ⋯은 끝없이 커지지만 1/(1 − 2) = −1이라는 값은 있습니다. 합이 뜻을 잃는 곳에서도 $\tfrac{1}{1-x}$이 그 자리를 이어받는 것입니다.

복소수 범위에서 미분⁠(differentiation)⁠ 가능하게(어느 방향으로든 매끄럽게) 이어 붙이는 방법은 하나뿐이라서, 넓힌 함수도 여전히 ζ라고 부를 수 있습니다(실수에서 그냥 매끄럽게 잇는 방법은 무수히 많으니, 이 유일성은 복소수이기에 얻는 성질입니다). 리만은 그렇게 넓힌 함수의 영점, 곧 값이 0이 되는 점들을 살폈습니다.

복소수가 왜 파동을 부르는지는 계산 한 줄로 보입니다. 재료는 오일러 공식⁠(Euler's formula)⁠ $e^{i\theta} = \cos\theta + i\sin\theta$입니다. 지수에 i × (각도 θ)를 넣으면, 복소 평면에서 원점을 중심으로 한 반지름 1인 원(단위원⁠, unit circle⁠) 위에서 각도 θ만큼 돈 점이 나온다는 뜻입니다. 이제 $s = \sigma + it$이면 $n^{-s} = n^{-\sigma} \cdot n^{-it}$이고, $n = e^{\ln n}$이므로 $n^{-it} = e^{-it\ln n}$입니다. 그래서 $n^{-s} = n^{-\sigma} e^{-it\ln n}$이고, 오일러 공식에 따라 $e^{-it\ln n}$은 단위원 위를 도는 점, 곧 $\cos(t\ln n) - i\sin(t\ln n)$입니다(「원을 그리는 지수함수」).

말로 읽으면, s의 실수부 σ('시그마')는 크기 $n^{-\sigma}$를 정하고, 허수부⁠(imaginary part)⁠ t는 반지름 1인 원 위에서 각도 $t \ln n$만큼 돈 방향을 정합니다. cos과 sin은 원 위를 도는 점의 가로·세로 좌표이니, 이 합에는 출렁이는 파동이 들어 있습니다. 정리하면, 복소수 지수는 '크기'와 '도는 각도'로 나뉘고, 도는 각도가 파동을 만듭니다.

이 계산이 리만의 공식에서 그대로 쓰입니다. 리만이 찾은 공식은 오늘날 '명시적 공식'이라 부르는데, 뼈대를 말로 적으면 이렇습니다.

ρ('로')는 제타 함수의 영점 하나를 가리키고, $\sum_\rho$는 그런 영점 모두에 대해 더하라는 뜻입니다(무엇을 영점으로 세는지는 아래에서 다시 적습니다). 매끄러운 주된 항은 5절의 $\mathrm{Li}(x)$입니다. 곧 Li(x)가 계단의 큰 모양을 맡고, 영점들이 계단의 울퉁불퉁한 부분을 맡습니다.

영점 하나의 파동이 어떻게 생겼는지 봅시다. 영점을 $\rho = \beta + i\gamma$(실수부 β '베타', 허수부 γ '감마')라 하면, 파동의 심장은 $x^\rho$입니다. 위와 같은 계산으로

입니다. 제타 함수의 영점은 늘 켤레끼리 짝을 지어 나옵니다. $\beta + i\gamma$가 영점이면 $\beta - i\gamma$도 영점입니다. 짝꿍은 sin 앞의 부호만 반대인 값을 주므로, 둘을 더하면 허수⁠(imaginary number)⁠ 부분이 지워지고 $2x^{\beta}\cos(\gamma \ln x)$가 남습니다. 영점 한 쌍이 실수 파동 하나를 만드는 것입니다. 실제 공식에서는 여기에 대략 $1/(|\rho|\ln x)$배로 줄이고 옆으로 조금 미는 손질이 더해지지만, 출렁임과 자라는 빠르기는 이 식이 정합니다.

이 파동은 x가 아니라 $\ln x$를 따라 출렁입니다. 허수부가 양수인 영점 가운데 허수부가 가장 작은 첫 영점은 $\rho_1 = \tfrac12 + 14.1347\,i$입니다. 그 파동은 $14.1347 \ln x$가 $2\pi$ 늘 때마다, 곧 $\ln x$가 $2\pi/14.1347 \approx 0.445$ 늘 때마다 한 번 오르내립니다. x로 말하면 x가 약 $e^{0.445} \approx 1.56$배가 될 때마다 한 번입니다. 허수부 γ가 큰 영점일수록 더 촘촘히 출렁이는 파동입니다.

그래서 리만의 공식은 매끄러운 사인파들을 더해 톱니나 계단 모양을 만드는 푸리에 급수와 닮았습니다. 파동 하나가 제타 함수의 영점 한 쌍(서로 켤레인 두 복소수, 곧 $a + bi$와 $a - bi$)에 대응하고, 영점을 더 많이 넣을수록 파동의 합이 계단의 모서리를 더 날카롭게 그려 냅니다. 노란 계단 $\pi(x)$가 소수마다 한 칸씩 오르는 모양이, 무한히 많은 파동이 겹쳐 만든 모양이라는 것입니다. 복소 평면 위 영점의 위치는 도메인 컬러링⁠(domain coloring)⁠, 곧 평면의 각 점을 그곳의 함숫값에 따라 색칠한 그림으로 볼 수 있습니다.

파동의 크기는 영점의 실수부가 정합니다. cos은 −1과 1 사이를 오가니, 실수부가 $\beta$인 영점의 파동은 대략 $x^{\beta}$에 비례하는 폭으로 흔들립니다(앞에서 말한 $1/(|\rho|\ln x)$ 같은 손질은 이보다 훨씬 느리게 변하니 뒤로 미뤄 둡니다). 그러니 $\beta$가 작을수록 흔들림도 작습니다. x = 100만이면 $x^{1/2}$ = 1,000이지만($x^{1/2}$은 $\sqrt x$와 같습니다), $x^{0.9}$ ≈ 25만입니다. 실수부가 1/2인 영점의 흔들림은 소수의 개수 78,498의 몇 %에도 못 미치는 규모에서 자라지만, 실수부가 0.9인 영점이 있다면 그 흔들림은 개수를 통째로 흔들 만한 규모에서 자랄 수 있습니다.

제타 함수는 −2, −4, −6, …에서도 0이 되지만, 이것들은 쉽게 찾아지는 '자명한' 영점이라 따로 칩니다. 자명한 영점⁠(trivial zero)⁠들은 명시적 공식에서 '작고 매끄러운 보정'에 들어가고, 합 $\sum_\rho$가 도는 것은 나머지, 곧 자명하지 않은 영점⁠(nontrivial zero)⁠들입니다. 이 영점들은 모두 실수부가 0과 1 사이인 띠 안에 있다는 것이 알려져 있습니다. 리만은 이 자명하지 않은 영점의 실수부가 모두 정확히 $\tfrac12$이라고 짐작했습니다. 복소 평면에 그리면, 영점이 모두 가로 좌표가 1/2인 세로 직선 한 줄 위에 늘어서 있다는 짐작입니다. 논문에는 근거가 적혀 있지 않지만, 70여 년 뒤 독일의 수학자 카를 루트비히 지겔이 유고를 살펴보니, 리만은 처음 몇 개의 영점을 실제로 계산해 두었습니다.

근들이 모두 실수일 가능성이 매우 높다. 물론 이에 대한 엄밀한 증명이 있으면 좋겠지만, 나는 잠깐의 헛된 시도 몇 번 끝에 그 증명을 찾는 일을 일단 제쳐 두었다. 내 연구의 당장의 목적에는 필요 없어 보였기 때문이다.— 베른하르트 리만, 「주어진 수보다 작은 소수의 개수에 대하여」(1859). 리만은 s = 1/2 + it로 바꾼 변수 t로 적었으므로, 여기서 '근 t가 실수'라는 말은 영점의 실수부가 1/2이라는 말과 같습니다.

이것이 리만 가설입니다. 가설이 참이면 어떻게 될까요? 모든 파동의 크기가 $\sqrt{x}$ 정도에 묶이고, $\pi(x)$와 $\mathrm{Li}(x)$의 차이도 $\sqrt{x}\,\ln x$에 어떤 고정된 상수를 곱한 값을 넘지 못합니다(1901년 스웨덴의 헬게 폰 코흐가 보였습니다). x = 10¹⁶이면 $\sqrt x$는 10⁸, 곧 1억이고 ln x는 약 37이니, $\sqrt x\,\ln x$는 약 37억입니다. 실제 개수 279조의 7만분의 1쯤이니 아주 작은 오차입니다.

5절 오른쪽 그림에서 분홍 점들이 회색 $\sqrt x$ 선 아래를 따라가는 모습은 이 예측과 어긋나지 않습니다. 물론 리틀우드의 경고처럼, 10¹⁶까지의 그림이 증명이 되지는 않습니다. 거꾸로 이 오차 한계가 성립하면 리만 가설도 참입니다. 정리하면, 소수가 얼마나 고르게 퍼져 있는가라는 질문과 복소 평면 위 영점의 위치라는 질문이 같은 질문인 것입니다.

1900년 힐베르트는 이 가설을 20세기 수학의 과제 목록에 넣었고, 2000년에는 클레이 수학연구소의 밀레니엄 문제 가운데 하나가 되었습니다. 아직 풀리지 않았습니다.

리만 가설 전체가 없어도 소수 정리⁠(prime number theorem)⁠는 증명할 수 있었습니다. 1896년 프랑스의 자크 아다마르와 벨기에의 샤를장 드 라 발레 푸생은 서로 독립적으로, 제타 함수가 실수부 1인 직선 위에서는 0이 되지 않는다는 것을 보였습니다. 모든 영점의 실수부 $\beta$가 1보다 작으면 흔들림 $x^{\beta}$는 $x$보다 느리게 자랍니다. 파동 중 어느 것도 길게 보면 주된 항만큼 크지는 않다는 뜻입니다. 파동이 무한히 많으니 그 합까지 다스리려면 섬세한 논증이 더 필요했지만, 열쇠는 이 사실 하나였습니다.

이것이 소수 정리입니다. 식은 "x를 한없이 키우면 π(x)를 x/ln x로 나눈 비가 1에 다가간다"고 읽습니다(lim은 극한을 뜻합니다). 가우스가 소수를 세기 시작한 지 약 100년 만이었습니다. 흔히 이 정리가 π(x)와 x/ln x의 차이가 작아진다는 뜻이라고 생각하지만, 5절에서 본 대로 차이는 오히려 커집니다. 작아지는 것은 차이의 비율입니다.

정리하면, 소수 정리를 증명하는 열쇠는 제타 함수의 영점이 실수부 1인 직선 위에는 없다는 사실이었고, 오차가 얼마나 작은지는 영점이 실수부 1/2인 직선에서 얼마나 벗어나는지에 달려 있습니다. 리만 가설은 하나도 벗어나지 않는다는 짐작입니다.

1948–49년에는 노르웨이의 아틀레 셀베르그와 헝가리의 에르되시가 복소수를 쓰지 않는 '초등적' 증명을 내놓아 또 한 번 놀라움을 주었습니다. 여기서 초등적이란 쉽다는 뜻이 아니라 복소함수⁠(complex function)⁠의 도구를 쓰지 않는다는 뜻입니다.

이것이 뜻밖이었던 까닭은 위에서 본 연결에 있습니다. 소수 정리는 '실수부 1인 직선 위에는 영점이 없다'는 사실과 사실상 같은 말이어서, 한쪽에서 다른 쪽을 끌어낼 수 있습니다. 그런데도 영점을 한 번도 말하지 않고 증명할 수 있다는 것입니다. 셀베르그의 출발점은 소수를 그 로그의 무게로 세는 합 하나를 아주 정확히 어림하는 식이었습니다(오늘날 셀베르그의 대칭 공식이라 부릅니다). 이것으로, x가 커질 때 비 $\pi(x)/(x/\ln x)$가 오르내리는 폭의 위쪽 끝과 아래쪽 끝이 체비쇼프의 0.92와 1.11처럼 벌어진 채로 있을 수 없고, 결국 둘 다 1이어야 함을 보였습니다.

에르되시는 또 하나의 추측도 남겼습니다. 역수의 합이 끝없이 커지는(발산⁠(divergence)⁠하는) 자연수의 집합에는 원하는 만큼 긴 등차수열⁠(arithmetic progression)⁠이 들어 있으리라는 것입니다. 등차수열이란 3, 5, 7이나 5, 11, 17, 23, 29처럼 같은 간격으로 늘어선 수들입니다. 4절에서 본 대로 소수는 역수의 합이 발산하는 집합입니다. 일반적인 추측은 아직 풀리지 않았지만, 소수에 대해서는 2004년 영국의 벤 그린과 오스트레일리아 출신의 테런스 타오가 원하는 만큼 긴 등차수열이 들어 있음을 증명했습니다. 수를 색칠하는 반 데르 바르던 정리⁠(van der Waerden's theorem)⁠에서 시작된 이 이야기는 「완전한 무질서는 없다」 7절에 있습니다.

'원하는 만큼 긴'의 뜻을 짚어 둡니다. 길이를 먼저 정하면(10항이든 100항이든) 그 길이의 등차수열이 소수 속 어딘가에 있다는 뜻이지, 끝없이 이어지는 등차수열 하나가 있다는 뜻이 아닙니다. 끝없는 것은 있을 수 없습니다. a, a + d, a + 2d, …에서 첫 항 a가 2 이상이면, a번 간격을 더한 항 $a + a d = a(1 + d)$는 a로 나누어떨어지기 때문입니다. 5, 11, 17, 23, 29도 다음 항이 35 = 5 × 7입니다.

소수에 대해 증명하기 어려웠던 까닭은 소수가 점점 드물어지기 때문입니다. 자연수 가운데 일정한 비율 이상(이를테면 1%)을 끝까지 차지하는 집합에는 원하는 만큼 긴 등차수열이 있다는 세메레디의 정리가 있지만, 소수의 비율 $1/\ln x$는 x가 커지면 0으로 줄어드니 이 정리를 그대로 쓸 수 없습니다. 그린과 타오는 소수를 '소수보다 촘촘하면서, 6절의 동전 던지기처럼 고르게 퍼진' 더 큰 집합 속에 넣고, 그 안에서는 소수가 일정한 비율을 차지한다는 것을 보여 이 벽을 넘었습니다.

초등적 증명 뒤에는 다툼도 있었습니다. 셀베르그와 에르되시는 프린스턴 고등연구소에서 서로의 중간 결과를 이어 받으며 증명에 이르렀지만, 공동 논문으로 낼지 따로 낼지를 두고 크게 다투었습니다. 결국 1949년 셀베르그는 『수학 연보』에, 에르되시는 『미국 국립과학원 회보』에 따로 실었고, 누가 무엇을 먼저 했는지를 두고 두 사람의 기억은 끝내 엇갈렸습니다. 이 초등적 증명은 뒤에 다른 쓰임도 얻었습니다. 2005년 카네기멜런 대학의 제러미 아비개드와 동료들은 셀베르그의 증명을 증명 보조기(증명의 한 걸음 한 걸음이 규칙에 맞는지 컴퓨터가 확인하는 프로그램) Isabelle로 옮겨, 소수 정리의 증명 전체를 기계가 한 줄씩 검사하게 했습니다(「증명은 프로그램이다」).

체비쇼프가 소수에 손을 댄 계기는 오일러였습니다. 오일러가 오래 일한 상트페테르부르크 학술원은 1849년 그의 정수론 논문과 원고를 모은 두 권짜리 논문집을 펴냈습니다. 젊은 체비쇼프는 수학자 빅토르 부냐콥스키 밑에서 이 편집을 맡아 오일러의 논문을 체계적으로 정리했습니다. 같은 해 그는 정수론 논문으로 박사 학위를 받았고, 이어 위의 부등식들을 증명했습니다. 100년 전 한 도시에서 쓰인 원고가 같은 도시의 다음 세대에게 문제를 넘겨준 셈입니다. 체비쇼프는 기계의 연결 막대와 확률에서도 이름을 남겼고, 그의 제자 마르코프의 글자 세기는 「다음 단어를 맞히는 기계」의 출발점이 됩니다.

영점을 실제로 찾아보는 일은 계산 도구의 역사를 따라갔습니다. 1914년 하디는 실수부가 $\tfrac12$인 영점이 무한히 많다는 것을 증명했습니다. 다만 그 밖에 영점이 하나도 없다는 증명은 아니어서 가설은 그대로 남았습니다. 1936년 옥스퍼드의 티치마시는 처음 1,041개의 영점이 모두 직선 위에 있음을 확인했습니다. 1939년 케임브리지의 튜링은 무게추를 단 톱니바퀴 여든 개로 영점을 찾는 기계를 설계했지만, 전쟁이 나자 완성하지 못한 채 블레츨리 파크의 암호 해독으로 떠났습니다(「나머지로 지키는 비밀」 7절). 전쟁 뒤 1950년 그는 맨체스터 대학의 전자계산기로 1,104번째 영점까지가 모두 직선 위에 있음을 확인하고, 그 결과를 1953년에 발표했습니다. 1936년 계산이란 무엇인지를 정의한 사람이 그 정의를 따라 만든 기계로 소수의 가설을 시험한 것입니다(「기계가 풀 수 없는 문제」). 오늘날에는 수조 개의 영점이 모두 직선 위에 있음이 확인되었고, 반례는 하나도 나오지 않았습니다.

8 · 수학 밖으로표를 만든 손, 소수를 쓰는 세상

이 절은 두 가지를 봅니다. 짐작의 재료였던 소수표를 누가 어떻게 만들었는가, 그리고 쓸모없어 보이던 소수가 수학 밖에서 무엇이 되었는가.

가우스도 르장드르도 표 없이는 아무것도 짐작할 수 없었습니다. 컴퓨터 이전의 소수표는 사람이 손으로 만든 것입니다. 1776년 빈에서 국비로 펴내기 시작한 펠켈의 큰 약수표는 팔리지 않아, 남은 종이가 튀르크와의 전쟁 때 탄약 싸개로 쓰였다고 전합니다. 19세기 프라하의 쿨리크는 20년 넘게 혼자 1억까지의 약수표를 만들어 빈 학술원에 남겼지만, 그 표는 끝내 출판되지 못했습니다.

20세기에 들어서야 표는 기계를 만났습니다. 1909년과 1914년 버클리의 D. N. 레머는 카네기 연구소의 지원으로 1,000만까지의 약수표와 소수표를 펴냈고, 그의 아들 D. H. 레머는 1920년대에 자전거 체인으로, 1930년대에는 광전관(빛을 받으면 전류가 흐르는 진공관)으로 체질하는 기계를 만들었습니다. 2절의 체가 톱니바퀴와 빛으로 옮겨 간 셈입니다.

소수 사냥에는 더 오래된 목표도 있었습니다. 『원론』 9권의 마지막 명제는 $2^n - 1$이 소수이면 $2^{n-1}(2^n - 1)$이 완전수⁠(perfect number)⁠, 곧 자기를 뺀 약수의 합이 자기와 같은 수라고 말합니다($n = 2$이면 6, $n = 3$이면 28). 28의 약수 1, 2, 4, 7, 14를 더하면 정말 28입니다. 5세기의 신학자 아우구스티누스는 『신국론』에서 신이 6일 동안 세상을 지은 것은 6이 완전수이기 때문이라고 풀이했습니다.

17세기에는 그 소수 $2^n - 1$ 자체가 사냥감이 되었습니다. 1640년 툴루즈의 페르마는 파리의 수도사 마랭 메르센에게 보낸 편지에서 $2^{37} - 1$이 $223 = 2 \cdot 37 \cdot 3 + 1$로 나누어진다고 알렸습니다. 이 계산은 뒷날 페르마 소정리⁠(Fermat's little theorem)⁠라 불릴 성질로 약수의 후보를 좁힌 것이었습니다. q가 소수이고 a가 q의 배수가 아니면, $a^{q-1}$을 q로 나눈 나머지가 1이라는 성질입니다. 예를 들어 q = 7, a = 2이면 $2^6 = 64 = 9 \times 7 + 1$이니 나머지가 1입니다. 이 성질에서 p가 홀수인 소수일 때 $2^p - 1$의 소인수는 모두 $2pk + 1$ 꼴(k는 자연수)이어야 한다는 것이 나옵니다. p = 37이면 $2 \cdot 37 = 74$이니 후보는 74에 1, 2, 3, …을 곱하고 1을 더한 수입니다. 그래서 75, 149, 223, …처럼 이 꼴의 수만 시험하면 되고, 세 번째 후보 223에서 나누어떨어집니다(「나머지로 지키는 비밀」).

1644년에는 메르센이 $2^p - 1$이 소수가 되는 $p$의 목록을 내놓았습니다. 목록에는 틀린 곳이 몇 군데 있었지만, 오늘날 이런 수를 메르센 수⁠(Mersenne number)⁠라고 부릅니다.

같은 1640년 무렵 페르마는 편지들에서 또 하나의 짐작을 적었습니다. $2^{2^n} + 1$ 꼴의 수 3, 5, 17, 257, 65537이 모두 소수이니 이 꼴의 수는 언제나 소수라는 것입니다. 페르마 자신도 증명은 없다고 인정했습니다. 1732년 상트페테르부르크의 스물다섯 살 오일러가 다음 수 $2^{32} + 1 = 4{,}294{,}967{,}297$이 $641 \times 6{,}700{,}417$임을 보였습니다. 641 = 10 × 64 + 1이고, 오일러는 뒤에 이 수의 소인수가 $64k + 1$ 꼴뿐임을 증명했습니다. 앞 문단의 $2pk + 1$과 같은 요령입니다. 그 뒤로 새 페르마 소수⁠(Fermat prime)⁠는 하나도 나오지 않았고, $n = 5$부터 적어도 $n = 32$까지는 모두 합성수로 확인되었습니다. 이 다섯 소수는 뜻밖의 두 곳에 다시 나타납니다. 1796년 열여덟 살의 가우스는 정17각형⁠(regular heptadecagon)⁠을 자와 컴퍼스로 그릴 수 있음을 발견했고, 소수 $p$에 대해 정$p$각형을 그릴 수 있는 것은 $p$가 페르마 소수일 때뿐임이 뒤에 밝혀졌습니다(「불가능의 증명」 3절). 그리고 65537은 오늘날 RSA 암호에서 공개 지수 $e$, 곧 메시지를 잠글 때 거듭제곱하는 지수로 가장 흔히 쓰이는 수입니다(자연로그의 밑 e와는 다른 수입니다). 이진법⁠(binary)⁠으로 1 뒤에 0이 열다섯 개, 다시 1이 오는 수라서 거듭제곱 계산이 빠르기 때문입니다.

그 뒤 가장 큰 소수의 기록은 계산 도구의 역사를 따라 늘어났습니다. 1876년 파리의 수학자 에두아르 뤼카가 손으로 증명한 $2^{127} - 1$은 1951년까지 알려진 가장 큰 소수였고, 1952년 1월 로스앤젤레스의 전자계산기 SWAC은 하룻밤 사이에 $2^{521} - 1$과 $2^{607} - 1$을 찾았습니다. 1996년 시작된 인터넷 자원봉사 계산 GIMPS(Great Internet Mersenne Prime Search, 메르센 소수⁠(Mersenne prime)⁠를 찾는 대규모 공동 계산)는 2024년 4,100만 자리가 넘는 $2^{136279841} - 1$을 찾았습니다. 거꾸로 소수 계산은 새 기계를 시험하는 데도 쓰였습니다. 1994년 미국의 수학자 토머스 나이슬리는 쌍둥이 소수의 역수 합을 계산하다 결과가 어긋나는 원인을 좇아 인텔 펜티엄 칩의 나눗셈 결함을 찾아냈습니다.

표에 기댄 짐작의 힘과 한계는 한 편지에서도 드러납니다. 케임브리지의 수학자 G. H. 하디의 삶을 크게 바꾼 것은 1913년 마드라스 항만청의 서기 라마누잔이 보낸 편지였습니다. 대학을 마치지 못한 그는 혼자 찾은 공식들을 빼곡히 적어 보냈고, 하디는 이듬해 그를 케임브리지로 불렀습니다. 편지에는 소수의 개수를 세는 공식도 있었지만 하디는 그것이 틀렸다고 보았습니다. 라마누잔은 표에 기대어 짐작했을 뿐 7절의 영점들이 만드는 흔들림을 몰랐다는 것입니다. 대신 둘은 1917년, 보통의 수 $n$에는 서로 다른 소인수가 대략 $\ln \ln n$개 있다는 것을 증명했습니다. 여기서 '보통의 수'란, 1부터 $N$까지에서 이 어림을 벗어나는 수의 비율이 $N$이 커질수록 0으로 간다는 뜻입니다. 4절의 $\ln \ln x$가 다시 나타난 것입니다. 병을 얻은 라마누잔은 1919년 인도로 돌아가 이듬해 서른두 살로 세상을 떠났습니다.

1940년 하디는 『어느 수학자의 변명』에서, 정수론은 전쟁에 쓰일 일이 없는 깨끗한 학문이라는 데서 위안을 얻었습니다. 2차 세계대전이 한창이던 해였습니다. 그러나 하디의 위안은 오래가지 않았습니다. 1977년 이후 큰 소수는 RSA 암호의 열쇠가 되었고, 6절의 밀도 $1/\ln x$는 그런 열쇠를 언제든 구할 수 있다는 보증이 되었습니다. 플라톤이 말한 '사고파는 일'과 '전쟁'이 가장 쓸모없어 보이던 수학을 다시 찾아온 것입니다.

하디가 정수론에 끌린 데에는 철학도 있었습니다. 같은 책에서 그는 이렇게 썼습니다. "317이 소수인 것은 우리가 그렇게 생각해서도, 우리 마음이 어떤 식으로 생겨서도 아니라, 그것이 그러하기 때문이다. 수학의 실재가 그렇게 지어져 있기 때문이다." 수학의 대상이 사람과 상관없이 있고 수학자는 그것을 발견할 뿐이라는 이 생각을, 1절의 플라톤 이름을 따 수학적 플라톤주의⁠(Platonism)⁠라고 부릅니다. 반대편에도 진지한 답이 있습니다. 네덜란드의 브라우어르는 수가 사람의 마음이 한 걸음씩 지어 내는 구성물이라고 보았습니다(직관주의⁠, intuitionism⁠). 힐베르트는 무한을 다루는 수학을 기호를 규칙대로 다루는 일로 보고, 그 규칙이 모순을 낳지 않음을 유한한 계산으로 보이자고 했습니다(형식주의⁠, formalism⁠). 그런데 317이 소수라는 데에는 세 입장이 모두 동의합니다. 317을 2, 3, 5, 7, 11, 13, 17로 나눠 보는 유한한 계산이면 확인되기 때문입니다(17² = 289이고 19² = 361이니 2절의 체처럼 17까지만 나눠 보면 됩니다). 입장이 갈리는 것은 '소수는 끝이 없다'처럼 무한을 말하는 문장을 어떻게 읽느냐입니다. 플라톤주의자에게 이 문장은 이미 다 갖추어진 소수 전체에 대한 사실이고, 직관주의자에게는 어떤 유한한 목록이 와도 그 밖의 소수를 지어 낼 수 있다는 약속입니다. 1절에서 본 유클리드의 조심스러운 문장과 그 증명은 두 읽기를 모두 만족시킵니다. 이 논쟁이 20세기 초에 어떻게 맞붙었는지는 수학 기초론 논쟁⁠(debate on the foundations of mathematics)⁠에 있습니다.

9 · 이어지는 길소수가 닿는 곳

소수는 정수론 안에만 머물지 않습니다. 이 글에서 지나온 길과 그 너머를 모아 보면 이렇습니다.

• 암호: 큰 두 소수를 곱하기는 쉽지만 곱에서 두 소수를 되찾기는 어렵습니다. 이 비대칭 위에 RSA 암호가 서 있고, 자물쇠를 여는 열쇠는 2절의 오일러 피 함수와 8절의 페르마 소정리입니다. 자세한 이야기는 「나머지로 지키는 비밀」에 있습니다.
• 확률: "소수일 확률 $1/\ln x$"와 "서로소일 확률 $6/\pi^2$"은 이미 정해져 있는 정수에 확률의 언어를 입혀 얻은 답입니다. 정확히는 유한한 범위에서 센 비율이 범위를 넓힐 때 다가가는 값입니다. 크라메르 모형처럼 무작위 모형으로 추측을 세우고, 진짜 소수와 어긋나는 곳에서 새 구조를 찾습니다.
• 해석학: 소수를 세는 문제가 로그, 적분, 무한곱⁠(infinite product)⁠, 조화급수의 문제로 바뀌었습니다. 수를 세는 데 연속적인 도구를 쓰는 이 방법을 해석적 정수론⁠(analytic number theory)⁠이라 부릅니다.
• 복소수: 소수의 가장 깊은 비밀은 복소 평면 위 제타 함수의 영점에 있습니다. 푸리에 급수처럼 계단을 파동으로 쪼개는 생각이 여기서도 쓰입니다.
• 그림: 자연수를 나선으로 감고 소수에만 점을 찍으면 뜻밖의 사선 줄무늬가 보입니다. 1963년 폴란드 출신의 수학자 스타니스와프 울람이 학회에서 낙서하다 발견한 울람 나선⁠(Ulam spiral)⁠입니다. 사선 하나하나는 $4n^2 + bn + c$ 꼴 이차식의 값들이고, 어떤 이차식이 소수를 많이 내는지는 2절의 "나머지 줄"처럼 작은 소수로 나눈 나머지가 크게 좌우합니다.
• 기하⁠(geometry)⁠: 4로 나눈 나머지가 1인 소수(5, 13, 17, …)는 두 제곱수의 합으로 쓸 수 있고 3인 소수는 그럴 수 없습니다. 페르마가 말하고 오일러가 증명한 이 사실은 빗변⁠(hypotenuse)⁠이 소수인 피타고라스 세 쌍⁠(Pythagorean triples)⁠과 이어집니다($5^2 = 3^2 + 4^2$, $13^2 = 5^2 + 12^2$).
• 분해가 하나가 아닌 세계: 1절의 산술의 기본정리는 정수에서만 공짜입니다. $a + b\sqrt{-5}$ 꼴의 수들에서는 $6 = 2 \cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5})$처럼 분해가 둘이 되고, 그 사실을 놓친 1847년의 페르마 증명과 그것을 고치며 태어난 아이디얼은 「틀린 증명이 만든 수학」에 있습니다.
• 자와 컴퍼스: 8절의 페르마 소수 3, 5, 17, 257, 65537은 자와 컴퍼스로 그릴 수 있는 정다각형⁠(regular polygon)⁠을 정합니다. 가우스의 정17각형과, 그리지 못하는 것을 증명하는 방법은 「불가능의 증명」 3절에 있습니다.
• 계산하는 기계: 튜링이 제타 함수의 영점을 계산한 일, 소수 판정이 '빨리 풀리는 문제'임이 증명된 일, 그리고 '빨리'의 뜻은 「기계가 풀 수 없는 문제」에서, 소수 정리를 기계가 검사하게 만든 증명 보조기⁠(proof assistant)⁠는 「증명은 프로그램이다」에서 이어집니다.