Prove that $n^2 + 2^n$ is composite if $n\not\equiv3\pmod{6}$.

Question

If $n>1$ is an integer not of the form $6k+3$, Prove that $n^2 + 2^n$ is composite.

Any idea of how to think about this problem? I have been thinking about it a lot and yet I was not able to come up with anything.

Answer 1

If $n$ is even then $n^2+2^n$ is even, and if $n\equiv\pm1\pmod{6}$ then $n^2+2^n\equiv1+2\equiv0\pmod3$.

Answer 2

If $n$ is even, the proof is trivial. Let $n=2m$, then $n^2+2^n=4m^2+4^m$ which is divisible by 4.

If $n$ is odd, consider $n=6k+1$.

When $k=1, n^2+2^n=177$

When $k=2, n^2+2^n=8361$

When $k=3, n^2+2^n=52469$

We wish to show that for all $k>0$, $(6k+1)^2+2^{6k+1} \equiv 0\pmod 3$. Let $a_k=(6k+1)^2+2^{6k+1}$. Assume the case $n=k$ is true. When $n=k+1$ $$a_{k+1}=(6(k+1)+1)^2+2^{6(k+1)+1}=(6k+1)^2+36+12(6k+1)+64(2^{6k+1})\equiv (6k+1)^2+2^{6k+1}=a_k$$

Thus, this means $$a_k\equiv a_{k-1} \equiv a_{k-2}\equiv...\equiv a_1\equiv 0\pmod 3$$ Our inductive proof is complete.