Following Euclid, let us prove that every finite list of prime numbers p1, p2, …, pn can be extended. Let N be the result of multiplying them together, and adding one: Since every natural number has a prime factorization, there must be some prime number q that is a divisor of N. But none of the primes pi is a divisor of N because each of them leaves a remainder of 1 when dividing into N. Therefore, q is a new prime number, not on the previous list. So we can always find another prime number, and therefore there must be infinitely many.
