Help with a proof.

[gimpy]

Let n \geq 2 be an integer such that 2^n + n^2 is prime. Prove that n \equiv 3(mod 6).

Ok this is what i have so far.
n \equiv 3(mod 6)\\ \Rightarrow 6|n-3\\ \Rightarrow n - 3 = 6k \\ \Rightarrow n = 6k + 3 \\.

Ok well i think i can use a proof by contradition. Obviosly n cannot be an even number because 2^n + n^2 wont be prime. So n must be 6k + 1 or 6k + 3 or 6k + 5. Now when i plug all these into 2^n + n^2 and mess around with it for a bit i just can't seem to prove it. Can anyone help me out?

[matt grime]

It suffices to consider the 2^n + n^2 mod 3.

Clearly, if n is NOT congruent to 0 mod three, then as n must be odd, 2^n = -1 mod 3 and n^2 = 1 mod 3, thus 2^n + n^2 =0 mod 3 and can't be prime (n=1 excepted)

Hence n is divisble by 3, and not by two, thus it is congruent to 3 mod 6