정수론 1강. 소수: 수의 원자
모든 자연수는 소수로 지어진 건물입니다. 그런데 벽돌이 어디서 나타날지는 아무도 모릅니다.
풀고 시작
수의 원자라는 발상
소수(prime number)는 1과 자기 자신으로만 나누어떨어지는 1보다 큰 자연수입니다. 2, 3, 5, 7, 11이 그 시작이죠. 소수가 특별한 이유는 산술의 기본정리(fundamental theorem of arithmetic)가 보장하는 지위 때문입니다. 1보다 큰 모든 자연수는 소수들의 곱으로 표현되며, 곱하는 순서를 무시하면 그 표현은 유일합니다. 60은 2² × 3 × 5이고, 다른 방식은 없습니다. 화학자가 물질을 원소로 분해하듯 수학자는 수를 소수로 분해합니다. 소수는 곱셈 세계의 원자인 셈이죠.
이 유일성 때문에 1은 소수에서 제외됩니다. 1을 소수로 인정하면 60 = 1 × 2² × 3 × 5 = 1² × 2² × 3 × 5처럼 분해가 무한히 많아져 정리가 무너지니까요. 1의 제외는 취향이 아니라 정리를 지키기 위한 설계입니다.
유클리드: 소수는 끝나지 않는다
기원전 300년경 유클리드(Euclid)는 『원론』에서 소수가 무한히 많다는 것을 증명했습니다. 논증의 뼈대는 이렇습니다. 소수의 유한한 목록 p₁, p₂, ..., pₙ이 전부라고 가정합니다. 이들을 모두 곱하고 1을 더한 수 N = p₁ × p₂ × ... × pₙ + 1을 만들죠. N을 목록의 어떤 소수로 나누어도 나머지가 1이므로, N은 목록의 소수로 나누어떨어지지 않습니다. 그런데 산술의 기본정리에 따라 N은 어떤 소수의 배수여야 합니다. 그 소수는 목록 밖에 있을 수밖에 없죠. 어떤 유한 목록도 완전할 수 없으므로 소수는 무한합니다.
이 증명은 2300년이 지난 지금도 수학적 증명의 모범으로 인용됩니다. 새 소수를 하나도 직접 제시하지 않으면서, 목록이 끝날 수 없다는 구조만으로 무한을 확정하기 때문이죠.
소수는 어떻게 흩어져 있는가
소수는 무한하지만 갈수록 희박해집니다. 100까지는 25개, 1000까지는 168개죠. 개수를 세는 함수 π(x)에 대해, 소수 정리(prime number theorem)는 π(x)가 대략 x/ln x에 가까워진다고 말합니다. 직관적으로 읽으면, x 근처에서 아무 수나 골랐을 때 그것이 소수일 확률은 약 1/ln x입니다. 100자리 수 근처에서는 대략 230개 중 하나꼴이죠. 이 정리는 가우스와 르장드르가 방대한 소수표를 들여다보며 추측했고, 1896년 아다마르(Hadamard)와 드 라 발레 푸생(de la Vallée Poussin)이 각각 독립적으로 증명했습니다. 추측에서 증명까지 한 세기가 걸린 셈입니다.
여기서 주목할 대비가 있습니다. 소수의 전체 밀도는 이렇게 매끈한 법칙을 따르는데, 개별 소수가 어디 나타날지는 여전히 예측 불가능합니다. 통계학 과목에서 본 것처럼, 집단의 규칙성과 개체의 무작위성은 얼마든지 공존하죠. 이 분포의 더 정밀한 구조를 묻는 것이 1859년 리만(Riemann)이 제기한 리만 가설인데, 상금 백만 달러가 걸린 밀레니엄 문제로 지금도 미해결 상태입니다.
풀리지 않은 문제들
소수 연구의 최전선은 놀랄 만큼 초등적인 질문들입니다. 쌍둥이 소수 추측은 (3, 5), (11, 13), (101, 103)처럼 차이가 2인 소수 쌍이 무한히 많다고 주장합니다. 2013년 장이탕(Yitang Zhang)이 "차이가 7000만 이하인 소수 쌍은 무한히 많다"를 증명해 돌파구를 열었고, 이후 공동 연구로 그 간격은 246까지 좁혀졌습니다. 그러나 2까지는 아직 도달하지 못했죠. 골드바흐 추측은 1742년 골드바흐가 오일러에게 보낸 편지에서 나온 것으로, 2보다 큰 모든 짝수는 두 소수의 합이라고 주장합니다. 컴퓨터로 4 × 10¹⁸까지 확인됐지만 증명은 없습니다. 검증 사례가 아무리 쌓여도 증명이 아니라는 것, 이것이 수학과 경험과학의 경계입니다.
이 "쓸모없어 보이는" 질문들이 어떻게 인터넷 보안의 기반이 되는지는 4강에서 다룹니다. 그 전에 2강에서 나머지의 수학, 모듈러 산술을 먼저 익힙니다.
인출 문제
생각해볼 질문 (정답 없음)
- 유클리드의 증명은 새로운 소수를 하나도 만들어 보이지 않고도 무한을 확정합니다. 존재를 보이는 것과 예시를 제시하는 것은 어떻게 다를까요?
- 쌍둥이 소수 추측처럼 초등학생도 이해하는 문제가 수백 년째 안 풀리는 것은 수학의 결함일까요, 수의 세계가 원래 그렇게 깊다는 증거일까요?