[Euclid's theorem] 소수의 무한성 이해하기 쉽게 증명하기

소수는 무수히 많다

Euclid's theorem 유클리드의 정리

소수(1과 자기 자신으로밖에 나누어 떨어지지 않는 수)는 무한히 존재한다는 정리입니다.

 

소수를 한번 나열해 볼까요?

2,3,5,7,11,13,17,19,23......

소수는 끝없이 나열할 수 있으며, 그 개수는 무한입니다.

 

 

소수가 무한 개라는 것을 과연 어떻게 증명할 수 있을까요?

후술할 산술의 기본정리(Fundamental Theorem of Arithmetic)와

수학적 귀류법(Proof of contradiction)을 이용하여 

직관적이고 쉬운 방법으로 증명할 수 있습니다.

 

듣자마자 패닉이 옵니다.

하지만 내용을 들여다보면 별볼일 없으므로

저의 논리를 그대로 따라오시기만 하면 자동으로 증명이 됩니다.

 

산술의 기본정리(Fundamental Theorem of Arithmetic)

산술의 기본정리는 다음의 의미입니다.

"1보다 큰 모든 정수 n은적어도 한 개 이상의 소수로 나누어 떨어진다."

 

이해를 돕기 위해 예시를 몇 개 들어보도록 하겠습니다.

 

2 > 소수 2로 나누어 떨어진다

3 > 소수 3으로 나누어 떨어진다.

4 > 소수 2로 나누어 떨어진다

5 > 소수 5로 나누어 떨어진다

6 > 소수 2,3으로 나누어 떨어진다

7 > 소수 7로 나누어 떨어진다

8 > 소수 2로 나누어 떨어진다

9 > 소수 3으로 나누어 떨어진다

10 > 소수2와 5로 나누어 떨어진다.

...

 

 

모든 정수를 자세히 보면

해당 정수를 나누어 떨어트리는 소수가 반드시 1개 이상 존재합니다.

 

 

그러므로 모든 정수는 다음과 같이 나타낼 수 있습니다.

 

n이라는 정수를 나누어 떨어트리는 소수가 다음과 같이 존재한다고 할 때

p1,p2,p3,....,pn

정수 n은 다음과 같이 나타낼 수 있습니다.

 

(단 r1,r2,r3 .. rk >= 1)

 

이해를 돕기 위해 아까와 같은 예시를 들어 보겠습니다.

 

2 = 2 ^ 1

3 = 3 ^ 1

4 = 2 ^ 2

5 = 5 ^ 1

6 = 2 ^ 1 * 3 ^ 1

7 = 7 ^ 1

8 = 2 ^ 3

9 = 3 ^ 2

10 = 2 ^ 1 * 5 ^ 1

 

중요한 사실은,

1보다 큰 정수 n을 나누어 떨어 트리는 소수 pk가 반드시 존재한다는 것 입니다.

 

수학적 귀류법을 통한 유클리드 정리 증명

자, 이제 수학적 귀류법을 통해서 Euclid's Theorem을 증명해 보겠습니다.

수학적 귀류법이라니...

수학을 보면 항상 학습 의욕을 떨어트리게 만드는

생소한 용어들이 많은 것 같아요..

도저히 정이 가지 않습니다.

 

 

하지만 그 속을 들여다보면 매우매우 별볼일 없는 경우가 많습니다.

당연한 얘길 수학적 기호를 통해서 도배해서 도대체 무슨 말인지 해석하기 어렵게 되는 경우도 많죠..

하지만 수학적인 언어로 표현하다 보니 그런 것이고,

우리가 그러한 수학적인 언어에 익숙하지 않기 때문에 그런 것입니다.

 

 

수학적 귀류법이 무엇인지를 설명하지 않겠습니다.

다음의 정리과정을 통하여 자연스럽게

"귀류법이 이것이구나!"하고 깨달을 수 있도록 하겠습니다.

따라오기만 하시면 됩니다!

 

본론으로 돌아가서,

소수가 무수히 많다는 사실을 증명해 보도록 하겠습니다.

 

먼저 다음과 같이 가정을 해 봅시다.

 

가정!!

소수는 유한하다.

모든 정수 중 소수는 다음과 같이 한정된 개수만이 존재한다

 

위와 같이 가정을 했을 때,

유한개의 소수 p1, p2, p3, ... pn만이 존재한다고 해 봅시다.

 

그리고 다음 정수를 생각해 봅시다.

N = p1 * p2 * p3 *... * pn + 1

 

아까 산술의 기본 정리에서

모든 정수는 반드시 적어도 한 개 이상의 소수로 나누었을 때 나누어 떨어진다고 하였습니다.

 

N을 모든 소수로 나누어 봅시다.

 

 

N을 p1로 나누면 > 나누어 떨어지지 않음!

N을 p2로 나누면 > 나누어 떨어지지 않음!

N을 p3로 나누면 > 나누어 떨어지지 않음!

N을 p4로 나누면 > 나누어 떨어지지 않음!

...

N을 pn로 나누면 > 나누어 떨어지지 않음!

 

N이라는 정수를 나누어 떨어트리는 소수가 존재하여야 하는데

존재하지 않습니다.(모순점 발견)

 

 

모순점을 발견한 이 시점에서,

저희가 방금 세웠던 가정은 거짓이라는 것을 알게 됩니다!

이것이 바로 수학적 귀류법입니다.

 

어떤 사실을 가정하고 논리를 전개해 나가서

모순에 부딪히면 

비로소 내가 세웠던 가정이 거짓이라는 것을 알게 됩니다

이러한 방식을 통하여 증명을 하는 방법을 수학적 귀류법이라고 합니다.

 

 

수학적 귀류법을 통하여 다음 사실을 알아냈습니다.

"소수는 유한히 많다"는 명제는 거짓이다.

 

그러므로 "소수는 무한히 많다"라는 사실을 증명하게 되었습니다.

 

[추가] 두 번째 증명 -  더욱 더 직관적인 증명과정

공부하는 과정에서 더 좋고 명확한 증명 방법을 찾아서 추가하였습니다.

 

증명하는 방법은 위와 비슷합니다.

먼저 소수가 유한 개(k개) 있다고 가정해 봅시다.

 

소수는 p1,p2,p3,...pk

 

그리고 자연수 n을 다음과 같이 가정해 봅시다.

n = 1 + p1*p2*...*pk

 

n은 반드시 합성수이므로

1 < = i <= k 인 적당한 i에 대하여 다음이 성립합니다.

 

pi | n

그리고 pi는 p1,p2,p3,...,pk중 하나이기 때문에

pi | p1*p2*...*pk

가 성립합니다.

 

pi | n이고 pi | p1*p2*...*pk이기 때문에

pi | (n - p1*p2*...*pk) = 1이고

pi = 1이라는 모순된 결과가 나오게 됩니다 (수학적 귀류법)

 

따라서 소수가 유한하다는 가정은 틀린 것으로 증명되었습니다.

 

이상 소수의 무한성에 대한 증명을 마치겠습니다.

감사합니다.