Several Different Paths to Prime Numbers

Share the Science!Share on Facebook13Pin on Pinterest0Share on Google+3Tweet about this on Twitter3Share on Reddit1Email this to someone

Visual representation of Eisenstein Primes: Image by Johannes Rössel

Last week’s “Brief Introduction to Prime Numbers” dangled a few teasers – since keen minds are eager to know more, let’s tie up some of the loose ends.

Pure Review: What is a Prime Number?

A “Prime” number is a natural number greater than one, that is only evenly divisible by itself and one. This infinite but countable set begins as {2, 3, 5, 7, 11…}.

Readers might remember that “composite” numbers are the natural numbers that can be composed into factors other than themselves and one. For example, 24 = 2*2*2*3.

People have tested prime numbers “by hand”; this work was assigned to early analog computers also, as seen in this image:

"Analog Prime Number Factoring Computer" by Tom Purves

Analog Prime Number Factoring Computer – Image by Tom Purves

Are There an Infinite Number of Prime Numbers?

Yes, there are infinitely many primes, and the proof goes back to the Greek philosopher Euclid. Suppose we have a set P={2, 3,…p} of prime numbers, and ‘p’ is the highest known prime. Simply calculate p[1] = ( ( 2*3*5*…*p ) + 1 ). Certainly ‘p[1]’ is not divisible by any of the primes in set P, since there would be a remainder of 1. Assuming that ‘p[1]’ is divisible by a prime larger than ‘p’. That assumption simply agrees with the notion that there is, in fact, a prime number larger than ‘p’.

The number ‘p[1]’ in the above paragraph is not necessarily the next larger prime greater than ‘p’, although it might be that “next prime”. It simply proves that there must be one. A later paragraph deals with Euclid numbers.

Is the Set of Prime Numbers a Countable Infinity?

Yes, the set of all prime numbers is indeed a countable infinity, which means that this set has a one-to-one relationship to Natural numbers.

The Sieve of Eratosthenes assists with this proof. As the Sieve is built to any desired length, it preserves the order of the prime numbers; none are skipped, which would force some extra counting. Therefore, we have a first prime number, a second, a third prime, and so on. This process of ordering and counting means that the set of prime numbers is a countable infinity.

(More details about infinity are found in “Cantor Defeated Galileo in the Battle of Infinite Numbers“).

What Special Groups of Prime Numbers Exist?

These groups are simply ways that people use to find some, but unfortunately not all, prime numbers. As mentioned above, Euclid proved that there are an infinite number of primes. Two special primes that use powers of two are Fermat primes and Mersenne primes. Their definitions differ only in using a plus sign or a minus sign.

Euclid Numbers and Euclid Prime Numbers

The nth “Euclid Number” is calculated as ‘E[n]’ = 1 + p[1] * p[2] *…*p[n] where ‘n’ is a positive natural number and ‘p[j]’ is the jth prime number. More simply, E[n] = 1 + 2*3*5*7*…*p[n].

Many Euclid numbers are prime, but some are not. For example, E[6] = 1 + 2*3*5*7*11*13 = 30031 = 59*509, which is composite. Those which are prime are called Euclid Prime Numbers.

Fermat Numbers and Fermat Prime Numbers

"Pierre de Fermat" by Magnus Manske

Pierre de Fermat: Image by Magnus Manske

There are two different types of Fermat numbers, both named for Pierre de Fermat.

Less Common Fermat Numbers

The “less commonly used” form of the nth Fermat number is defined as F[n] = 2^n +1 where ‘n’ is a natural number greater than zero. The set F = {3, 5, 9, 17,…}.

Some, but not all, of the above Fermat numbers are prime. From the list above, {3, 5, 17,…} are prime but ‘9’ is not.

The rest of this article will ignore this type of Fermat number.

Following the More Popular Fermat Numbers

The “more common” Fermat numbers are defined as F[n] = 2^2^n + 1 where ‘n’ is a natural number greater than or equal to zero. [This is calculated as ( (2^(2^n) ) + 1 ), by the way].

This set F = {3, 5, 17, 257, 65537,…}.

To quote Mathworld in “Fermat Number“, the “only known Fermat primes” are the first five Fermat numbers. This set is {3, 5, 17, 257, 65537}. Also, only the next seven Fermat numbers have been completely factored into all their primes. These Fermat numbers grow huge at a very rapid rate.

Mersenne Numbers and Mersenne Prime Numbers

Named for Marin Mersenne, the nth Mersenne number is defined as M[n] = 2^n – 1 where ‘n’ is a natural number greater than zero. The set M = {1, 3, 7, 15,…}.

"Marin Mersenne by Philippe de Champaigne" via University of Wisconsin at Madison

Marin Mersenne by Philippe de Champaigne: Image via University of Wisconsin at Madison

Some, but not all, Mersenne numbers are prime. From the list above, {3, 7,…} are prime but ‘1’ is not prime (as an exception) and ’15’ is not prime because it is composite.

It turns out that ‘n’ must be a prime number in order for ‘M[n]’ to be prime. This is not sufficient; for example M[11] = 2^11 -1 = 2047 = 23 * 89.’

Some mathematicians may refer only to Mersenne primes but call them “Mersenne numbers”.

Is There a Future for Prime Numbers?

Mathematicians see prime numbers as an extremely important window into number theory, with an array of unsolved problems.

From the limited viewpoint of this series of articles: yes, the future of primes should include a survey of the ways in which prime numbers are used. Another future article will explain the mysterious image of Eisenstein Primes.


Ball, W. W. Rouse. “Pierre de Fermat (1601 – 1665)” from ‘A Short Account of the History of Mathematics’ (4th edition, 1908). Accessed Oct. 23, 2011.

O’Conner, John J. & Robertson, Edmund F. & EFR. University of St Andrews, Scotland. “Marin Mersenne”. (Aug. 2005). Accessed Oct. 23, 2011.

Weisstein, Eric W. Mathworld (Wolfram). “Euclid Number“, Fermat NumberMersenne Number. (1999-2011). Accessed Oct. 23, 2011.

Editor’s Note: 9-3-13 Thanks to Christine for catching the typo! 

© Copyright 2011 Mike DeHaan, All rights Reserved. Written For: Decoded Science
Share the Science!Share on Facebook13Pin on Pinterest0Share on Google+3Tweet about this on Twitter3Share on Reddit1Email this to someone



Leave a Reply

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