1. Limited time only! Sign up for a free 30min personal 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!

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