[수학] 증명: 소수는 무한히 많다 - 유클리드의 고전적인 증명

수학에서 소수(Prime Number)는 1과 자기 자신 외에는 다른 어떤 수로도 나누어지지 않는 자연수를 의미합니다. 소수는 수론에서 매우 중요한 개념이며, 무한히 존재한다는 사실이 고대 그리스 수학자 **유클리드(Euclid)**에 의해 증명되었습니다. 이번 글에서는 **모순법(proof by contradiction)**을 사용하여 소수가 무한히 많음을 증명해 보겠습니다.

---

소수의 무한성을 증명하기

1. 가정 (Contradictory Assumption)

소수가 유한하다고 가정해 보겠습니다. 즉, 우리가 모든 소수를 나열할 수 있다고 가정하면, 이 소수들은 다음과 같이 유한한 개수만 존재한다고 볼 수 있습니다.

$$p_1, p_2, p_3, \dots, p_n$$

여기서 $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, $p_4 = 7$, ... 등으로 이어집니다. 우리는 이 리스트가 모든 소수를 포함하고 있다고 가정합니다.

---

2. 새로운 수 $N$ 정의

이제 기존에 존재하는 모든 소수를 곱한 뒤, 1을 더한 새로운 수 $N$을 정의합니다.

$$N = p_1 \times p_2 \times p_3 \times \dots \times p_n + 1$$

즉, 모든 소수의 곱에 1을 더한 수입니다.

---

3. $N$이 새로운 소수를 포함함을 보이기

이제 $N$이 기존의 소수들 중 어느 것도 약수로 갖지 않는다는 사실을 증명하겠습니다.

• $N$을 기존의 소수 중 하나인 $p_i$로 나누면 항상 나머지가 1이 남습니다.
• 즉, 기존의 소수들 중 어떤 것도 $N$을 나눌 수 없습니다.

이것은 $N$이 새로운 소수를 포함하고 있음을 의미합니다.

---

4. 모순 도출 (Contradiction)

• 만약 $N$이 소수라면, 이는 기존 목록에 없는 새로운 소수이므로, 처음에 가정한 **"소수는 유한하다"**는 가정에 모순됩니다.
• 만약 $N$이 합성수라면, 그 소인수 중 하나는 기존 목록에 없는 새로운 소수일 것입니다.
• 따라서, 어떠한 경우에도 소수는 유한할 수 없습니다.

이로써 소수는 무한히 많다는 결론이 도출됩니다.

---

결론

유클리드의 이 증명은 수학에서 가장 유명한 증명 중 하나로, 소수가 무한히 많음을 간결하면서도 강력하게 보여줍니다.

이 증명은 이후의 수론 연구에도 큰 영향을 미쳤으며, 오늘날에도 수학의 기초 개념으로 활용되고 있습니다. 우리가 다루는 수가 아무리 크더라도, 언제나 새로운 소수를 찾을 수 있다는 사실은 소수의 신비로움을 더욱 부각시킵니다.