Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.


Matt E's edited answer -

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?

share|improve this question

4 Answers 4

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$

share|improve this answer
1  
It is very easy. Learn! Very useful. Regards. –  Dutta Jan 6 at 5:32
3  
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 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 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

share|improve this answer

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

share|improve this answer
    
@oldrinb, that's what is written in the POST, right? –  lab bhattacharjee Jan 5 at 18:39
    
I misread -- didn't see the ",3q" part –  oldrinb Jan 5 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 at 10:29
    
@DwayneE.Pouiller, $$3q-1,3q,3q+1$$ are any three consecutive integers, right? –  lab bhattacharjee Apr 8 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.

share|improve this answer
    
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 at 10:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.