Euclid's Proof of the Infinity of Prime Numbers

 

home | courses | topics | theorems | starters | worksheets | timeline | KS3 | KS4 | KS5

   
 
           
                   

Euclid first proved that the number of primes is infinite. There is no largest prime number as much as there is no largest number!

Euclid started by looking at the known primes and adding one to their product. For example both 2 and 3 are primes: their product + 1 is also a prime: 2*3+1=7. Continue by adding 5 to the same process: 2*3*5+1=31 - and presto! that is a prime too. The nice but not beautiful thing about this is that sometimes this algorithm will churn out primes and sometimes it will not!

Try with few numbers to see how many primes you'll get and whether you'll spot the numbers which are not prime.

Although Euclid did not find the way to using this procedure to find only primes, he did find that this can be used to show that the there is infinitely many primes.

 

 

Proof

Let us suppose that p 1 , p 2 , p 3 , ... p n   are prime numbers. Multiply them together and add 1, calling this number a new integer q . If q is a prime number, then we have a new prime. If q is not a prime, it must be divisible by a prime number r . But r cannot be p 1 or any other from our original list of prime numbers, because if you divide q by any of p 1 , p 2 , p 3 , ... p n you will get a remainder 1, which means that q is not divisible by any of these prime numbers. So r is a new prime. Whichever way you choose to look at it, either you have found a new prime q, or if q is not a prime, than you have found that it has a new prime for a prime factor.

   

Main number page

Prime numbers

Largest Prime Number known

See Eratosthenes' Prime Number sieve and download some worksheets: 100, 200 or 500 number sieve.

What people thought of primes through the history

Prime number (as the one defined by Aristotle, Euclid and Theon of Smyrna) is a number "measured by no number but by an unit alone". Iambilicus - a Greek philosopher, called the prime numbers "odd times odd".

Prime number was apparently first described by Pythagoras.

Iamblichus writes that Thymaridas called a prime number rectilinear since it can only be represented one-dimensionally.

In English language the expression 'prime number' is first found in Sir Henry Billingsley's 1570 translation of Euclid's Elements (OED2).

Some older textbooks include 1 as a prime number.

In his Algebra (1770), Euler did not consider 1 a prime [William C. Waterhouse].

 

artefacts | numerals | concepts | people | places | pythagoreans | egyptians | babylonians

 

Google
Search WWW Search www.mathsisgoodforyou.com

_____________________________________________________________________________________________________________________

Acknowledgements | Copyright | Contact | Mission Statement | Tell a friend about this site