chapter 01

Prime numbers

The multiplicative atoms of the whole numbers.

Begin with division

A prime number is a whole number greater than 1 whose only positive divisors are 1 and itself. The number 7 is prime: no whole number other than 1 and 7 divides it exactly. The number 12 is not prime, because $12=3\times4$.

The number 1 is deliberately excluded. If 1 were prime, factorizations could contain as many copies of 1 as we liked, destroying the uniqueness we need later.

The first fifty numbers. Highlighted cells survive the sieve.

12345678910 11121314151617181920 21222324252627282930 31323334353637383940 41424344454647484950

The atoms of multiplication

Every whole number greater than 1 is either prime or can be broken into primes. For example,

$$84=2\times42=2\times2\times21=2^2\times3\times7.$$

More importantly, the final prime factorization is unique apart from its order. This is the fundamental theorem of arithmetic. It says that primes play for multiplication roughly the role atoms play for matter.

$18=2\cdot3^2$$35=5\cdot7$$100=2^2\cdot5^2$$143=11\cdot13$

There is no last prime

Euclid’s argument is short enough to hold in your head. Imagine that $p_1,p_2,\ldots,p_n$ were every prime. Form

$$N=p_1p_2\cdots p_n+1.$$

Dividing $N$ by any prime on our list leaves remainder 1. So either $N$ is prime itself, or it has a prime factor missing from the list. Either way, the supposed complete list was incomplete. There are infinitely many primes.