# For which primes p is $p^2 + 2$ also prime?

Origin — Elementary Number Theory — Jones — p35 — Exercise 2.17 —
For which primes $$p$$ is $$p^2 + 2$$ also prime?

Only for $$p = 3$$. If $$p \neq 3$$ then $$p = 3q ± 1$$ for some integer $$q$$, so $$p^2 + 2 = 9q^2 ± 6q + 3$$ is divisible by $$3$$, and is therefore composite.

(1) The key here looks like writing $$p = 3q ± 1$$. Where does this hail from? I know $$3q - 1, 3q, 3q + 1$$ are consecutive. $$p$$ is prime therefore $$p \neq 3q$$?

(2) How can you prefigure $$p = 3$$ is the only solution? Does $$p^2 + 2$$ expose this? On an exam, I can't calculate $$p^2 + 2$$ for many primes $$p$$ with a computer — or make random conjectures.

Use Fermat's little theorem.

If $\gcd(p,3) = 1$, $p^2 \equiv 1 \pmod 3$ that gives $p^2 + 2\equiv 3 \pmod 3$.

Thus only possibility is $p = 3$

• It is very easy. Learn! Very useful. Regards. Jan 6 '14 at 5:32
• That $p^2 \equiv 1 \bmod 3$ if $3$ does not divide $p$, certainly does not require Euler's totient theorem or Fermat's little theorem! Those are overkill for such an easy-to-check fact. Jan 6 '14 at 6:28
• Thanks. How did you prefigure to start with $\gcd(p, 3) = 1$? Why not $\gcd(p,$random integer$) = 1$? Apr 8 '14 at 10:30
• And what about $p^2-2$ ? Numerical evidence suggests that there are many primes $p$ such that $p^2-2$ is itself prime (e.g. all the following ones : 2, 3, 5, 7, 13, 19, 29, 37, 43, ... but not 11, 17, 23, 31, 41, 53, 59, 67, 73, ...). Are there infinitely many ? May 1 '19 at 5:55

Any integer $n$ can be written as $3q\pm1, 3q$ where $q$ is an integer

Now we can immediately discard $3q$ as it is composite for $q>1$

Now $\displaystyle(3q\pm1)^2+2=9q^2\pm6q+3=3(3q^2\pm2q+1)$

Observe that $3q^2\pm2q+1>1$ for $q\ge1,$ hence $\displaystyle(3q\pm1)^2+2$ is composite

• @oldrinb, that's what is written in the POST, right? Jan 5 '14 at 18:39
• I misread -- didn't see the ",3q" part Jan 5 '14 at 18:40
• Can you please explain where $3q \pm 1$ hails from? It feels uncanny. The rest of your answer isn't what I'm querying about. Can you please answer my edited post in your answer (not in comments)? Apr 8 '14 at 10:29
• @DwayneE.Pouiller, $$3q-1,3q,3q+1$$ are any three consecutive integers, right? Apr 8 '14 at 10:34

Hint $\$ Apply the special case $\,q=3\,$ of the following

Theorem $\$ If $\ p,\,q\$ and $\,r = p^{q-1}\!+q\!-\!1\,$ are all prime then $\, p = q$.

Proof $\,$ If $\,p\ne q\,$ then $\,q\nmid p\,$ hence, by little Fermat, $\,q\mid \color{#c00}{p^{q-1\!}-1}\,$ so $\ \color{#0a0}{q\mid r}\,=\, \color{#c00}{p^{q-1}\!-1}+q$. However $\,p,q \ge 2\,$ so $\,p^{q-1}\!\ge 2\,$ so $\,r> q,\,$ so $\,\color{#0a0}q\,$ is a $\color{#0a0}{proper}$ factor of $\,r,\,$ contra $\,r\,$ prime. $\ \$ QED

Whenever you see a quantity of the form $x^2 + a$ in a basic number theory course (especially in hw. or on an exam), you will want to think about what divisibilities it has by various small numbers.

E.g. any square is either $\color{purple}0$ or $\color{teal}1$ $\begin{cases}\mod 3, & \text{ depending on whether or not$3$divides$x$} \\ \mod 4, & \text{depending on whether or not$2$divides the number being squared} \end{cases}$,
and $0,$ $1$, or $4$ mod $8$ (depending on whether or not $2$ or $4$ divide the number being squared).

Thus, when you see $p^2 + 2$, you should think: $\begin{cases} = \color{purple}0 + 2 & \mod3 \text{ , if$3$divides$p$} \\ = \color{teal}1 + 2 \equiv 0 & \mod3 \text{ , if$3 \not| p$} \end{cases}$.
Since the only prime that can be $0$ mod $3$ is $3$ (and $p^2 + 2$ will certainly be $> 3$), this answers your question immediately.

• Thanks. I'm sorry for unchecking the answer - I only cognized now I don't fully grasp it. Can you please answer my edited post in your answer (not in comments)? Apr 8 '14 at 10:28