Prove that $n^2 + 2^n$ is composite if $n\not\equiv3\pmod{6}$. 
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.

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.
