Prove that $2^p+p^2$ is prime for $p=3$ only I do know that all prime numbers larger than $3$ can be expressed as $3k + 1$ and or $3k + 2$. Plugging those in I still see no solution.
EDIT: $p$ can only be a prime number.
 A: Whether $p\equiv 1\pmod 3$ or $p\equiv 2\pmod 3$, either way $p^2\equiv 1\pmod 3$
Since $p$ must be odd, $2^p\equiv 2\pmod 3$
Adding them together gets you a number that is divisible by $3$.
A: So you know that all primes larger than 3 are of the form $3k + 1$ or $3k + 2$.
Do you know which of those forms $2^p$ is? Obviously $2 = 3 \times 0 + 2$. Then $4 = 3 \times 1 + 1$, $8 = 3 \times 2 + 2$, $16 = 3 \times 5 + 1$, $32 = 3 \times 10 + 2$, etc. In short, $2^n \equiv 2 \pmod 3$ if $n$ is odd, so if $p$ is a prime number greater than 2, it's odd, and consequently $2^p \equiv 2 \pmod 3$. Let's say $2^p = 3m + 2$ for later reference.
Now let's review what happens with the squares of primes. Suppose $p = 3k + 2$. Then $p^2 = (3k + 2)^2 = 9k^2 + 12k + 4 \equiv 1 \pmod 3$.
And so $2^p + p^2 = (3m + 2) + (9k^2 + 12k + 4) = 9k^2 + 12k + 3m + 6$, and, just in case it's not obvious enough: $$\frac{9k^2 + 12k + 3m + 6}{3} = 3k^2 + 4k + m + 2.$$
A: Hint: If $p$ is odd, then $2^p+p^2 \equiv -1+p^2 =(p-1)(p+1) \bmod 3$.
A: From Fermat's little theorem, it follows that $2^p \equiv 2 \pmod p$. Then $2^p + p^2 \equiv 2 \pmod p$... oops, that doesn't help, never mind.
Oh, wait a minute: since $2 = 3 - 1$, then $p^2 \equiv 1 \pmod 3$ by Fermat's little theorem. That means $p^2$ is of the form $3k + 1$.
So as long as $2^p \not \equiv 2 \pmod 3$, the number $2^p + p^2$ has a shot at being prime. However, since $2^2 \equiv 1 \pmod 3$ but $2^3 \equiv 2 \pmod 3$, it follows that the powers of $2$ alternate $2, 1 \pmod n$ according to whether $n$ is odd or even. But since $p > 2$ is odd, it follows that $2^p \equiv 2 \pmod 3$. Therefore, with $p > 3$ odd, $2^p + p^2$ must be a multiple of $3$.
And the only prime multiples of $3$ are $3$ itself and $-3$. So it is only with $p = 3$ that we have $2^3 + 3^2 = 17$.

Just as an amusing aside: given $p = -3$, we have $$2^p + p^2 = \frac{73}{8}.$$
