Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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:
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook