소수: 수학자들이 사랑한 수 (1)

소수와 에라토스테네스의 체

소주 한 병을 소주잔에 따르면 7잔 (정확히는 7.5잔)이 나온다는 이야기가 있다. 흔히들 행운의 숫자라 불리지만 술자리에서 7은 반가운 수는 아니다. 두 명으로 나눠도, 세 명으로 나눠도, 7은 깔끔히 나눠떨어지지 않는다. 왜 그럴까? 그것은 7을 나눌 수 있는 수가 오직 1과 7, 자기 자신 뿐이기 때문이다. 그렇게 한 병 비우고 나면, 우리는 어쩔 수 없이 손을 들며 외친다. “이모, 소주 한병 추가요!”

소수는 아주 오래전부터, 그러니까 문명이 형성되고 수학이 태동했을 때부터 흥미의 관심사였으리라 추측한다. 소수에 대한 흥미, 아니 집착은 아주 간단한 질문에서 비롯되었다.
 

왜 어떤 수들은 1과 자기 자신으로만 나눠질까?

예를 들어, 4는 1, 2, 4로 나뉜다. (이때 1, 2, 4를 4의 '약수'라고 부른다.) 반면 5의 약수는 1과 5 자기 자신뿐이다. 6 역시 1, 2, 3, 6 등의 약수를 갖지만, 7은 1과 7 자신밖에 약수가 없다. 5와 7처럼 1과 자기 자신으로만 나뉘는 숫자를 소수(prime number)라고 부른다. 반면 4와 6처럼 그렇지 못한 숫자들은 합성수(composite number)라 부른다. 소수도 합성수도 되지 못한 단 하나의 수가 있다. 1이 바로 그것이다. 정의만 따른다면 1은 소수로 불려 마땅해 보이지만, 수학자들은 1을 소수로 취급하지 않기로 하였다.
 

소수에 대한 다양한 이야기를 펼치기에 앞서, 먼저 소수를 구하는 방법을 소개해볼까 한다. 에라토스테네스의 체(Sieve of Eratosthenes)라는 이름의 이 방법은, 아주 간단한 산수만을 이용해 소수들을 구하는 쉽고 간단한 알고리즘이다. 이를 이용해 50 이하의 모든 소수를 찾아보자. 우선 1부터 50까지의 수를 적는다.
 

 

첫 단계로, 1을 제외한다. 정의상 1은 소수가 아니기 때문이다.

다음으로, 2를 제외한 모든 2의 배수를 제거한다. 이 과정을 거치면 다음과 같은 표가 남는다.
 

그다음은 3을 제외한 3의 배수를 제거한다.

그 뒤로도 5를 제외한 모든 5의 배수, 7을 제외한 7의 배수를 제거해 나간다. 이후에도 11, 13,…에도 같은 과정을 반복할 수 있지만, 사실 7의 배수를 제거하는 시점에서 표에 남아 있는 합성수는 더 이상 없다. 최종적으로 우리는 다음과 같은 표를 얻을 것이다. 이 표의 ‘생존자’들은 모두 소수이다.

직접 에라토스테네스의 체를 그린 부지런한 독자분들은 눈치챘겠지만, 숫자가 커질수록 소수의 분포는 희박해진다. 예를 들어, 11이 소수인지 아닌지 알아보려면 11보다 작은 숫자로 나누기를 시도해 보면 알 수 있다. 반면 101이 소수인지 확인하려면, 101보다 작은 모든 숫자로 일일이 나눠봐야 한다. 즉 숫자가 커질수록 확인해야 할 약수 후보가 많아지기 때문에 소수가 될 확률은 점점 줄어든다. (각주 [1] 참고.) 그렇다면 언젠가 소수가 완전히 사라지는 지점이 있지 않을까? 어쩌면 가장 큰 소수라는 것이 존재하지 않을까?

[1] 엄밀히 말하면 “확률”이라는 표현은 부적절하다. 소수가 되는 것은 동전 던지기처럼 무작위적인 사건이 아니라 이미 결정된 사실이기 때문이다. 그럼에도 임의의 수가 '소수일 확률'을 통계적으로 구할 수 있는데, 이러한 방법론을 크레이머 모델(Cramér's model)이라 한다.