March 2009

### Step 3 — Solution

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

Now suppose that 2*N* +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 2*N* + 1. Now 2*N* + 1 is an odd number, so both *a* and *b* must be odd. We can write them as *a* = 2*p* + 1 and *b* = 2*q* + 1 for some integers *p* and *q* greater than or equal to
1. This gives

*N*+ 1 =

*ab*= (2

*p*+ 1)(2

*q*+ 1) = 2

*p*(2

*q*+ 1) + 2

*q*+ 1,

which gives

*N*=

*p*(2

*q*+ 1) +

*q*.

But this is the *q*th element of the *p*th row of the array, so *N* lies in the array, proving the assertion above.