What the Greeks meant by a prime
A prime number is a whole number greater than 1 whose only divisors are 1 and itself. The first few are 2, 3, 5, 7, 11, 13. In Book VII of the Elements, around 300 BCE, Euclid defines a prime as a number measured by a unit alone, meaning that nothing but the unit divides it exactly. Numbers that are not prime he calls composite, since they are measured by some other number.
His definition differs from ours in a detail that surprises people. For Euclid, a number was a multitude of units, so 1 was the unit, not a number in the strict sense. That is one reason 1 is not treated as prime in his scheme. Later writers sometimes treated 1 differently, and only in the nineteenth century did the convention become fixed that 1 is neither prime nor composite. The modern convention is useful, because it keeps the statement that every number factors in a single way into primes tidy.
Earlier Greek sources use related terms, such as “first” and “incomposite” numbers, and the idea of a number with no parts other than the unit goes back at least to the Pythagorean tradition, though the details of who first used it are not documented well enough to be sure.
Why primes matter
Primes are the building blocks of multiplication. Every whole number greater than 1 is either prime or can be written as a product of primes. Euclid proves a form of this, in Book VII, showing that every composite number is measured by some prime. The full statement, that the factorisation is unique apart from order, was stated clearly by Gauss in the early nineteenth century. Together these facts are called the fundamental theorem of arithmetic.
Euclid’s proof that primes never run out
In Book IX, Proposition 20, Euclid proves that prime numbers are more than any assigned multitude of prime numbers. In modern language, there are infinitely many primes. His reasoning goes like this.
Take any finite list of primes. Multiply them all together and add 1. The new number is either prime or composite. If it is prime, it is a prime not on the list, since it is bigger than all of them. If it is composite, then it has some prime divisor. That divisor cannot be any prime on the list, because dividing the new number by any listed prime leaves remainder 1. So it is a prime outside the list. Either way, the list was incomplete.
Euclid wrote the proof with three primes as an illustration and then said the same argument works for any number of them. A common mistake is to think the argument claims that the product plus 1 is always prime. It does not. Multiply the first six primes, 2, 3, 5, 7, 11 and 13, to get 30030, and add 1: 30031 is 59 times 509, so it is composite. The argument only needs a new prime to exist, not for the number itself to be prime.
The proof is regularly cited as a model of mathematical reasoning because it is short, rests on a clear idea, and still holds without change.
Eratosthenes and the sieve
A different kind of question is how to find the primes. A method attributed to Eratosthenes of Cyrene, the third-century BCE scholar who worked at the Library of Alexandria and who is also known for estimating the size of the Earth, is described by Nicomachus in his Introduction to Arithmetic. We know it largely through that later account.
To find the primes up to 30:
- Write the numbers from 2 to 30.
- Leave 2 and cross out every second number after it.
- Move to the next number not crossed out, 3, and cross out its multiples.
- Repeat with 5, and its multiples.
- Stop when the next unmarked number is one whose square exceeds 30. That is 7, since 7 times 7 is 49.
What is left is 2, 3, 5, 7, 11, 13, 17, 19, 23, 29: ten primes. The shortcut in the last step works because any composite number up to 30 must have a prime factor no larger than its square root, and such a factor would already have been used to cross it out.
The method is called a sieve because it filters numbers. It is efficient for lists of primes within a modest range, and versions of it are still used in computing.
Open questions that came later
The Greek theory raised questions that stayed unanswered. How are primes spread among the whole numbers? They thin out, but irregularly. Pairs of primes that differ by two, such as 11 and 13 or 17 and 19, keep appearing, and whether there are infinitely many such pairs remains unproven. The distribution of primes was studied seriously from the eighteenth century onward, and the largest known primes are today found with computers.
Primes also link to other number lore. Mersenne primes, of the form 2 to the n minus 1, are tied to the perfect numbers Euclid also treated, and primes appear in the wider story of the sequences mathematicians prized.
What survives
The Greek contribution here is partly a set of definitions and partly a style of proof. Euclid showed that a statement about infinitely many objects can be settled by a finite argument, and the sieve showed that a list of primes can be produced by a simple repeating procedure. Both were done with no algebraic notation, using lines to represent numbers, which makes them an early example of mathematics as argument rather than calculation.