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: Problem with prime and composite numbers

  1. Sep 11, 2010 #1
    If p >= 5 is prime, prove that p^2 + 2 is composite.

    So i noticed if we divide any p >= 5 by 6 we only get remainders of 1 or 5.

    6 | 5 , r = 5
    6 | 7 , r = 1
    6 | 11, r = 5
    6 | 13, r = 1
    6 | 17, r = 5 and so on

    so for my proof i am saying for p >= 5, p = 6k + 1 or 6k = 5

    so for the first , p^2 + 2 = (6k+1)^2 + 2 = 36k^2 +12k + 3 = 3(12k^2 + 4k + 1)

    and similarly, p^2 + 2 = (6k+5)^2 + 2 = 36k^2 + 60k + 27 = 3(12k^2 + 20k + 3)

    so both of these are composite so that is great.

    But is there a way i can justify that any prime p >= 5 can be written as 6k + 1 or 6k + 5?

    I mean i can go through a ton of examples and the remainders are only 1 or 5 but examples don't mean anything.

    Can someone help me justify that first step.
     
    Last edited: Sep 11, 2010
  2. jcsd
  3. Sep 11, 2010 #2
    I just thought of something can someone tell me if this is correct. for p primes p >=5 we can only get remainders 1 or 5 when dividing by 6 because if we get 2 3 4 we see what happens

    6k + 2 = 2(3k +1)
    6k + 3 = 3(2k +1)
    6k + 4 = 2(2k + 2) and none of these can be prime because they have factors of either 2 or 3.
    Is this correct?
     
  4. Sep 11, 2010 #3

    jgens

    User Avatar
    Gold Member

    Clearly, every prime number greater than 5 can be written in the form 3k+1 or 3k+2. Then all that you need to demonstrate is that (3k+1)2+2 and (3k+2)2+2 are composite. This is similar to your line of thinking.
     
  5. Sep 11, 2010 #4
    ah ok, thank you very much
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook