1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number Thry: Divisibilty, perfect square.

  1. Jan 19, 2007 #1
    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!
     
  2. jcsd
  3. Jan 19, 2007 #2

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Can you have a number 3k that is the square of a prime greater than 4?
     
  4. Jan 19, 2007 #3
    Obviously not, otherwise the "prime" would be divisible by 3 :smile: That takes care of the second part, thanks!
     
    Last edited: Jan 19, 2007
  5. Jan 19, 2007 #4
    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.
     
  6. Jan 19, 2007 #5

    Gib Z

    User Avatar
    Homework Helper

    Induction? Prove its not true for n=1, then n=k+1.
     
  7. Jan 19, 2007 #6

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    There's a tiny error there (should be a=0,1,2 mod 3)...but the method works.
     
  8. Jan 19, 2007 #7
    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:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?