Euclid's theorem

From Wikipedia, the free encyclopedia

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.

Assume p is the greatest prime number. Let P = {2,3,5,...,p} be the set of all prime numbers less than or equal to p, i.e. the set of all primes. Let where . It is clear p' is not prime, since every element of P is a factor of p'. Let q = p' + 1. Clearly every element of P divides q with a remainder of 1. Thus, q is prime or there exists a prime not in P which divides q. If q is prime, this would contradict our assumption that p is the greatest prime since q > p. Therefore, there must exist a prime that divides q which is not an element of P. But this would contradict our assumption that P is the set of all primes. Contradiction.

[edit] External links

• Euclid's Theorem at Mathworld