유클리드의 증명

 

목차

1. 무수히 많은 소수가 존재한다

2. 소수 기계

3. 유클리드의 기계는 모든 소수를 만들어낼 수 있을까요?

---

 

 

 

 

1. 무수히 많은 소수가 존재한다

 

가장 간단한 수는 소위 자연수라 불리는 수입니다. 수를 셀 때 사용하는 1, 2, 3, …, n 말입니다. 그 중에는 자신의 수보다 작은 수의 곱으로 표시할 수 없는 특별한 수도 있습니다. 예를 들면 2, 3, 5가 그렇죠. 하지만 101과 1,234,271도 이에 해당합니다. 이런 수를 소수라고 하고, 소수는 수학의 역사 초기부터 많은 수학자들을 매혹시켰습니다.

 

세상에는 얼마나 큰 소수가 있을까요? 유클리드가 '세상에는 무수히 많은 소수가 있으며, 그러므로 그 중에는 무수히 큰 소수가 존재할 것' 이라는 유명한 증명을 해보인 것은 2,000년도 더 된 일이고, 이 증명의 아이디어는 다음과 같습니다.

 

“유클리드는 임의의 소수를 집어넣을 수 있는 일종의 기계를 상정했다. 여러 개의 서로 다른 소수를 집어넣으면 집어넣은 소수들과 다른 한 소수가 만들어져 나오는 기계다. 그러므로 한정된 수의 소수가 아닌, 알 수 없이 많은 소수가 존재할 것이라는 주장이다.”

 

 

 

그 결과의 파장은 엄청나게 컸으며, 이토록 긴 숫자가 있다는 생각만으로도 아찔해질 것입니다. 예를 들어 유클리드는 이 세상에 존재하는 모든 검은색 잉크를 다 써도 인쇄할 수 없는 소수의 존재를 확신했으며, 이 엄청난 수를 인쇄된 상태로 눈앞에 대할 일은 없을 것입니다. 어쨌든 이제까지 믿을 수 있는 절차를 거쳐 확인된 가장 큰 소수는 사백만 자리에 육박합니다. (이 수가 얼마 나 큰 수인지 상상해 보자. 만약 이 최고기록 보유숫자를 책으로 찍어내면 800 쪽 가까이 된다).

큰 소수는 또한 암호 연구자들에게 큰 관심거리이며, 암호 연구에서는 기껏 해봐야 몇 백 자리만 되는 작은 수가 사용되고 있습니다.

소수의 비밀을 하나 둘씩 벗겨내는 일은 수학자들에게는 여전히 큰 도전이며, 가우스는 이미 오래 전에 이 분야를 ‘수학의 여왕' 이라고 불렀습니다.

---

 

2. 소수 기계

 

유클리드의 소수 기계의 사용설명서를 살펴보면,

 

m개의 소수가 있다. 이것을 p1, p2, …, pn,이라고 부르자. 이것이 너무 추상적으로 느껴진다면 7, 11, 13, 29라는 수를 생각해 보자. 즉 n=4이고, p1=7, p2=11, p3,=13, p4=29이다. 이제 이 소수들을 곱한 뒤 거기에 1을 더 한다. 그리고 그 결과를 m이라고 하면 다음과 같은 식이 나온다.

 

m=p1*p2*(…)*pn+1

 

우리의 예에 적용하면 m=7*11*13*29+1=29030이다.

모든 수는, 즉 m 또한 소수인 인수를 가진다. 이 인수를 p라고 하자.

특이하게도 p는 p1, p2, …, pn,과 다른 수일 수밖에 없다. 왜냐하면 m을 p1, 혹은 p2, 혹은 ··· Pn으로 나누어도 나머지는 1이기 때문이다. (위의 에에서 p=5라고 해보자. 이것은 29,030의 소인수다. 수 5는 정말로 7, 11, 13, 29 중에 들어 있지 않다).

 

 

 

정리 : 주어진 임의의 소수 p1, p2, …, pn을 집어넣으면 '입력'된 수에 들어있지 않은 다른 수가 만들어진다. 그래서 소수의 창고는 무한할 수밖에 없다. 이 기계는 끊임없이 새로운 제품을 내놓는다.

---

 

3. 유클리드의 기계는 모든 소수를 만들어낼 수 있을까요? 

 

처음에는 2가 소수라는 것만 알고 있고, 이 수를 기계 속에 넣으면 3을 얻게 됩니다. 이제 2와 3을 기계 속에 집어넣을 수 있으며, 기계는 7이라는 수를 토해냅니다. 이제 2, 3, 7을 가지고 작업을 계속할 수 있습니다. 이 소수들이 한꺼번에 다 들어있지 않아도 되고 하나가 여러 번 들어 있어도 됩니다. 이렇게 계속하면 언젠가는 모든 소수가 유클리드 기계의 출력 칸에 모습을 드러낸다는 소리일까요?

 

 

 

대답은 ‘그렇다'입니다. 왜냐하면 p가 어떤 소수이든 간에 반드시 서로 다르지 않아도 되는 임의의 소수 p1, …, pr의 곱은 p-1이기 때문입니다.

곧, p1*p2*…*pr+1=p이기 때문에 p1, …, pr을 입력하면 소수 p가 나올 것이며, 이 논증은 ‘수 n보다 작은 모든 소수는 유클리드의 기계에서 만들어진다'는 명제를 n에 따른 연역법으로 증명하는 데 사용할 수 있습니다.