# 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, 2014 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, 2014 at 6:28
• Thanks. How did you prefigure to start with $\gcd(p, 3) = 1$? Why not $\gcd(p,$random integer$) = 1$? Apr 8, 2014 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, 2019 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, 2014 at 18:39
• I misread -- didn't see the ",3q" part Jan 5, 2014 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, 2014 at 10:29
• @DwayneE.Pouiller, $$3q-1,3q,3q+1$$ are any three consecutive integers, right? Apr 8, 2014 at 10:34

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

Theorem $$\ p\ge 2\,$$ & prime $$\,q\nmid p\Rightarrow r = p^{q-1}\!+q\!-\!1$$ is composite, with proper factor $$\,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.$$ $$\ \$$ 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, 2014 at 10:28