Help with Proof: Prove n \equiv 3(mod 6) if 2^n + n^2 is Prime

[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$$ won't 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

 

[M98Ranger]

First, we can rewrite the given expression as 2^n + n^2 = (2^n - 1) + (n^2 + 1). Since n \geq 2, both terms in the parentheses are greater than 1. Therefore, for the expression to be prime, one of the terms must be equal to 1 and the other must be equal to the prime number.

Now, let's consider the possible values of n \mod 6. If n \equiv 1 \mod 6, then n^2 + 1 \equiv 2 \mod 6, which means that n^2 + 1 is not a prime number. Similarly, if n \equiv 5 \mod 6, then n^2 + 1 \equiv 2 \mod 6, which again means that n^2 + 1 is not a prime number. Therefore, the only possible value for n \mod 6 is n \equiv 3 \mod 6.

Now, let's assume that n \not\equiv 3 \mod 6. This means that n \equiv 1 \mod 6 or n \equiv 5 \mod 6. In both cases, n = 6k + 1 or n = 6k + 5 for some integer k. Plugging these values into n^2 + 1, we get n^2 + 1 = (6k + 1)^2 + 1 = 36k^2 + 12k + 2. This expression is clearly not prime, as it is divisible by 2. Therefore, our assumption was incorrect and n \equiv 3 \mod 6 must be true.

Thus, we have proven that if 2^n + n^2 is prime, then n \equiv 3 \mod 6.