Euclid's theorem

Euclid's Theorem is generally a reference to the theorem (often credited to Euclid) which demonstrates the existence of an infinite number of prime numbers. Here is a version of this proof by contradiction.

Suppose p is the greatest prime number. Let p!+1 (i.e. p factorial + 1) be q. Note that p! is divisible by all natural numbers 1,2,3,...p-2,p-1, and p. Therefore q divided by any natural number p or less has a remainder of 1; q is not divisible by any natural number greater than 1 but equal to or less than p. However, even though p is assumed to be the greatest prime number, q does not have a prime factor less than p. Thus, in contradiction to our original premise, p is not the greatest prime number. Therefore, there does not exist a natural number p as the greatest prime number.