Howmany Prime

소수가 정의 되었으니, 그렇다면 소수들을 모아보자. 소수는 어떤 어떤 성질을 갖는 걸까? 그리고 자연수 세계에서 어떤 역할을 하는 것일까? 소수가 제 아무리 많아도 유한개라면 우리가 소수를 찾는 알고리듬이라든가, 소수의 어떤 성질을 찾는 것은 간단해진다. 그렇다면 주어진 자연수의 약수를 구하는 것도 간단해지고 자연수들끼리 나뉨 관계로 비교해보는 것도 간단해진다. 자연수 세계의 비밀이 한꺼풀 벗겨질 수 있다. 과연 자연수가 그리 호락호락 할까 ?

소수들은 개수는 몇 개나 될까?

소수의 개수는 몇 개나 되는데 무한개 많은 모든 자연수를 다 표현할 수 있을까? 이 문제에 대해 '설마 유한개 일까? 자연수가 한없이 많이 있으니까 그 중에 소수가 나타나겠지’라고 지레 짐작할 수 있다. 또는 ‘상상할 수 없이 큰 자연수를 소수로 쪼개다 보면 큰 소수가 등장할 수밖에 없을 거야. 자연수가 커지면 커질수록 소수도 커질 수 있겠지.’ 라고 짐작할 수도 있다. 수학에서 '짐작'은 소중한 것이지만 그것을 논리적으로 근거를 달지 않으면 수학이 아니다.

이렇게 말했다고 하자.

‘만약 소수가 끝이 있다 해보자. 그 모두를 곱하자. 자연수는 끝이 없으니 그 모두 곱한 수보다 더 큰 자연수가 있을 것이다. 그 수는 소수의 곱으로 나누어지지 않을 것이다. 그래서 소수가 된다. 그러면 유한개의 소수 중 가장 큰 것보다 더 큰 소수가 있다는 말이기 때문에 이건 말이 안 되는 것이다. 그래서 소수의 개수는 한없이 많다.’

자 어떤가? 이건 훨씬 상상력이 풍부하고 더 나름대로 논리가 있다. 빈틈없는 논리인가? 물론 아니다. (위에서 한 말에는 어디가 문제가 있는가?)

도대체 어디에 문제가 있을까? 우리는 앞에서도 말하였지만, 어떤 자연수를 소수의 곱으로 표현하기 위해 등장하는 소수가 꼭 한 번씩만 나와야 할 이유가 없다. 12만 하더라도 2, 2, 3 으로 표현되어 소수 2가 두 번 등장하게 된다. 따라서 유한 개의 소수를 가지고 그것이 표현할 수 있는 가장 큰 자연수가 어딘가에 있다고 말할 수 없다. 논리전개에 구멍이 뚫려 있었고 결론이 성급했다. 그렇다고 해서 그 추론이 전혀 의미 없는 것일까? 그렇지 않다. 거의 다가가다가 소홀해서 함정에 빠졌을 뿐이다. 조금만 조심하면 논리적 결함을 말끔하게 없앨 수 있다.

소수들은 끝없이 많다

소수는 끝없이 많다. 다른 말로 하면 어떤 소수보다 더 큰 소수가 있다. ^[1] 이제 우리가 여기서 보고자 했던 핵심, 그것을 문장으로 적어보자.

정리 : 자연수에는 소수가 끝없이 많이 있다.

증명을 여럿 볼 것이다. 정리를 아는 것은 물론 재미있는 일이지만, 같은 정리를 여러가지로 증명할 수 있다는 것은 수학적 의미나 중요성에다, 그 자체로 신나는 일이다! 피타고라스 정리 처럼, 기초적이고 중요한 정리들에 대해 증명하는 방법이 많은 경우는 수학에서 그리 드물지 않다. 새롭고 반짝이는 생각으고 간명하게 해 낸 증명은 아름다움을 느끼게도 한다.

소수의 무한성 증명 : 유클리드 '원론'의 증명

가장 고전적인 증명을 먼저 살펴보자. 이 증명은 유클리드의 유명한 책 원론 ^[2] 에 담긴 내용이다. 이 증명은 자연수와 나눗셈에 대한 통찰이 엿보이는 멋진 증명이다. 먼저 다음 수들을 보자.

2,4,6,8,\cdots

이는 모두 2의 배수다. 2k 꼴이다. 이 수들 다음 수인 2k+1 꼴의 수는 홀수고 따라서 2로 나뉘지 않는다. 그리고

3,6,9,12,\cdots

3의 배수인 이 수들에 대해서도 3k+1 꼴의 수는 3으로 나뉘지 않는다. 5의 배수, 7의 배수, 11의 배수도 마찬가지다.

이 점에 주목해 유클리드는

2\cdot 3+1

2\cdot 3\cdot 5+1

2\cdot 3\cdot 5\cdot 7+1

2\cdot 3\cdot 5\cdot 7\cdot 11+1

2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1

\ldots

처럼 소수들을 곱한 수들에 그 다음 수를 만들었다. 그렇다면 첫번째 수는 2의 배수 다음 수이고 3의 배수 다음 수 이니, 2와 3으로 나뉘지 않을 것이고, 두번째 수는 2, 3 과 5의 배수들의 다음 수이니 2, 3 과 5로 나뉘지 않을 것이고, 이런 상황은 계속된다. 그렇다면 이 수들이 모두 소수일까? 처음부터 차례대로 이 수는 7, 31, 211, 2311, 30031, ... 이다. 처음 넷은 소수지만,

2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30031=59\cdot 509

로 두개 의 소수로 나뉜다. 그런데, 이런 식으로 만들어가는 수는 비록 새로운 소수가 아니어도 이 수를 만들기 위해 참여했던 소수 어떤 것으로도 나뉘지 않는 것은 분명하다. 이제 말끔하게 증명할 준비가 충분히 되었다.

유클리드의 증명 : 간접 증명

앞에서 보았듯, 표 왼쪽에 있는 수는 표 오른쪽 같은 줄에 있는 수들로 나누어지지 않는다.

$2+1$		$2$
$2\cdot 3+1$		$2,3$
$2\cdot 3\cdot 5+1$		$2,3,5$
$2\cdot 3\cdot 5\cdot 7+1$		$2,3,5,7$
$2\cdot 3\cdot 5\cdot 7\cdot 11+1$		$2,3,5,7,11$

소수가 유한개라 하자. s 개라 하고 $p_{1},p_{2},\cdots ,p_{s}$ 로 나타내자.
그것들을 모두 곱해서 1을 더한 수 $p_{1}\cdot p_{2}\cdots p_{s}+1$ 를 보자.
이 수는 가장 큰 소수 $p_{s}$ 보다 크니 소수가 될 수 없다. 합성수다.
합성수이니까 소수로 나누어져야 한다. 그런데 앞의 예에서 보았듯이 이 수는 $p_{1},p_{2},\cdots ,p_{s}$ 중 어느 소수로 나누어도 항상 나머지가 1이다. 나누어지지 않는다. 말이 안된다. 유한개의 소수만 있다는 말을 버려야 한다. 증명 끝.

유클리드 증명의 수정 : 직접 증명

처음부터 s개의 소수들 $p_{1},p_{2},\cdots ,p_{s}$ 곱해가자. 그리고 거기다 1을 더해 m 이라고 한다.

m:=p_{1}\cdot p_{2}\cdots p_{s}+1

m 은 소수거나 합성수다.

만약 m이 소수라면 '새로운' 소수가 있는 것이다. 따라서 소수는 끝이 없다.
만약 m이 합성수라면, 정의에 따라 소수의 곱으로 표현할 수 있다. 예를 들어,

m=q_{1}\cdot q_{2}\cdot q_{t}

$p_{1},p_{2},\cdots ,p_{s}$ 들 어느 것도 m을 나눌 수 없으므로 이 소수들 $q_{1},q_{2},\cdots ,q_{t}$ 은 '새로운' 소수다. ^[3] 처음부터 s 개의 소수들로 부터 새로운 소수가 등장한다. 소수는 끝이 없다. 증명 끝.

유클리드 증명 속에 담긴 뜻

유클리드 '원론'에서 보인 증명은 기본 생각이 아주 간결하다는 점에서 매력적이다. 이에 대해 잠시 멈추어 더 생각해보도록 하자.

이 증명의 밑바탕에는 어떤 생각이 자리하고 있을까? 이 증명에서 고대 그리스 사람들이 소수의 무한성을 탐구하는데 있어 대단히 ‘겸손하였다’는 것을 미루어 볼 수 있다. 소수를 모두 찾아내면서 그 성질을 뒤지면서 소수가 끝이 없다는 식으로 증명을 시도한 것이 아니라는 것이다. (어쩌면) 처음부터 소수의 개수가 끝이 있을 것이라는 생각 자체를 포기했던 것 같다. 소수가 유한개라고 가정하고 그럴 때 논리적 모순을 나온다고 유도함으로써 '끝없이 많다'를 보이려는 헛수고를 피해갔다. 고대 그리스 현자들은 지금의 많은 수학자들이 그렇듯 소수의 구성이 대단히 복잡하다고 생각했을 수 있다. 따라서 그것 전체를 아우를 어떤 법칙을 찾기를 처음부터 포기했는지도 모른다.

그런데 위의 증명에서 ‘모든 수를 곱한 다음 하나 더하기’, 곧, +1은 본질적으로 중요한 역할을 할까? 다른 수면 안될까? 다른 수가 가능하다면 어떤 수가 가능할까? (스스로 찾아보라.)

증명이 파생하는 중대한 문제 : 어떤 범위 안에 소수는 몇 개 일까? 로

유클리드의 책에 있는 증명은 새로운 문제를 파생시켰다. 수학이란 정리를 내고 증명해서 문제를 완결하는 경우보다 알고 있는 것으로부터 새로운 궁금증을 발견하거나 새로운 문제를 창안하고 논리적으로 해결해가는 과정이라고 할 수 있다. 끝없는 탐구 의욕과 상상력으로 떠나는 여정인 것이다. 유클리드의 책에 있는 증명은 어떤 문제를 더 생각하게 할 수 있나 ? 다음을 보도록 하자.

2\ =\ 2^{1}

3\ <\ 2^{2}

5\ <\ 2^{4}

7\ <\ 2^{8}

...

이고 만약 $p_{k}<2^{2^{k-1}}$ 라면 $p_{k+1}<2^{2^{k}}$ 라는 것을 보일 수 있다. 따라서 일반적으로

p_{k+1}\leq p_{1}\cdot p_{2}\cdots p_{k}+1<2^{1+2+4+8+\cdots +2^{k-1}}=2^{2^{k}-1}+1<2^{2^{k}}

이 성립한다. 이로부터 다음을 보일 수 있다. (로그에 익숙한 사람은 스스로 확인해보라.)

\pi (n)\leq \log _{2}\log _{2}n+1

앞에서 $\pi (n)$ 은 n 보다 작은 소수의 개수다. 이제 새로운 문제가 제기되는 셈이다. ‘어떤 자연수 n 보다 작은 소수의 개수는 몇 개일까?’라는 문제와 연관된다. 바로 문제로 남긴 문제에서 $\pi (n)$ 를 찾는 문제다. 과연 그것을 정확히 찾을 수 있을까? 정확히 찾을 수 없다면 더 정확한, 다시 말해 앞의 문제에서 오른쪽 항의 식이 진짜 $\pi (n)$ 에 더 접근하는 그 무엇은 ? 이라는 문제다.

\pi (n)\leq f(n)\leq \log _{2}\log _{2}n+1

에서 더 좋은 f(n) 을 찾는 문제로 새로운 길이 터나가는 셈이다. 이는 더 나아가 전체 자연수에서 소수는 얼마나 자주, 또는 얼마나 듬성듬성 나올까 라는 문제를 파생한다.

소수의 무한성 : 다른 증명들

자연수 안에 소수가 끝없이 많이 있다는 것은 이미 증명되었음에도 불구하고 그 후로 여러 증명이 나왔다. 이 증명들은 저마다 증명의 특징이 있고 수학적 의미가 다르다. 여기 그 중 몇가지를 싣는다.

Note

↑ '무한'이라는 것은 아직 막연하다. 제논의 역설 이후 이 '무한'이라는 말을 조심해서 쓰거나 아예 쓰지 않았다고 한다. 그래서 유클리드가 자연수나 소수에 대하여 ‘무한’의 개념을 쓸 때는 언제나 ‘어떤 수보다 더 큰 수가 있다.’와 같은 문장을 썼다. 무한과 제논의 역설에 대해서 이상한 무한의 세계 1 를 참고하라.
↑ 유클리드의 원론 : 영어로는 'Elements'로 번역되고 우리말로는 '원론'으로 번역되는데 '시작'이라고 할 수도 있고 '기초'라고 할 수도 있다. 원론이라는 번역보다 '시작'이나 '기초'가 나아보인다. 당시 고대 그리스의 수학은 자연수에 대한 신비로운 생각을 정리해놓은 자연수론 분야와 기하학 분야였는데 특히 '공리적 체계'를 도입하여 순수하게 논리적으로 사고하여 새로운 수학적 사실을 발견해가는 방법을 도입하였다. 유클리드가 고대 그리스의 수학적 성과를 집대성하면서 나름대로 새로운 증명을 보탠 것으로 추정하고 있다. '공리적 체계'와 유클리드 공리 체계에 대해서는 공리적 체계를 참고하라.
↑ 이때 ' $p_{i}$ (여기서 i = 1, 2 ... ,s) 는 $q_{1}\cdot q_{2}\cdots q_{t}$ 를 나눌 수 없으므로 $p_{i}$ 는 $q_{j}$ (여기서 j = 1, 2 ... ,t) 는 다르다' 라고 한 부분은 의심할 바 없이 명확한가? 합성수를 소수들의 곱으로 나타내는 방법과 위의 질문과 관련하여 산술의 기본정리을 보라.

[1] '무한'이라는 것은 아직 막연하다. 제논의 역설 이후 이 '무한'이라는 말을 조심해서 쓰거나 아예 쓰지 않았다고 한다. 그래서 유클리드가 자연수나 소수에 대하여 ‘무한’의 개념을 쓸 때는 언제나 ‘어떤 수보다 더 큰 수가 있다.’와 같은 문장을 썼다. 무한과 제논의 역설에 대해서 이상한 무한의 세계 1 를 참고하라.

[2] 유클리드의 원론 : 영어로는 'Elements'로 번역되고 우리말로는 '원론'으로 번역되는데 '시작'이라고 할 수도 있고 '기초'라고 할 수도 있다. 원론이라는 번역보다 '시작'이나 '기초'가 나아보인다. 당시 고대 그리스의 수학은 자연수에 대한 신비로운 생각을 정리해놓은 자연수론 분야와 기하학 분야였는데 특히 '공리적 체계'를 도입하여 순수하게 논리적으로 사고하여 새로운 수학적 사실을 발견해가는 방법을 도입하였다. 유클리드가 고대 그리스의 수학적 성과를 집대성하면서 나름대로 새로운 증명을 보탠 것으로 추정하고 있다. '공리적 체계'와 유클리드 공리 체계에 대해서는 공리적 체계를 참고하라.

[3] 이때 ' $p_{i}$ (여기서 i = 1, 2 ... ,s) 는 $q_{1}\cdot q_{2}\cdots q_{t}$ 를 나눌 수 없으므로 $p_{i}$ 는 $q_{j}$ (여기서 j = 1, 2 ... ,t) 는 다르다' 라고 한 부분은 의심할 바 없이 명확한가? 합성수를 소수들의 곱으로 나타내는 방법과 위의 질문과 관련하여 산술의 기본정리을 보라.

[1]

[2]

[3]