The Mystery of Prime Numbers

Prime numbers are one of those things in mathematics that makes you start to think there is a method to the madness of the universe. The fundamental theorem of arithmetic tells us that every natural number can be uniquely factored into a prime numbers. Prime numbers can therefore be viewed as the building blocks of the integers. Yet, while the FTA tells us that every number can in principle be factored into primes, nobody has yet figured out how to factor large numbers rapidly, something that many modern cryptographic protocols—such as the RSA cipher—rely on for their security.


Euclid’s theorem tells us in principle that there are arbitrarily large primes out there, but does not give a recipe to find them.  Indeed, the prime numbers seem to be so “randomly” distributed that it is often difficult to establish what patterns exist within them. The Greeks were certainly aware of the importance of prime numbers, and several key results and conjectures about primes come to us from the ancient Greeks. Much of this is captured in Euclid's Elements.


Very little is known about the Greek mathematician Euclid. The date and place of his birth, and the date and circumstances of his death are unknown; we have only a rough idea based on contemporary references. There were no likenesses or descriptions made of him during his lifetime. The few historical references to Euclid (as opposed to his books) were made centuries after his death. In spite of the scarcity of the historical record, Euclid's Elements are without question the most influential works in mathematics, serving as one of the main texts for the teaching of mathematics from its creation until the early 20^th century. Euclid's rigorous approach to mathematical proof remains central to modern mathematics; in many ways Euclid set the standard for a proof. While many, possibly all, of the mathematical results in the Elements originated with other mathematicians, Euclid's impressive accomplishment was to capture the breadth of the mathematics of his day and present it all in a single, logically coherent framework, a feat that was never before accomplished, and never repeated.


After the Greeks, there were relatively few results on prime numbers until the 1600's, when the French monk Marin Mersenne studied primes of the form 2^p-1 , with p prime (called Mersenne primes today). Mersenne was a French monk who, in addition to dabbling with prime numbers made great strides in music theory, earning the nickname the “father of acoustics.” In 1640, Pierre de Fermat, perhaps the greatest amateur mathematician of all time, conjectured that a^p-a is divisible by p, where a is any integer and p is prime; this is Fermat's Little Theorem, which, like so many of Fermat's theorems, he himself did not prove. Two other luminaries, Leibniz and Euler, tackled this problem much later. Fermat also conjectured that all numbers of the form 2²ⁿ+1 is prime; he verified this to n=4 , but was proven wrong; the next Fermat number is composite, and no others are known to be prime.


In the 1700's, number theory had fallen out of fashion, prior to tackling Fermat's little theorem and conjecture, Leonard Euler tackled the zeta function, which more than 100 years later was again studied by (and eventually named after) Bernhard Riemann:

Euler's Zeta Function

For s>1, this series is finite. Euler showed that this infinite series has a deep connection to the prime numbers, and the zeta function equals the infinite product:

The Zeta Function and Prime Numbers

Since Euclid's time, it was known that even perfect numbers, numbers that are the sum of their prime factors, have the form 2^p-1(2^p-1). In 1747 Euler showed that an odd perfect number would have the form:

Odd Perfect Numbers

While we know what they would have to look like, we don't know if there are any. It is believed no odd perfect numbers exist, but there is no proof. Thus far, it has been shown that no odd perfect numbers exist less than 10³⁰⁰.


The primes behave so randomly that we have no useful exact formula for the nth prime. But we do have an important approximate formula in the Prime number theorem. One of the most important results about prime numbers, it was a long time coming. In the 19^th century Legendre and Gauss, conjectured that as x tends to infinity, the number of primes is asymptotic to x/ln(x). In 1859, Riemann described his hypothesis about zeta function, which has become one of the great unsolved problems in mathematics. In his paper, Riemann outlined an approach in this paper that would lead to proof of Legendre and Gauss' conjecture. It was two mathematicians, Jacques Salomon Hadamard and Charles-Jean Étienne Gustave Nicolas de la Vallée Poussin who independently proved Legendre and Gauss' conjecture in 1896.


The prime number theorem shows that the primes have some large-scale structure, even though they can behave quite randomly at smaller scales. The proof of the theorem is a remarkable work of multidisciplinary mathematics, using arithmetic functions (Von Mangoldt function), distribution theory (Mellin transforms), and complex analysis.

Von Mangoldt Function

A prime number’s only divisors are 1 and itself. The fundamental theorem of arithmetic says that every number is either prime or has a unique factorization of prime divisors. This is a powerful result, and it tells us that prime numbers are the building blocks of the integers. However, finding the prime factors of a large integer is hard. Many asymmetric cryptography schemes rely on this difficulty, and make use of it by essentially multiplying extremely large prime numbers together. Knowing only the product and not the primes, factoring is extremely difficult, especially when the numbers are large. With large enough numbers finding the prime factorization is, practically speaking, impossible.


The fundamental nature of prime numbers has been known since the time of the ancient Greeks, but their role in cryptography is relatively recent. What is fascinating is that something decidedly modern such as e-commerce, which requires secure communications for online transactions, makes use of number theoretic results that have been around for more than thousands of years. Despite having studied them since the dawn of mathematics, prime numbers still hold many secrets.

The Natural Numbers

The natural numbers are the counting numbers {1, 2, 3,…}, sometimes with 0 included.  There is no universal definition for the natural numbers; sometimes the natural numbers are defined to be the set of non-negative integers {0, 1, 2, 3,...}, and sometimes they are defined to be the set of positive integers {1, 2, 3,...}.  Natural numbers have two primary uses—counting and ordering.  They are the simplest set of numbers in many ways, but they have some amazing properties, and are still being studied today.  The set of natural numbers is often represented by a fancy N.

The exclusion or inclusion of zero depends on your particular mathematical discipline.  Number theorists usually define the natural numbers to the set of non-negative integers.  Number theory is one of the oldest mathematical disciplines, and the Greeks, Indians, and Islamic mathematicians of antiquity studied it extensively.  Number theorists enjoy a body of theorems stretching back further than any other mathematical discipline, with the possible exception of geometry, so you might say the study of the natural numbers is steeped in tradition.  Given the comparatively recent discovery of zero, the number theorists’ exclusion of zero from the natural numbers is understandable, but to avoid confusion, most mathematicians, when referring to the set of natural numbers will name the set the non-negative integers or the positive integers, depending on whether zero is included or not.

The natural numbers have several important algebraic properties.  They are closed under addition and multiplication.  That is, for all natural numbers a and b, both a+b and a*b are also natural numbers.  Addition and multiplication on the natural numbers are both associative and commutative, and there is both an additive and a multiplicative identity (0 and 1, respectively).  The natural numbers are also ordered:  for any two natural numbers a and b, either a<b, a=b, or a>b. 

The systematic study of the natural numbers as abstract entities most likely begins with the Greeks, and is usually credited to the Greek philosopher-mathematicians Pythagoras and Archimedes. 

Some of the special types of numbers from Pythagorean number theory.

Pythagoras was an interesting character.  He is best known for the Pythagorean Theorem, though he almost certainly did not discover this theorem, as it was known and used by the Babylonians.  Pythagoras was born around 570 BC on the island of Samos in the eastern Aegean Sea, and is thought to have traveled widely, being exposed to Babylonian and Egyptian mathematics.  He was the founder of a mystical religious sect known as the Pythagoreans, heavily influenced by mathematics, though as Pythagoras himself wrote nothing down, the exact belief system of the Pythagoreans is unknown.  So much of what has been written about Pythagoras is myth and legend—for example, according to Aristotle, some ancients believed that Pythagoras had the ability to travel through space and time and could communicate with animals—that the reality is hard to know.  His sect’s fascination with numbers is evident in early music theory.  By examining the vibrations of a single string (called a monochord) they discovered that harmonious tones occurred only when the string was fixed at points along its length that were ratios of natural numbers. For instance when a string is fixed 1/2 way along its length and plucked, a tone is produced that is one octave higher and in harmony with the original. Harmonious tones are produced when the string is fixed at distances such as 1/3, 1/4, 1/5, 2/3 and 3/4 of the way along its length. Fixing the string at points along its length that were not a simple fraction produces a note that is not in harmony with the other tones.  These ratios still form the foundation of modern music theory.  The Pythagoreans carried things a bit further, to the harmony of the spheres, in which the planets and stars moved according to mathematical equations which corresponded to musical notes.

The Pythagoreans did some solid mathematical work, but they also went a little bit off the deep end.  In Pythagorean numerology numbers had mystical attributes. Odd numbers were regarded as male and even numbers as female. 

1.   The number of reason (the generator of all numbers)‏
2.   The number of opinion (The first female number)‏

3.   The number of harmony (the first proper male number)‏
4.   The number of justice or retribution, indicating the squaring of accounts (Fair and square)‏
5.   The number of marriage (the union of the first male and female numbers)‏
6.   The number of creation (male + female + 1)‏
10.  The number of the Universe.

The tetractys was an important symbol to the Pythagoreans, representing for them all possible geometric dimensions. The rows were:  1 point (0 dimensions), 2 points (a line, 1 dimension), 3 points (a plane, 2 dimensions), and 4 points (a surface, 3 dimensions) ‏.  These added up to 10, the number of the Universe.

The Tetractys, a sacred symbol for the Pythagoreans.

Modern mathematics doesn’t view natural numbers in quite the same mystical, religious light as the Pythagoreans, but there are still fascinating properties about the naturals that make them vitally important.  The factorization of a natural number is one example.  If n, m, and q are natural numbers, and n=mq, then m and q are the factors (or divisors) of n.  The process of finding factors is factoring.  The product mq is called the factorization of n.  There are many factorizations of a natural number, but there is only one prime factorization, i.e. when all the factors are prime numbers.  A positive natural number whose only factors are 1 and itself is a prime number.  Prime numbers are critically important in number theory, and have an application central to modern society:  cryptography.

There are hints that the ancient Egyptians had some knowledge of primes.  Egyptian arithmetic was recorded in the form of recipes.  The forms for the expansion of fractions were very different for prime numbers versus composite numbers.  However, the earliest records of the explicit study of primes come from Ancient Greece.  The best known example is Euclid's Elements, written around 300 BC, which contained several important theorems about prime numbers.  One of these is The Fundamental Theorem of Arithmetic, which states that every positive integer (excluding 1) can be expressed as a product of primes and this factorization is unique.  Euclid’s proof of this result and the proof of the infinitude of primes remain to this day beautiful examples of the use of reductio ad absurdum, or proof by contradiction. 

A sketch of Euclid’s proof of the Fundamental Theorem of Arithmetic (FTA) is as follows.  Assume N is the smallest number that is neither prime nor can it be expressed as a product of primes.  Since N is composite (otherwise it would be prime), N = p * q, both less than N.  If p and q are primes, then the assumption is wrong and N can be written as a product of prime factors.  If p and q are composite, then since they are smaller than N they a product of primes, as again the assumption leads to a contradiction.  Thus there is no smallest N that cannot be expressed as a product of prime numbers; hence any number can be expressed as a product of primes. QED.  (This is Latin for quod erat demonstrandum, or “what was to be demonstrated”).

Euclid’s proof of the infinitude of prime numbers is equally ingenious.  We again assume the contrary and consider the finite set of primes: p₁, p₂, …. p_n-1, p_n.  Let S = p₁* p₂* …* p_n-1* p_n.  Consider the number T=S+1, which is either prime or composite.  Since T = p₁* p₂* …* p_n-1* p_n+1.  If T is prime then we have a prime that is not on our list and is larger than any prime on our list, which is a contradiction.  If T is composite, then it can be written as the product of prime numbers by the FTA.  But clearly T is not divisible by any of the primes on our list, as that would leave a remainder of 1, so there must be a prime p>p_n, that divides T, and again we have a contradiction.  Hence there is no largest prime number, and the number of primes is infinite.  QED. 

Euclid’s work on prime numbers doesn’t stop there.  He also showed how to construct a perfect number,  a number that is the sum of its prime factors, from a Mersenne prime, which are prime numbers with the form 2^p-1, with p  prime.  The Greeks also gave us the Sieve of Eratosthenes, a simple method for finding prime numbers.

This barely scratches the surface of number theory, which, while not the focus area for every mathematician remains interesting to all of us, perhaps because the natural numbers are so fundamental.  The German mathematician Leopold Kronecker, said it best:  “God created the integers, all the rest is the work of man.”