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

  • $\begingroup$ 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. $\endgroup$ – chx Oct 31 '13 at 0:11
  • $\begingroup$ 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. $\endgroup$ – Rosie F Apr 17 '19 at 7:24
  • $\begingroup$ @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. $\endgroup$ – N. S. Apr 17 '19 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.