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

소수의 무한성과 유클리드의 증명

앞서 우리는 '귀류법'이라는 오래되었지만 든든한 무기를 손에 넣었다. 하지만 이 무기 하나로는 소수의 무한성을 증명하기에 역부족이다. 귀류법은 적진을 무너뜨리는 최후의 무기, 폭탄과도 같은 존재다. 그것만 믿고 전진에 뛰어든다면 예상치 못한 조무래기에게 당할 수 있다. '자연수가 무한히 많음'을 증명할 때는 'x가 자연수라면 x+1도 자연수'라는 무기로 충분했지만, 소수의 무한성을 보이려면 더욱 정교하고 세련된 무기가 필요하다.

그럼 먼저 몇 가지 수학 용어부터 정립하자. 정수(integer)는 …, -3, -2, -1, 0, 1, 2, 3, … 처럼 소수점 없이 딱 떨어지는 수들을 말한다. 임의의 두 정수를 취해보자. 가령 5와 7이라 하면, 그것의 합은 12, 차는 -2, 곱은 35가 되어 모두 정수가 된다. 꼭 5와 7일 필요는 없다. 어떤 두 정수를 취하더라도, 그 합, 차, 곱은 언제나 정수가 된다. 이러한 성질을 두고 '정수는 덧셈, 뺄셈, 곱셈에 닫혀있다'라고 한다. 하지만 정수는 나눗셈에는 닫혀있지 않다. 5를 7로 나눈  5/7은 더 이상 정수가 아니기 때문이다. (각주 [1] 참고.)

소수를 정의할 때, 우리는 '나눈다'라는 말을 사용했다. 예컨대 4는 2로 나뉜다, 5는 2로 나뉘지 않는다, 5는 소수이기에 1과 5로만 나뉜다 등의 표현을 자연스럽게 사용해 왔다. 하지만 누군가는 이렇게 반문할 수 있다. "왜 5가 2로 안 나뉘어? 5/2=2.5잖아?" 이처럼 '나누다'라는 너무나 당연하고 친숙한 단어조차 엄밀한 정의가 필요하다!

정의: 정수 a와 b를 가정하자. 만약 b=ax를 만족하는 정수 x가 존재한다면, 'a는 b를 나눈다'라고 말한다. (이를 a | b라 표기한다.) 

이 정의를 기반으로 다음의 사실들을 유도할 수 있다.   

• 3은 6을 나눈다. 6 = 3x를 만족하는 정수 x가 존재하기 때문이다. 그리고 그러한 정수 x는 2이다.
• 3은 5를 나누지 못한다. 5 = 3x를 만족하는 정수 x는 존재하지 않기 때문이다.
• 3은 0을 나눈다. 0 = 3x를 만족하는 정수 x가 존재하기 때문이다. 그러한 정수 x는 0이다.
• 3은 -3을 나눈다. -3 = 3x를 만족하는 정수 x가 존재하기 때문이다. 그러한 정수 x는 -1이다.

사족을 달자면, 임의의 정수 x가 2로 나뉜다면 (즉, 2 | x라면), 우리는 x를 짝수라고 부른다. 이 정의에 기반하면 -2도 0도 짝수로 분류된다.

과학에서는 입증된 중요한 사실을 법칙(Law)이라 부른다. 수학에서는 이를 정리(Theorem)라 부른다. 두 학문의 차이는 과학이 경험과 실험으로 법칙을 입증하는 반면, 수학은 정의와 논리로 정리를 증명한다는 점이다. 위대한 정리는 허공에서 뿅 하고 나타나지 않는다. 멋진 성을 쌓기 위해 투박하지만 단단한 초석이 필요하듯, 아름다운 정리를 증명하는 데에도 작고 자잘한 사실들이 필요하다. 이러한 사실을 소정리(lemma)라 부른다. 소수의 무한성을 증명하기 위해선 다음의 소정리가 필요하다.

소정리: 정수 a, b, c를 가정하자. 덧붙여 a가 b와 c를 나눈다고 가정하자. 그렇다면 a는 b-c 또한 나눈다.

이 성질이 참인지 여러 가지 구체적인 예시를 통해 직관을 쌓아보자. 예를 들어 3은 15를 나누고, 21도 나눈다. 15 = 3x와 21 = 3y를 만족하는 정수 x와 y, 곧 5와 7이 존재하기 때문이다. 15와 21의 차이는 -6이며, 역시 -6 = 3z를 만족하는 정수 z, 곧 -2가 존재한다. 직관은 우리에게 이 소정리가 참일 것이라고 속삭인다. 하지만 엄밀한 수학의 세계에서는 각각의 예시는 ‘특별한 경우’에 불과하다. 이 성질이 모든 정수에 대해 보편적으로 성립함을 보이려면 증명해야만 한다.

증명: b와 c는 a로 나뉘므로, 정의에 의해, b = ax와 c = ay를 만족하는 정수 x와 y가 존재한다.

그러므로 b-c = ax - ay = a(x-y)이다.

x와 y가 정수이며, 정수는 뺄셈에 닫혀있으므로 x-y 또한 정수이다.

그러므로 b-c = az를 만족하는 정수 z는 존재하며, 그러한 z는 x-y이다.

이로써 b-c는 a로 나뉨을 보였다. 증명 종료. (각주 [2] 참고.)

드디어 우리는 소수가 무한히 많다는 사실을 증명할 준비가 되었다. 귀류법을 사용할 것이니, 먼저 우리의 주장하는 바의 반대 상황을 가정하자.

증명: 소수가 무한히 많지 않다고 가정하자. 그렇다면 가장 큰 소수 P가 존재할 것이다. M을 2×3×5×...×P라 정의하자. 즉 M은 모든 소수로 나뉜다.

M+1이란 수를 보자. 산술의 기본정리에 의해 M+1은 소수이거나 합성수다. 

M+1은 소수가 될 수 없다. M+1은 P보다 크며, P가 가장 큰 소수라 했기 때문이다. 

M+1이 합성수라 하자. 그렇다면 M+1을 나누는 소수 Q가 존재한다. P가 가장 큰 소수니, Q는 P 이하여야 한다. 

즉 Q는 2, 3, 5,..., P 중 하나이며, M의 정의상 Q는 M도 나눈다. 

그러므로 Q는 M과 M+1을 나눈다. 소정리에 의해 Q는 (M+1)-M=1도 나눠야 한다. 하지만 소수는 1을 나눌 수 없다! 

'소수는 무한히 많지 않다'는 가정은 모순을 낳는다. 그러므로 소수는 무한히 많다. 증명 종료.

친근한 예시를 들어 이 증명의 핵심을 들여다보자.

세상의 소수가 2와 3 뿐이라 가정하면 M+1은 7이 된다. 7은 3보다 더 큰 소수이니, 우리의 가정은 모순을 낳는다.

세상의 소수가 2, 3, 5 뿐이라면, M+1은 31이 된다. 31은 5보다 더 큰 소수이니, 역시 모순을 낳는다.

세상의 소수가 2, 3, 5, 7, 혹은 2, 3, 5, 7, 11 뿐이라 가정하면 M+1은 211과 2311이 되며 이들은 소수다. 역시 7과 11보다 큰 소수이니 모순을 낳는다. 성급한 독자는 “M+1은 항상 소수네!”하고 그릇된 결론을 내릴지도 모른다. (각주 [3] 참고.)

세상의 소수가 2, 3, 5, 7, 11, 13 뿐이라 가정하면 M+1은 30,031인데, 이는 합성수이다. 하지만 2, 3, 5, 7, 11, 13 중 어느 것도 30,031을 나누지 못한다. 30,031의 소인수분해는 59x509이며, 각각은 13보다 큰 소수이니, 역시 모순을 낳는다. 즉 M+1이 합성수라 할지라도, 그 소인수는 우리가 가정한 ‘가장 큰 소수’보다 더 커야 한다.

이 증명은 기원전 300년경 유클리드의 원론(Elements)에도 등장하는 유서 깊은 것이다. (각주 [4] 참고.) 수학이 발전하며 소수의 무한성은 여러 방법으로 증명되었지만, 이토록 아름답고 쉬운 증명은 없었다. 감히 말하자면 가장 탁월한 증명이고, 앞으로도 이보다 탁월한 증명은 없을 것이다.

필자의 기준으로 버금가는 아름다운 증명은 오일러의 증명이다. 오일러는 소수의 역수의 합이 무한으로 발산한다는 사실을 보였다. 다시 말해 다음을 밝혔다는 뜻이다. (각주 [5] 참고.)

1/2 + 1/3 + 1/5 + 1/7 + … = ∞.

각 값, 즉 1/2, 1/3, 1/5는 모두 1보다 작다. 소수가 유한개뿐이라면, 1보다 작은 값을 유한번 더해 무한을 만들 수 없다. 그러므로 소수는 무한히 많다. 물론 이 증명이 앞서 소개한 유클리드의 증명보다 더 간결해 보이지만, 이를 완성하려면 소수의 역수 합이 무한이란 사실을 먼저 증명해야 한다. (각주 [6] 참고.)

[1] 연습문제: 그렇다면 자연수는 덧셈, 뺄셈, 곱셈, 나눗셈 중 어떤 연산에 닫혀있을까?

[2] 증명 말미에 '증명이 끝났음'을 알리는 것은 수학의 에티켓이다. 과거에는 Q.E.D.(Quod Erat Demonstrandum)를 써넣곤 했는데 이는 '이것이 보여야 할 것이었다'는 라틴어이다. 하지만 현대에는 매우 유명한 난제의 증명이 아니라면 Q.E.D. 를 사용하지 않으며 대부분 검은 사각형(■) 혹은 흰 사각형(□)을 사용한다.

[3] 인터넷에서 흔히 볼 수 있는 몇몇 증명들은 "M+1이 항상 소수이므로 모순"이라며 마무리하는데, 이는 틀린 논증이다.

[4] 유클리드 원론 제9권 제20번 명제

[5] 엄밀히 말해 오일러는 이를 증명하진 못했다. 수렴과 발산이란 개념은 오일러 사후 약 100년이 지나서야 정립되었기 때문이다. 오일러는 소수의 역수의 합이 무한이어야 하는 이유를 제시했고, 엄밀한 증명은 1874년 메르텐스에 의해 완성되었다.

[6] 오일러의 설명을 이해하려면 적어도 초등정수론을, 메르텐스의 증명을 이해하려면 해석적 수론을 알아야 한다. 짧은 증명이지만 그에 필요한 소정리를 증명하는 과정이 상당히 깊은 수학적 이해를 요구한다.