<s>[INST] If $2^n+n^2$ is prime number then $n \equiv 0 \pmod 3 $? Is it true that :

$((2^n+n^2) \in \mathbf{P} \land n \geq 3)\Rightarrow n\equiv 0 \pmod 3  $

I have checked this statement for the following consecutive values of $n$ : $3,9,15,21,33,2007,2127,3759$
Note that $2^n+n^2$ is special case of the form $2^n+k\cdot n$. One can easily show using Dirichlet's theorem that for any odd $n$ sequence $a_k=2^n+k\cdot n$ contains infinitely many primes.
Any idea how to prove or disprove statement above ?
 [/INST] If $n =1 \mod 6$ then $2^n+n^2 = 0 \mod 3$.
If $n =2 \mod 6$ then $2^n+n^2 = 0 \mod 2$.
If $n =4 \mod 6$ then $2^n+n^2 = 0 \mod 2$.
If $n =5 \mod 6$ then $2^n+n^2 = 0 \mod 3$.
P.S. Looking mod 6 is natural, since $2^n \mod 3$ repeats after 2 steps. So to decide what is $2^n \mod 3$, we need to know if $n$ is odd or even. Thus we need to look $\mod 2$ and $\mod 3$ at the same time....
</s>