Step 3 — Solution

First turn the statement "if N does not lie in the array, then 2N + 1 is prime" into its logical equivalent "if 2N + 1 is not prime, then N does lies in the array". It's this second statement we'll prove.

Now suppose that 2N +1 is not prime and can therefore be factored as the product of two integers a and b, both greater than 1 and less than 2N + 1. Now 2N + 1 is an odd number, so both a and b must be odd. We can write them as a = 2p + 1 and b = 2q + 1 for some integers p and q greater than or equal to 1. This gives

which gives

But this is the qth element of the pth row of the array, so N lies in the array, proving the assertion above.

Got it, on to the conclusion;
Back to the main article