If $p$ and $p^2+8$ are both prime numbers, then $p^3+4$ is prime.

Solution 1:

It's a trick question. This is only possible for $p=3$.

For suppose that $p$ was such that $p^2+8$ is prime, and $p \neq 3$. Then, $p \equiv 1 \pmod{3}$ or $p \equiv - 1 \pmod{3}$ and in either case $p^2 \equiv 1 \pmod{3}$. Thus, $p^2+8$ is divisible by $3$, and can't be a prime.

Hence, it remains to check that $3^3 + 4 = 31$ is prime. It happens to be true.

Solution 2:

Hint If $ p \neq 3$ prove that $p^2+8 \equiv 0 \pmod {3}$.

Thus $3 |p^2+8$. Can you finish it from here?

P.S. You can prove the first claim without modular arithmetic by observing that

$$p^2+8=p^2-1+9=(p-1)(p+1)+9$$ Both terms in the sum are multiple of $3$.

Solution 3:

Suppose $p^3+4$ is not prime and note that for $p=2$, $p^2+8$ is not prime and for $p\neq2$ $(p,p^3+4)=1$ which implies that $p=3$ or $p=5$ by Euclidean Algorithm. If $p=3$ then $p^2+8=17$ and $p^3+4=31$ is prime. If $p=5$ then $p^2+8=33$ is not prime. Therefore $p^3+4$ is prime.