Number Theory: A Very Short Introduction

In each case we’ve generated at least one new prime number that wasn’t in our original list.

A more formal proof is as follows. We’ll suppose that there are finitely many primes, which we’ll call p₁, p₂, …, and p_n, and we’ll form the number

Now, each of these primes divides their product, , and so cannot also divide N because this would leave a remainder of 1. So either N is a new prime, or N is a composite number in which case it must split into new primes. In either case, there must exist a prime that’s different from p₁, p₂, …, and p_n, and this contradicts our assumption that these were the only primes. Our original assumption must therefore be false, and so there are infinitely many primes.

Factorizing into primes

Earlier I mentioned that the prime numbers are the building blocks for our counting system, and we’ll now explore this idea further.

Starting from any collection of primes, we can build up further numbers by multiplication: for example, beginning with the primes 2 and 3 we can construct the numbers

and any other number of the form , where and .

Turning things around, we see that every integer greater than 1 splits into primes, because if the number n is composite then we can write for smaller integers a and b: for example, . If a is composite, then we can split it up further, and similarly for b. Continuing in this way, after a finitely many steps we’ll eventually obtain n as a product of primes.

Moreover, if we’re given a number such as 108, then we can split it up in more than one way: for example,

In the same way, we can write

We can illustrate all these factorizations as tree diagrams (see Figure 18).

18. Factorizations of 108 and 630.

In each case the prime factors at the lower ends of the trees are exactly the same, but they appear in a different order. This suggests the following result, which is known as the ‘fundamental theorem of arithmetic’. Although it must have been familiar to mathematicians for hundreds of years, it seems not to have been proved formally until Gauss did so in his Disquisitiones Arithmeticae of 1801.

Fundamental theorem of arithmetic: Every integer greater than 1 is either a prime number or can be written as a product of primes. Moreover, there is only one factorization into its prime factors, apart from the order in which they appear.

We can now see why we don’t wish 1 to be a prime number—for, if it were, then we could write, for example,

so that the uniqueness of the prime factorization would be lost.

Using the fundamental theorem of arithmetic, we can now write every positive integer as a product of primes in a standard way, by listing its prime factors in increasing order of size, with each one raised to the appropriate power: for example,

In general, if the prime factors of the number n are p₁, p₂, …, and p_r, where each prime p_i is raised to the power e_i and the primes are listed in increasing order, then we write

This is called the canonical form of the prime factorization of n, and we’ll often write prime factorizations in this way.

To conclude this section we’ll return briefly to least common multiples and greatest common divisors. In Chapter 2 we showed that and by listing the multiples and divisors of 90 and 54. But a quicker method is to write each number as a product of primes in canonical form:

where the extra factor 5⁰ (which equals 1) is introduced so that the primes that appear (2, 3, and 5) are the same. Then:

to find lcm (90, 54), we look at each prime factor in turn, take the larger power that appears—that is, 2¹, 3³, and 5¹—and multiply them to give ;

to find gcd (90, 54), we look at each prime factor in turn, take the smaller power that appears—that is, 2¹, 3², and 5⁰—and multiply them to give .

In general, if a and b are written in canonical form as

(where we introduce the exponent 0 whenever a particular prime doesn’t appear), then

where max (e, f) is the larger of e and f, and

where min (e, f) is the smaller of e and f.

We can now revisit a result from Chapter 2—that, for any numbers a and b,

To explain why this is true we note first that, for any numbers e and f,

—for example, . Then the power of the first prime factor p₁ on the left-hand side of the result that we’re trying to prove is

which is the power of p₁ on the right-hand side. So the powers of p₁ on the two sides match, and the same is true for all the other prime factors. So the two sides are equal.

Searching for primes

Are there any formulas for producing primes? Here are some historical attempts at finding them.Euler’s primes

Leonhard Euler was obsessed with prime numbers, as we’ll see throughout this book. In 1771 he investigated the formula

and made the surprising observation that if we substitute every number n from 1 to 40 in turn, then we always get primes:

and so on, up to

These are all prime numbers, but the formula may also fail to produce primes: for example,

Likewise, the formula

produces prime numbers for every number n from 1 to 79, but not for 80 or many larger numbers. So neither of these formulas always gives primes.Mersenne primes

Particularly important among the prime numbers, for reasons that will soon become clear, are those that are one less than a power of 2, such as

Numbers of the form