6
$\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$

5 Answers 5

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

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

$\endgroup$
4
$\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$ Commented Apr 8, 2014 at 10:28
-1
$\begingroup$

We know that any prime no greater than 3 can be written in the form of 6k±1,

We can say $p²= (6k±1)² , p²+2= (6k±1)²+2 : = 3(12k²±4k+3).$ As p≠3m

P must be equal to less than or equal to 3. We can check it for 2,3

If $p=2 p²+2=6$ which can not be possible as 6 is composite And $p=3: p²+2= 11$ Which mean p should be equal to 3

$\endgroup$
1
  • $\begingroup$ This is essentially the same as lab's answer $9$ years ago (put $q = 2k)$, which is essentially the same as Supriyo's (but eliminating modular language). Please don't duplicate prior answers. $\endgroup$ Commented Apr 9, 2023 at 17:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .