A Prime Post

A prime number is a positive integer that is greater than one and has no factors except one and itself. One is not considered a prime number. 2, 3, 5, 7.. etc are some examples of prime numbers. Numbers that are not prime are called composite numbers. Here are the prime numbers less than 1000.

      2      3      5      7     11     13     17     19     23     29
     31     37     41     43     47     53     59     61     67     71
     73     79     83     89     97    101    103    107    109    113
    127    131    137    139    149    151    157    163    167    173
    179    181    191    193    197    199    211    223    227    229
    233    239    241    251    257    263    269    271    277    281
    283    293    307    311    313    317    331    337    347    349
    353    359    367    373    379    383    389    397    401    409
    419    421    431    433    439    443    449    457    461    463
    467    479    487    491    499    503    509    521    523    541
    547    557    563    569    571    577    587    593    599    601
    607    613    617    619    631    641    643    647    653    659
    661    673    677    683    691    701    709    719    727    733
    739    743    751    757    761    769    773    787    797    809
    811    821    823    827    829    839    853    857    859    863
    877    881    883    887    907    911    919    929    937    941
    947    953    967    971    977    983    991    997

So how do we find prime numbers?

One technique attributed to Eratosthenes of Cyrene (3rd century B.C) is called the sieve of Eratosthenes which allows us to find all prime numbers equal to or less than a specified number. The algorithm goes like this:

Start with all number from 2 to the specified number. For example, if we want to find all prime numbers less than or equal to 20, write down all numbers from 2 to 20.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Now remove all multiples of the first number (which is 2), from this list starting from the next position:

2, 3, 5, 7, 9, 11, 13, 15, 17, 19

Now remove all multiples of the second number (which is 3) from this list starting from the next position:

2, 3, 5, 7, 11, 13, 17, 19

Do this until you reach the end of the list. Now you will have the list of primes under 20 which is:

2, 3, 5, 7, 11, 13, 17, 19

The primes become more sparse as the numbers become larger and larger. So do they stop existing after we get to a certain point? In other words, is the list of prime numbers finite?

Euclid proved that there are an infinite number of prime numbers. He proved it using a technique called proof by contradiction.

To understand Euclid’s proof we need to learn about a theorem called the Fundamental Theorem of Arithmetic. This theorem states that every number greater than 1 is either a prime or is a unique product of primes.

Now let us move on to the proof.

Consider there are only a finite number of primes, say n. Let us represent this finite set as {p1, p2, p3…pn} where n is the total number of primes.

Let x = (p1 * p2 * p3 * .. * pn) + 1

Now ‘x’, which is one more than the product of the primes, should either be a prime or a composite. If x is prime, then the assumption that there are only n prime numbers is wrong. If x is a composite, then we should have a unique list of primes whose product will be equal to x (as stated by the Fundamental Theorem of Arithmetic).

Since x = (p1 * p2 * p3 * .. * pn) + 1, dividing x by any of the n primes would result in a remainder of 1. That means that there needs to exist at least one other prime number which would complete the unique list of primes that can be multiplied to get x. So our assumption that {p1, p2, p3… pn} represents the entire set of primes is wrong. To state it differently, there are infinite number of primes.

P.S.

As a reader you might be wondering what prompted me to write this post. I have been reading about prime numbers and found many explanations of the Euclid’s proof online. Some were plain wrong and some had very cryptic explanation. So I spent some time thinking about it and reading many websites to get things clear in my mind first and then I thought I will share it here for the benefit of other searching for the same.

Leave a Reply

Your email address will not be published. Required fields are marked *