📂정수론

유클리드의 증명: 소수는 무한히 존재한다

정리 ¹

소수는 무한히 많이 존재한다.

설명

소수가 무한하다는 것을 증명하는 방법은 여러가지가 있다. 그 중에서도 가장 간단한 유클리드의 방법을 소개하도록 하겠다. 이 증명은 단순할 뿐만 아니라 매우 아름답기로도 유명하다.

증명

소수가 $n$ 개만 존재한다고 가정하자. $n$ 개의 소수들을 각각 $p_1, p_2, \cdots , p_n$ 이라고 하고 $p_{n+1}=p_1 p_2 \cdots p_n + 1$ 에 대해 생각해보자.

• 만약 $p_{n+1}$ 이 소수라면, $p_{n+1}$ 은 다른 어떤 소수와도 같지 않은 새로운 소수가 된다. 이는 가정에 모순이다.
• 만약 $p_{n+1}$ 이 소수가 아니라면, $p_{n+1}$은 소수 $q_1, q_2, \cdots , q_m$ 들의 곱으로 나타난다. 그러나 $q_1$ 역시 소수기 때문에 $p_1, p_2, \cdots , p_n$ 중 그 어떤것과도 같지 않다. 이는 $q_1$ 이 $n$ 개의 소수 중 하나가 아닌 새로운 소수라는 뜻이다. 이는 가정에 모순이다.

따라서 소수는 무한히 많이 존재한다.

■

같이보기

• 오일러의 증명