• Support PF! Buy your school textbooks, materials and every day products Here!

Number Thry: Divisibilty, perfect square.

  • Thread starter mattmns
  • Start date
1,058
6
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 [itex]p \geq 5[/itex], then [itex]p^2 + 2[/itex] 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 [itex]n^2 - 1 = 3k+1[/itex] and then breaking into evens and odds, but that did not get anywhere. I was also trying to get a contradiction with [itex]3k+2 \mid n[/itex], 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 [itex]p^2+2[/itex] is composite. But for the latter I am stuck again. Any ideas here?

Thanks!
 

Answers and Replies

Gokul43201
Staff Emeritus
Science Advisor
Gold Member
6,987
14
Can you have a number 3k that is the square of a prime greater than 4?
 
1,058
6
Obviously not, otherwise the "prime" would be divisible by 3 :smile: That takes care of the second part, thanks!
 
Last edited:
682
1
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
Homework Helper
3,344
4
Induction? Prove its not true for n=1, then n=k+1.
 
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
6,987
14
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.
 
1,058
6
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 :biggrin:
 

Related Threads for: Number Thry: Divisibilty, perfect square.

Replies
1
Views
2K
Replies
9
Views
6K
  • Last Post
Replies
11
Views
6K
  • Last Post
Replies
8
Views
6K
  • Last Post
Replies
2
Views
6K
Replies
13
Views
9K
  • Last Post
Replies
1
Views
2K
Top