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

Origin — Elementary Number Theory — Jones — p35 — Exercise 2.17 —

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 cognize $3q - 1, 3q, 3q + 1$ are consecutive.

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

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

(3) Can someone please clarify why I'd prefigure or think about mod 3, mod 4, mod 8?
Why not consider mod of some random natural number?

(4) The last paragraph considers mod 3. How can I prefigure this?

-

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. – Dutta 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. – ShreevatsaR 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$? – Dwayne E. Pouiller Apr 8 '14 at 10:30

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

-

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? – lab bhattacharjee Jan 5 '14 at 18:39
I misread -- didn't see the ",3q" part – oldrinb 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)? – Dwayne E. Pouiller Apr 8 '14 at 10:29
@DwayneE.Pouiller, $$3q-1,3q,3q+1$$ are any three consecutive integers, right? – lab bhattacharjee Apr 8 '14 at 10:34

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)? – Dwayne E. Pouiller Apr 8 '14 at 10:28