Number Thry: Divisibilty, perfect square.

[mattmns]

Here is the question:
-------------
Show that a perfect square is never of the form 3k+2 for any k. Conclude that if p is prime and p \geq 5, then p^2 + 2 is always composite.
-------------

We are at the very start of the book, so there is not very much available to use. We have defined a|b, primes, floor and ceiling (which I don't think will play a role here), and have the division theorem.

For the first part I think it is going to be proved by contradiction, so I have been trying to get some kind of parity going with both sides. I tried using n^2 - 1 = 3k+1 and then breaking into evens and odds, but that did not get anywhere. I was also trying to get a contradiction with 3k+2 \mid n, but again was able to get nothing. Any ideas?

For the second part I was using the result of the first. Since a perfect square is not of the form 3k+2 it must be of the form 3k+1 of 3k, for the former it is easy to see that p^2+2 is composite. But for the latter I am stuck again. Any ideas here?

Thanks!

 

[Gokul43201]

Can you have a number 3k that is the square of a prime greater than 4?

 

[mattmns]

Obviously not, otherwise the "prime" would be divisible by 3 That takes care of the second part, thanks!

 

[tim_lou]

1) look at things mod 3.
a can either be:
a=1,2,-1 mod 3 => a^2=1 mod 3

2) use mod 3 again.

 

[Gib Z]

Induction? Prove its not true for n=1, then n=k+1.

 

[Gokul43201]

1) look at things mod 3.
a can either be:
a=1,2,-1 mod 3 => a^2=1 mod 3

There's a tiny error there (should be a=0,1,2 mod 3)...but the method works.

 

[mattmns]

We can't techincally use mod, but the idea behind it is perfect for the proof, thanks for the idea, I got it all worked now