## Finding “new” primes

To accompany How to Solve it, I also bought How to Prove It: A Structured Approach which deals with the construction of proofs.

I am puzzled, though, by its treatment of Euclid’s famous proof of the infinite order of the set of primes.

Not because it gets the proof wrong – but because I do not understand the answer it gives to one part of one exercise.

Now the proof (this is my summary not the book’s) runs like this:

Suppose you decide that the number of primes is finite, the set $p_1 ... p_n$ (where $p_1$ is 2 and so on). You then form a number $m$ from the product of these primes plus 1 – $m = p_1 \times p_2 \times ... \times p_n + 1$. This number cannot be a prime and yet is not divisible by any of the primes. Hence we have a contradiction and the set of primes must be infinite.

Now the book asks the following:

The proof of [the theorem] gives a method for finding a prime number from any in a given list of prime numbers:
(a) Use this method to find a prime different from 2, 3, 5 and 7
(b) Use this method to find a prime different from 2, 5 and 11

Now, the first seems easy enough:

$p_{new} = 2 \times 3 \times 5 \times 7 + 1 = 211$

and the book agrees with my calculation.

But what of the second?

Well, $2 \times 5 \times 11 + 1 = 111$, but that’s not a prime at all. The book gives the answer as “3 and 37” (which obviously are primes) but I cannot see what formal method is used from the list of “2, 5 and 11” to generate these numbers.

The obvious suggestion is that I have missed the “method” in the theorem as set out in the book, but I have reread it many times and I cannot see where I have missed anything (it is really just a longer version of my summary).

Can someone set out the formal method that would work with a partial list such as 2, 5 and 11?