소수는 무한한가? - 유클리드의 증명

소수는 무한한가? - 유클리드의 증명

안녕하세요. 글루온입니다. 이번 포스팅에서는 소수의 무한성에 대해서 논의해 보겠습니다. 사실 깊게 들어가려면 메르센 소수 등 이야기할 것들이 많아지지만, 오늘은 간단하게 소수의 개수가 무한이라는 것만 증명하겠습니다.

소수(prime number)는 참으로 신기한 수입니다. 오늘날 잘 알려진 세계 7대 수학 난제 중 하나에 속할 만큼 이 미스터리는 아직도 남아 있습니다. 세계 7대 수학 난제 중 하나인 리만 가설은 소수의 규칙성에 관한 문제입니다. 소수는 대체 어떤 규칙성을 띠고 있을까? 하는 것이죠.

이것이 왜 이슈가 되냐면 요즘 암호체계가 이 소수와 관련이 깊기 때문입니다. 소수의 불규칙성에 의해서 보안이 유지되는데, 소수의 규칙성을 알아내버리면 보안체계가 흔들리는 거죠.

으음......그럼 더 깊게 들어가지 않고 간단하게 소수의 무한성을 증명하겠습니다. 

다음을 증명하면 소수의 무한성이 증명됩니다.

P1, P2, P3 .... PN 이라고 하는 N개의 소수가 있을 때, 이들과는 다른 소수가 항상 존재한다.

이제 새로운 하나의 수를 만들겠습니다.

이 수는 P1, P2, P3, ...PN 안에 포함되지 않고, 그 수들로 소인수분해가 되지 않습니다.

그렇기 때문에 A의 소인수는 P1, P2, P3, ...PN와는 다릅니다.

따라서 소수는 무한하다는 것을 알 수 있습니다.

(여기서 주의할 점은 A가 항상 소수가 아니라는 점입니다. A의 소인수 중에 새로운 소수를 찾는거죠.)

증명 과정이 참으로 간단하다는 것이 놀랍지 않나요?ㅋㅋ

도움 되셨다면 손가락 클릭 해 주세요^^