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.

A Basic Overview of Number Theory

Number theory is one of the oldest branches of mathematics. The earliest mathematics was undoubtedly application focused, coming out of, for example, counting problems in commerce and geometry problems in construction. When mathematics turned its gaze inward, numbers were the first things that were explored. Almost every mathematical culture had a version of elementary number theory

Number theory is divided into several areas. As with any area of mathematics, the different sub-specialties are too numerous to list, but some of the largest areas include:

Analytic number theory employs techniques from real and complex analysis to answer questions about the natural numbers. The Prime Number Theorem and the related Riemann Hypothesis are part of analytic number theory, as are the proofs of the transcendence of numbers such as e or . The Riemann Hypothesis, proposed by the German mathematician Bernhard Riemann in 1859, remains one of the most famous unsolved problems in mathematics.

Algebraic number theory applies the methods of abstract algebra, group theory, field theory, and Galois theory to study the algebraic numbers—numbers that are the roots of polynomials with rational coefficients. Numbers that are not algebraic are transcendental—e and  for example. Many concepts in algebraic number theory are studies modulo-p, where p is any prime number. This yields the p-adic numbers.

Combinatorial number theory applies combinatorial ideas such as partitions, covering systems, arithmetic progressions, and zero-sum problems, to number theoretic problems.

Computational number theory deals with algorithms relevant to number theory, such as integer factorization and primality testing algorithms. Computational number theory is intimately connected with cryptography.

At the heart of all the different branches of number theory is the Elementary number theory of Euclid, which studies the properties of the natural numbers without the use of techniques from other branches of mathematics. Questions in elementary number theory involve divisibility (greatest common divisors, for example), factorizations into prime numbers, special classes of natural numbers such as perfect numbers, multiplicative functions, and investigations of natural number sequences such as the Fibonacci numbers. Many famous conjectures in mathematics were stated in terms of elementary number theory, such as Goldbach’s conjecture, the Collatz conjecture, and Fermat’s Last Theorem. Those conjectures that have been proved have required techniques from outside elementary number theory.

Many questions in elementary number theory, and many of the applications of number theory, revolve around the notion of divisibility. If a, b and c are integers such that a = b *c, then b and c are said to divide (or are factors) of a, while a is said to be a multiple of b (as well as of c). The pipe symbol “|” denotes “divides” so we write b|a  c|a. The divisors we are interested in most often for a given number are the prime divisors.

Remainders in division are just as important in number theory as divisors, in the form of modular arithmetic. Let a be an integer, and d be a positive integer. There are unique integers q, r with r  {0,1,2,…,d-1} satisfying a = dq + r. The quantity r is called the remainder. We can calculate the remainder via the mod function. a mod b is a number between 0 and b –1 inclusive, which is the remainder of ab. A related notion is the modular congruence, which relates two numbers a, a’ to each other relative some base b. The notation a  a’ (mod b) means that a and a’ have the same remainder when dividing by b.

The notion of congruence is useful for manipulating expressions involving the mod function. It lets us view modular arithmetic relative to a fixed base, allowing us to create a number system with a finite number of elements inside of which all the calculations can be carried out. The study of these finite number systems is called finite field arithmetic, and they are essential to most symmetric encryption algorithms.

Modular arithmetic is an essential aspect of number theory’s best known application, cryptography. For example, modular arithmetic's properties are at the heart of the RSA public key encryption algorithm.

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.”

Numeral Systems

Every civilization has known in some way about the universal concept of numbers, and every civilization created a numeral system to represent them. Humans count things, and early numeral systems were all about counting. Most of us probably take our familiar base-10 numeral system for granted, but looking at early numeral systems can help you appreciate the power of good notation (a theme I think runs throughout the history of math).

Certainly early humans had to count things, whether is was deer or logs for the fire, but early civilizations with their reliance on agriculture really highlighted the need to keep track of counts. In many ways, commerce drove the development of numeral systems. It was the needs of merchants to keep track of their money that made Europeans open to the use of Hindu-Arabic numerals described in the book Liber Abaci by Leonardo of Pisa (better known to us as Fibonacci). Going back even further in history, it was the needs of early civilizations to keep track of counts larger than 10 or 20 that led to the development of different numeral systems.

This will be a necessarily shallow introduction to numeral systems. Books can and have been written about Babylonian, Egyptian, and Greek mathematics, as well as less famous civilizations such as the ancient Cretans. Someday, I'd like to read some of those books, so I can know more about them than what is here.

Any numeral system should have at a minimum two characteristics: it should represent a useful set of numbers (all the natural numbers at least), and it should have a unique representation for each number. There are two types of numeral systems—additive systems and positional, though Archaeologist and anthropologists, i.e. people that know that they are doing, may classify ancient numeral systems differently.

Additive systems are the simplest number systems, in which a number . The simplest additive system is a unary system, where every natural number is represented by a corresponding number of symbols. The Cretans, for example, from 1700-1200 BCE, used a unary system, which consisted essentially of tally marks.

Additive systems can be improved by employing special symbols for the grouping of units. The ancient Egyptians employed a base 10 numeral system, with special symbols for powers of ten. The Greeks had a slightly more complicated system, an extended decimal system with special symbols for powers of 10, five, and multiples of five and powers of 10. The symbols have the same meaning regardless of their position. More familiar are Roman numerals. When I was a kid we had to learn about Roman numerals, though I've never figured out why it was important to learn about them. Additive systems are simple, and for purposes of representing natural numbers they work; larger numbers get a bit cumbersome, but every natural number can be represented, and there is a unique representation for each number. Where additive systems really fall apart is with arithmetic. Try multiplying 2459671 and 45689 in the additive numeral system of your choice and you can see the problems.

Positional numeral systems are a bit more complicated than additive systems; the location of the symbol matters. In a base-b positional numeral system, we write the number

as:

For example, in the base 10 numeral system with which we are familiar, when we write 1231, we mean the number:



The Babylonians had a sexagesimal, or base-60 numeral system, which really works quite well; other than the (to us) unusual base and symbolism, the Babylonians system seems quite modern, especially when compared to additive systems such as the Romans. One notable difference between this ancient systems and our own is the lack of a symbol for zero.

The number zero was a surprisingly long time coming. Many cultures had trouble with the idea of 0 as a number. Zero was synonymous with nothing, and how could nothing be a number? The Babylonians dealt with the lack of a positional value by leaving the place blank. This works, but you can see how sloppy penmanship could lead to numerical confusion. The Mesoamerican Long Count Calendar, a non-repeating base-20 and base-18 calendar dating to 36 BCE and used by several ancient Central American civilizations including the Maya, makes use of several glyphs for zero as a placeholder. The Mayans base-20 numeral system settled on a shell glyph for zero, again as a placeholder. 

Zero appears sporadically as a placeholder in Old World mathematics, but the first instance of zero as a number withing a positional numeral system is generally credited to Indian mathematicians, who by the 9^th century AD were carrying out calculations with zero as a number. The Hindu-Arabic number system, with its zero, was first described by the renowned Persian mathematician Abū ʿAbdallāh Muḥammad ibn Mūsā al-Khwārizmī, whose book on Arithmetic, written in 825 AD, is considered one of the most influential ancient texts. One of al-Khwārizmī's later fans, Leonardo of Pisa, introduced European mathematicians to the Hindu-Arabic numeral system through his book Liber Abaci. While the symbols have evolved somewhat, they are remarkably similar to the original numeral system described by al-Khwārizmī.

With the introduction of the number zero, the positional numeral system was complete. You can pick your base—decimal, hexadecimal, binary, whatever—the essential qualities are the same. Arithmetical computation is easy. The history of numeral systems is fascinating; it took a very long time to get to something that we take for granted.

The evolution of numeral systems didn't stop with the Hindu-Arabic numeral system. Complex numbers, with the imaginary unit i, were a later discovery, but by that time mathematicians were thinking in the decimal numeral system we use today, and with a good system of notation, the possibilities are endless.

What Are Numbers?

Numbers are the most natural place to start a survey of mathematics. Each time I've taught the Survey of Mathematics course, we've started with the basic (but not easy) question: “What is a number?” Like many things that we think of as obvious, it is hard to explain. Naming examples of numbers is easy, and it is nearly as easy to list things for which numbers are used—counting, measuring, ordering, and labeling or identifying. We can take these uses of numbers and get a quick definition: a number is a mathematical object used to count or measure (the other uses are related to ordering and uniqueness, two properties most of our number sets will have). This definition is admittedly squishy, but it has one key element that rings true. A number is a mathematical object.

It is easy to confuse the concept of “numbers” with the symbol used to represent them, numerals. To see the differences, consider an example: “5” and “five” are two ways of representing the same abstract mathematical object. “Five” is something beyond the word or symbol we use to describe it. If you look at a stack of five apples and a stack of five books, you can see that while the two stacks may have very little in common, they share the same fundamental quality of “fiveness.” Getting at what “fiveness” or “threeness” actually is takes us down the road to mathematical Platonism, a view of mathematics that has been with us for more than 2000 years.

Plato's philosophy of mathematics grew out of his attempts to understand the relationship between particular things and universal concepts. The world we live in is filled with particular things—this chair, that chair, big chairs, little chairs, and so forth. There is a quality all of the instances of particular chairs share—for lack of a better phrase we'll call it “chairness”—which presents a bit of a problem. It is not itself a chair and unlike all chairs we know it cannot be located in some place or at some time, but that does not mean that “chairness” is a figment of our imagination. Replace “chairness” with “fiveness” or “threeness” and we see how all this applies to numbers. Numbers are not particular things, they are universal concepts.

Initially driven by the need to count things, our understanding of numbers has grown considerably, pushed along by problems we've needed to solve. Counting problems led to the natural numbers, {1,2,3,4,...}, and then to the integers, problems in geometry led to the rational numbers and to the irrational numbers, which collectively give us the real number system. Problems in algebra and physics led to the complex number system. And mathematical explorations have led to more exotic number systems such as quaternions, and generalizations of numbers in abstract algebra like fields. Mathematicians have found these generalizations through their favorite game, making up axioms and seeing where those axioms lead.

To the Platonic way of thinking, these generalizations weren't invented, they were discovered. Numbers, universal concepts that they are, were always there, as were the generalizations like fields, humans just had to figure out how to use and to represent them. Humans didn't invent numbers, we invented numeral systems, but like anything in mathematics, numerals systems rely on notation, and it took a long time to find a notation that worked really well. Exploring how numeral systems evolved, and learning how ancient civilizations did mathematics, is a fascinating journey.