오늘은 유클리드 원론에서 가장 간단 명료한 증명으로 알려진 소수의 무한성에 대한 증명을 소개해 보겠습니다.
유클리드 원론 9권 명제 20의 내용은
소수의 개수는 무한하다. 정확하게는 유한하지 않다. 즉,
유한 개의 소수가 있으면 새로운 소수를 발견할 수 있다.입니다.
유클리드는 세 개의 소수를 예로 들어 설명하면서 새로운 소수가 존재해야 함을 증명하고 있습니다. 유클리드의 증명법을 일반화하면 간단하게 다음과 같습니다.
여러 개의 유한한 소수들이 있다. 이들의 최소공배수를 구한다.
여기에 단위수를 더하자. 그렇다면
이 새로운 수는 소수이거나 합성수일 것이다.
소수라면 목록에 없는 새로운 소수이다.
합성수라면 이 수의 소인수 중에 하나를 아무거나 생각한다. 이것이 처음에 주어진 소수 중에 하나라면 그 소수는 처음의 최소공배수와 그 최소공배수 더하기 단위수를 동시에 나누어야 하니 즉 단위수를 나누어야 한다. 모순이다. 즉 그 소인수는 주어진 소수의 목록에는 없는 소수이다.
유클리드가 말했던 방법을 다른 관점에서 해석하면 다음과 같습니다.
소수들이 있을 때 그 소수들로 나눈 나머지가 모두 1인 수를 찾는다.
소수들을 모두 곱한 후에 1을 더하면 목록에 있는 어떤 소수로 나누어도 나머지는 1입니다.
이 영상에서는 이 부분을 살짝 바꾸어서 새로운 방법을 제시해 보겠습니다.
나머지를 바꾸어보는 방법입니다. 나머지가 꼭 1일 필요는 없습니다. 나누어 떨어지지만 않는다면 나머지가 어떤 수여도 상관없이 새로운 소수를 찾는 열쇠가 될 수 있습니다.
그런데 이 방법과 관련해서는 다음의 문제를 먼저 이야기해야 합니다. 바로
중국인의 나머지 정리
라고 알려진 문제입니다. 이 문제는 5세기 중국 남북조 시대의 수학서 《손자산경》(孫子算經)이라는 책에 최초로 등장합니다. 《손자산경》 하권(下卷) 3장 문제 26번입니다.
개수를 알지 못하는 것들이 있다. 셋씩 센다면 두 개가 남고, 다섯씩 센다면 세 개가 남고, 일곱씩 센다면 두 개가 남는다. 질문: 총 몇 개인가?
정답: 23개.
풀이: 셋씩 세어 두 개가 남으면, 140을 적는다. 다섯씩 세어 세 개가 남으면 63을 적는다. 일곱씩 세어 두 개가 남으면 30을 적는다. 이들을 더해 233이 되고, 210을 빼면 정답을 얻는다. 마찬가지로, 셋씩 세어 한 개가 남으면 70을 적는다. 다섯씩 세어 한 개가 남으면 21을 적는다. 일곱씩 세어 한 개가 남으면 15를 적는다. 합이 106보다 더 크므로, 105를 빼면 정답을 얻는다.
이 책의 저자에 대해서는 알려진 바가 없습니다만, 손자의 설명에는 증명이나 일반적인 문제 해결의 방법이 포함되어 있지 않습니다. 처음에 왜 140이나 63, 30 을 이용하였는지 알 수는 없지만 아마도 이 수들은 각각 5곱하기 7의 배수이며 3으로 나누어서 나머지가 1인 수인 70, 7 곱하기 3의 배수이며 5로 나누어 나머지가 1인 수인 21, 3 곱하기 5의 배수이며 7로 나누어 나머지가 1인 수인 15에서 각각 얻어진 듯 합니다. 놀랍게도 이 방법을 그대로 이용하여 증명을 완성할 수 있습니다. 현대의 정수론 교재에서도 바로 이 방법을 사용합니다. 놀랍죠?
그럼 이 중국인의 나머지 정리를 이용하여 새로운 소수를 찾아보겠습니다. 새로운 소수를 찾아보면서 소수의 무한성을 직접 확인해 보겠습니다.
하지만 손자의 방법보다 좀 더 단순하고 기초적인 방법으로 답을 구해보도록 하죠.
예를 들어 보겠습니다.
소수가 2,3,5,7로 주어져 있다고 해보죠. 각각 나머지를 1,2,3,4로 정합니다. 이 수를 찾아보겠습니다. 나머지가 0만 아니라면 어떤 것이든 상관없습니다. 먼저 2로 나누어 나머지가 1인 수들을 차례로 나열합니다.
1,3,5,7,9, 11,…
이중에서 3으로 나누어 나머지가 2인 수를 찾습니다.
5, 11, 17,23, 29, 35,….
6(=2 곱하기 3)으로 나누어 나머지가 5인 수들입니다. 다시 여기에서 5로 나누어 나머지가 3인 수를 찾습니다.
23, 53, 83,…
30(=2 곱하기 3 곱하기 5)로 나누어 나머지가 23인 수입니다. 53이 바로 7로 나누어 나머지가 4인 수군요.
다행히 53은 그 자체가 소수입니다.
만약 나머지가 1, 2,3,3이라면 어떨까요?
23, 53, 83,113,143,…
143이네요. 소수는 아닙니다.
11 곱하기 13입니다. 그런데 모두 처음의 소수 목록에 없었던 소수들입니다.
이런 방식으로 새로운 소수가 있다는 주장을 할 수 있습니다. 2로 나눈 나머지를 1로, 3으로 나눈 나머지를 1,2로, 5로 나눈 나머지를 1,2,3,4로, 7로 나눈 나머지를 1,2,3,4,5,6으로 정하면 모두 1곱하기2곱하기4곱하기6=48경우를 조사할 수 있습니다.
어떤 수의 배수들은 매우 규칙적으로 나타납니다. 그런 관점에서 소수는 비규칙성의 상징입니다. 소수의 무한성은 그러한 비규칙성들이 반드시 나타날 수 밖에 없음을 뜻합니다. 이 방법들은 소수의 무한성에 대한 아주 단순한 증명입니다.
중국인의 나머지 정리를 이용한 접근은 유클리드의 접근법을 조금 체계적으로 바꾸어 본 방식인데, 두 방법 모두 두 가지 점에서 아쉬움이 남습니다.
한 가지는 새롭게 얻어진 수가 소수인지 아닌지는 미리 알 수 없다는 점입니다.
또 한 가지는 얻어진 수가 너무 크다는 점입니다.
예를 들어보겠습니다. 2,3,5,7,11,13이라는 6개의 소수목록이 주어져 있습니다.
유클리드의 방법으로는 2곱하기3곱하기5곱하기7곱하기11곱하기13+1=30031이 얻어집니다. 59곱하기509네요.
중국인의 나머지 정리를 이용하기 위해서 나머지를 차례로 1,2,3,4,5,6이라고 해 볼까요?
53,263,473,893,1103,1313,1523,…
1523, 3833,6143,8453,10763,13073,15383,17693,20003,2231324623,26933,29243,…
29243입니다. 다행스럽게도(?) 소수네요.
나머지를 잘 정하면 좀 더 작은 수를 얻을 수 있지 않을까요? 쉽지 않습니다.
다음 영상에서는 소수무한성을 바라보는 보다 새로운 관점, 보다 현대적인 관점을 소개하겠습니다.
<<쇼츠>> 소수의 무한성에 대한 증명은 이미 유클리드가 원론에서 제시했습니다. 유클리드의 방법을 조금 변형해 보겠습니다. 어쨌든 이미 주어진 소수들을 이용해서는 나누어질 수 없는 수를 찾으면 되는 거니깐요~ 첫 6개의 소수로 예를 들어 보겠습니다.
방법은 두 모듬으로 적당히 나누어 각각 곱한 후에 더하거나 빼는 방식입니다.
2곱하기 7 곱하기13 더하기 3곱하기 5곱하기11 을 생각합니다. 7로 나누어 볼까요? 앞부분은 나누어지지만 뒷부분은 나누어지지 않습니다. 다른 소수도 모두 마찬가지로 나누어지지 않습니다. 결과는 347 소수입니다.
2곱하기 7 곱하기13 빼기 3곱하기 5곱하기11= 17 소수입니다.
목록에 있는 소수들로 나누어지지 않는 수는 항상 찾을 수 있고 그러한 수를 찾는다면 새로운 소수가 등장할 수 밖에 없습니다.