유클리드의 정리 (Euclid’s Theorem) 의 내용은 다음과 같습니다.
소수 의 집합 P의 크기는 무한하다.
(증명의 스케치)
소수가 유한하게 있다고 치고, q=1+∏p∈Pp라 하자. (P는 모든 소수들의 집합)
모든 소수 p에 대해 q와 p는 서로소 이고, q>max이므로, 1보다 크고 q보다 작은 약수가 존재하지 않으므로 q는 소수이다.
이렇게 되면 모든 소수들의 집합이라는 가정에 모순이 생긴다.