Let \(n\ge2\) be an integer such that \(2^n+n^2\) is prime. Prove that \[ n\equiv3\pmod6. \]
Solution
1. The integer \(n\) is odd.
If \(n\) were even, then both \(2^n\) and \(n^2\) would be even. Hence \[ 2^n+n^2 \] would be even. Since \(n\ge2\), this number is greater than \(2\), so it would not be prime. Therefore \(n\) is odd.
2. The integer \(n\) is divisible by \(3\).
Suppose instead that \(3\nmid n\). Then \[ n^2\equiv1\pmod3. \] By step 1, \(n\) is odd, so \[ 2^n\equiv(-1)^n\equiv-1\pmod3. \] Therefore \[ 2^n+n^2\equiv0\pmod3. \] An odd integer \(n\ge2\) not divisible by \(3\) must satisfy \(n\ge5\), so \(2^n+n^2>3\). Thus the displayed divisibility by \(3\) contradicts the assumed primality. Hence \(3\mid n\).
3. One has\[ \boxed{n\equiv3\pmod6.} \]
By step 1, \(n\) is odd, and by step 2, \(3\mid n\). The odd multiples of \(3\) are exactly the integers congruent to \(3\) modulo \(6\).
4. Q.E.D.
Step 3 is the required congruence.