5

Problem: If $p\geq 5$ is a prime number, show that $p^2+2$ is composite.

Remarks: Now if one observes that $p$ takes the forms $6k+1$ and $6k+5$, the problem is resolved quite easily. However, if one were to choose other forms say $4k+1$ and $4k+3$ then $p^2$ would be of the form $4p+1$ which would yeild the general form $4p+3$ on addition with $2$. Obviously this does not lead to any concrete conclusion. I was wondering whether there is any specific procedure involved in finding the right quotients (For eg. $6$ and $4$) or is this just a random problem solving trick. Moreover, if anyone could provide some intuition as to why $6$ works would be much appreciated.

Student
  • 9,196
  • 8
  • 35
  • 81
  • 1
    Any thoughts? Hint: try the first few cases. See if you can find a common factor. – lulu Nov 04 '16 at 12:59
  • 1
    My strategy: try all prime moduli up to $11$, if none works, probably no modulus will work. For this particular problem, the exponent $2$ might suggest that either modulus $2$ or $2+1$ will work, because Fermat's little theorem. – Wojowu Nov 04 '16 at 13:00
  • 3
    Hint: if $3\nmid p$ then $p^2\equiv 1\mod{3}$, by Fermat's Little Theorem. – user259242 Nov 04 '16 at 13:01
  • By Euclid's algorithm we know that the prime numbers can be written as 6k + 1 or 6k + 5, for an integer k, then you must replace those values ​with p and factor to show that it is a composite number – santiago garcia rincón Mar 02 '21 at 20:57

4 Answers4

7

If $p$ is a prime larger than $3$, then $p \equiv 1$ mod $3$ or $p \equiv 2$ mod $3$, hence in either case $p^2 + 2 \equiv 0$ mod $3$. Meaning $3$ divides $p^2 +2$. $p^2 + 2$ cannot be equal to $3$, so it must indeed be composite.

Nicky Hekster
  • 49,281
3

I suppose the reason is that $p^2 + 2$ is always divisible by 3; hence, taking a quotient by any multiple of 3 will allow you to prove the result. On the other hand, the number $p^2 + 2$ will never be divisible by 2, so you should not expect taking the numbers mod 4 to give you any information.

Mees de Vries
  • 26,947
  • 1
    So what would you suggest as a general stratergy for these types of problems? I guess, we should first try a few cases in order to determine a prime divisor that divides all such numbers and then use its multiples to prove the result. – Student Nov 04 '16 at 15:51
1

So it is in fact quite simple!

p is a prime number, and it is not 2 and it is not 5. We also know it is not even (if it were, then it would be 2 or it would not be prime since 2 would divide it). If we divide p by 6, then the remainder must be 1 or 5. If it were 0, then it would be a multiple of 6 --> even ---> not prime If it were 2, then it would be even ---> not prime If it were 3, then since 3 divides 6, it would be a multiple of 3--->not prime If it were 4, then it would be even --> not prime So that leaves 1 and 5.

So you have two cases. p=5k+1 or p=5k+5.

I hope this helps!

Amber Cathey
  • 11
1

Firstly, $p$ must be odd. Let's see some examples:

$p=5 \Rightarrow p^2 +2=27=3\cdot9$,

$p=7 \Rightarrow p^2 +2=51=3\cdot17$,

$p=11 \Rightarrow p^2 +2=123=3\cdot41$,

This suggests that $p^2 +2$ is a multiple of 3. Let $p$ be the form $6k+1$, with $k$ integer. Then we have $$ (6k+1)^2 +2=36k^2+12k+1+2=3(12k^2+4k+1) $$

Therefore, $p^2 +2$ is composite.

Marcos Paulo
  • 65
  • How do we know we can let $p=6k+1$? This won't be equal to $5$ or $11$ like in the examples you used to deduce that $p^2+2$ is divisible by $3$. – ddswsd Mar 08 '21 at 19:40
  • Won't we also have to let $p=6k-1$ so we can include the primes that $p=6k+1$ misses? – ddswsd Mar 08 '21 at 19:44