5
$\begingroup$

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.

$\endgroup$
18
$\begingroup$

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$

$\endgroup$
4
  • 1
    $\begingroup$ It is very easy. Learn! Very useful. Regards. $\endgroup$ – Supriyo Jan 6 '14 at 5:32
  • 3
    $\begingroup$ 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. $\endgroup$ – ShreevatsaR Jan 6 '14 at 6:28
  • $\begingroup$ Thanks. How did you prefigure to start with $\gcd(p, 3) = 1$? Why not $\gcd(p, $random integer$) = 1$? $\endgroup$ – Dwayne E. Pouiller Apr 8 '14 at 10:30
  • $\begingroup$ 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 ? $\endgroup$ – Adren May 1 '19 at 5:55
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ @oldrinb, that's what is written in the POST, right? $\endgroup$ – lab bhattacharjee Jan 5 '14 at 18:39
  • $\begingroup$ I misread -- didn't see the ",3q" part $\endgroup$ – obataku Jan 5 '14 at 18:40
  • $\begingroup$ 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)? $\endgroup$ – Dwayne E. Pouiller Apr 8 '14 at 10:29
  • $\begingroup$ @DwayneE.Pouiller, $$3q-1,3q,3q+1$$ are any three consecutive integers, right? $\endgroup$ – lab bhattacharjee Apr 8 '14 at 10:34
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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)? $\endgroup$ – Dwayne E. Pouiller Apr 8 '14 at 10:28

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.