# Thread: [SOLVED] Proof with Primes

1. ## [SOLVED] Proof with Primes

Prove that if p is a prime number and p is not equal to 3 then 3 divides p^2+2. (HINT:When p is divided by 3, the remainder is either 0, 1, or 2....i.e. for some k, p=3k or 3k+1 or 3k+2....)

Ok, so for p to be prime, it has only 2 positive divisors (1 and itself).

I tried doing this with a contradiction and assuuming 3 does not divide p^2+2, but I got a bit confused.

I also tried something along the lines of Assume p is prime, then p=pk or p=1k for some integer k. But that just confused me. What can I do?

2. Originally Posted by zhupolongjoe
Prove that if p is a prime number and p is not equal to 3 then 3 divides p^2+2. (HINT:When p is divided by 3, the remainder is either 0, 1, or 2....i.e. for some k, p=3k or 3k+1 or 3k+2....)

Ok, so for p to be prime, it has only 2 positive divisors (1 and itself).

I tried doing this with a contradiction and assuuming 3 does not divide p^2+2, but I got a bit confused.

I also tried something along the lines of Assume p is prime, then p=pk or p=1k for some integer k. But that just confused me. What can I do?
It can be done with a direct computation. If P is a prime other than 3, then it is not divisible by 3 and so is of the form 3k+ 1 or 3k+ 2. If P= 3k+1 then $P^2= 9k^2+ 6k+ 1$ so $P^2+ 2= 9k^2+ 6k+ 3= 3(3k^2+ 2k+ 1)$. If P= 3k+ 2 then $P^2= 9k^2+ 12k+ 4$ so $P^2+ 2= 9k^2+ 12k+ 6= 3(3k^2+ 4k+ 2)$.

3. Oh wow, thanks got it! That's the thing about proofs, sometimes they can be so obvious you don't see them!

4. Where p > 3 then p^2 is at 6n+1, so your number is at 6n+3.