Is this a true statement? Can you prove?

• Apr 25th 2012, 05:16 PM
goalkeeper00
Is this a true statement? Can you prove?
Let n be a natural number. If 3 does not divide (n2 +2), then n is not a prime number or n = 3.
• Apr 26th 2012, 05:57 AM
emakarov
Re: Is this a true statement? Can you prove?
In plain text, it is customary to write n^2 for n2.

This seems true. If 3 does not divide n^2 + 2, then n^2 + 2 = 3k + 1 or n^2 + 2 = 3k + 2 for some k. In the latter case, n is divisible by 3. Suppose that n^2 = 3k - 1 and, towards contradiction, assume that n is prime. Then n = 6m + 1 or n = 6m - 1 for some integer m as described here. Try to derive a contradiction.

Maybe there is an easier proof...
• Apr 26th 2012, 07:09 AM
princeps
Re: Is this a true statement? Can you prove?
Quote:

Originally Posted by goalkeeper00
Let n be a natural number. If 3 does not divide (n2 +2), then n is not a prime number or n = 3.

Let $n=p$, where $p$ is a prime number greater than $3$ , then :

$p \equiv 1 \pmod 3 ~\text{or}~p\equiv 2 \pmod 3$

Hence :

$p^2 \equiv 1 \pmod 3 \Rightarrow p^2+2 \equiv 0 \pmod 3$