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. 
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 onedimensionally. 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
_____________________________________________________________________________________________________________________ Acknowledgements  Copyright  Contact  Mission Statement  Tell a friend about this site 
