March 2009

### Step 2 — Solution

Since *N* lies in the array, it is equal to (2*n*+1)*m*+*n* for some *n* and *m*. Use this to work out 2*N*+1 in terms of *m* and *n*:

2*N*+1=2[(2*n*+1)*m*+*n*]+1=2(2*n*+1)*m*+ 2*n*+1=(2*n*+1)(2*m*+1).

Since 2*m*+1 and 2*n*+1 are both integers greater than 1, this shows that 2*N*+1 has factors that are both greater than one, so it cannot be prime. This shows that if *N* lies in the array, then 2*N*+1 cannot be prime.