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

In the book, "Elementary Number Theory - 6th Edition" written by David M. Burton, I have a question. The problem is

If $p$ and $p^2+8$ are both prime numbers, prove that $p^3+4$ is also prime. (p. 58 problem 3.3 #20)

I don't know how to prove this. Thank you very much if you solve this question.

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.

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$.

• I much like this one because it can be explained so nicely without modular arithmetic by expanding a little on it: out of three consequtive numbers, one is divisible by 3. If it's p then p=3 because it's a prime, if not then either p-1 or p+1 and so (p-1)(p+1) must be divisible too. – chx Oct 31 '13 at 0:11
• It's certainly a simple valid argument, but to see that, out of three consecutive numbers, one is divisible by 3 is to use arithmetic modulo 3. – Rosie F Apr 17 at 7:24
• @RosieF Or (simpler) look at the remainder when $p$ is divided by 3... Or use the fact that $\binom{p+1}{3}$ is an integer and 3 is prime. – N. S. Apr 17 at 14:52

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.