IX 권
명제
명제 20
소수의 개수는 무한개이다.
소수의 개수는 무한개이다.
IX 권
명제
소수의 개수는 무한개이다.
소수의 개수는 무한개이다.
소수의 개수는 무한개임을 보여야 한다.
소수가 유한개라 하고 그 소수들을 \(a\), \(b\), \(c\)라 하자. 그러면 \(a\), \(b\), \(c\) 보다 많은 소수가 있음을 보이자.
\(a\), \(b\), \(c\)의 최소공배수를 \(\overline{\rm DE}\)라 하자. 단위수를 \(\overline{\rm DF}\)라 하고 수 \(\overline{\rm EF}=\overline{\rm DE}+\overline{\rm DF}\)라 하자.
그러면 \(\overline{\rm EF}\)는 소수이거나 소수가 아니다.
1) \(\overline{\rm EF}\)가 소수라고 하자.
그러면 \(a\), \(b\), \(c\), \(\overline{\rm EF}\)가 소수이니 소수 \(a\), \(b\), \(c\) 개수 보다 많다.
2) \(\overline{\rm EF}\)가 소수가 아니라고 하자.
어떤 소수가 \(\overline{\rm EF}\)를 나눈다. [VII권 명제 31] 이 소수를 \(g\)라고 하자.
그러면 \(g\)가 \(a\), \(b\), \(c\)와 다른 소수임을 보이자.
\(g\)가 \(a\), \(b\), \(c\) 중 하나와 같다고 하자. \(a\), \(b\), \(c\)는 \(\overline{\rm DE}\)를 나눈다. 그런데 \(g\)가 \(\overline{\rm EF}\)를 나눈다. 그러므로 \(g\)는 \(\overline{\rm DF}\)도 나눈다. 그런데 \(\overline{\rm DF}\)는 단위수이므로 이것은 모순이다. 그러므로 \(g\)는 \(a\), \(b\), \(c\)와는 다른 소수이다.
따라서 \(a\), \(b\), \(c\), \(g\)는 소수이므로 소수 \(a\), \(b\), \(c\) 보다 개수가 많다.
그러므로 소수의 개수는 무한개이다.
Q.E.D.
소수가 \(n\)개의 소수 \(a_1\), \(a_2\), \(\cdots\), \(a_n\) 만이 있다고 하자. 유클리드는 \(n=3\)일 때 증명하였다. \(m\)이 소수 \(a_1,\, a_2,\, \cdots,\, a_n\)의 최소공배수라 하자. (이 최소공배수는 [IX권 명제 14]에서 다루었다. 그 명제의 증명에서 소수의 최소공배수가 그들의 곱이라는 것이 언급되지 않았으며, 이 증명에서도 언급되지 않았다.)
수 \(m+1\)을 생각하자. 그러면 이 수는 \(n+1\)개의 소수가 존재함을 보이자.
\(m+1\)이 소수가 아니라고 가정하자. [VII권 명제 31]에 의해서, 소수 \(g\)가 \(m+1\)을 나눈다. 그러나 \(g\)는 \(m\)은 나누지만 \(m+1\)을 나누지 않기 때문에, \(g\)는 소수 \(a_1,\, a_2,\, \cdots,\, a_n\)과 모두 다른 소수이다. 그러므로 \(n+1\)개의 소수가 존재한다.
이 명제는 이후 원론에서 사용되지 않는다.