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?


3 responses to “Finding “new” primes”

  1. Looks like you just have to factor the result. 111 = 3 * 37
    2 * 7 + 1 = 15 = 3 * 5
    Haven’t found an example that doesn’t work.
    2 * 5 + 1 = 11

    1. Yes, but any non-prime number is a product of primes. What’s the universal method?

      1. I think what they are saying is that this method gives you primes that you don’t already have. So you can always multiply the primes you receive with the rest of what you have and get new ones. And then use those to get more, etc. probably not what you’re looking for. Sorry.

%d bloggers like this: