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: Prime Number Proof

  1. Jan 23, 2010 #1
    1. The problem statement, all variables and given/known data

    If p is a prime greater than 3, then p leaves a remainder of 1 or 5 when divided by 6.

    2. Relevant equations

    I have been given the definition of composite which is an integer a is composite if there exist integers b and c such that a=bc where both b>1, c>1

    3. My attempt
    Let P be a prime number greater than 3
    P=6q+r 1<=r<=5 by the division algorithm

    This is where I get lost. I'm not even sure if line two is the way to approach this proof.
    SHould I do separate cases such as
    CaseI: r=1 so p=6q+1 ?

    I dont think so because that would not be proving anything but rather it would be a retelling of what I need to prove.

    Thanks for your time and help
  2. jcsd
  3. Jan 23, 2010 #2
    You need to do all the cases that you want to show aren't possible and show that they are impossible. So for instance:

    Case 1 (r = 2):
    Then p=6q+2 = 2(3q+1) which isn't prime unless q=0, but then p=6*0+2=2 which is a contradiction.

    You now need to do the cases r=3,4.
  4. Jan 23, 2010 #3
    Thank you, is this what I would do?

    Case 1: r=2, p=6q+2, p=2(3q+1) which is not prime unless q=0, but then p=6*0+2=2 which is a contradiction of the fact that p>3.

    Case 2: r=3, p=6q+3, p=3(2q+1) which is not prime unless q=0, but then p=6*0+3 which is a contradiction of the fact that p>3.

    Case 3: r=4, p=6q+4, p=2(3q+2) which is not prime

    I feel as though I need to state why it is that p=2(3q+1), p=3(2q+1), and p=2(3q+2) are not prime. What I mean is to me it seems like this is not sufficient enough to just state that they are not prime. But wait, they are not prime because they are two integers being multiplied to create p correct?

    Also, would I need to actually show that the remainder is 1 or 5 via the cases p=6q+1 and p=6q+5? Because it seems as though all I am doing is saying that the remainder cannot be 2,3,4 but I say nothing about it being 1 or 5.

    Thank you very much for your time and help
  5. Jan 23, 2010 #4
    Yes that is the approach I would suggest.

    Yes mn is composite if both m and n are >1.

    That is all you're saying, but it's also all you're asked to show. If the remainder isn't 0,2,3,4, then it must be 1 or 5. You don't need to prove that it can be either. Even if every prime >3 left a remainder of 1 the statement would be true. It's also true that any prime >3 leaves a remainder of 1,5 or 2 on division by 6. In reality it never leaves a remainder of 2, but the statement is still true in the sense that saying "the king is male or female" is true even though the king is never female.
  6. Jan 23, 2010 #5
    Thank you for all your help rasmhop. All I would need to add is another case that has r=0 correct? This is obvious that it is not a prime but it must be shown nonetheless.
    Last edited: Jan 23, 2010
  7. Jan 23, 2010 #6
    Yes you need to add this case, and then you're done.
  8. Jan 23, 2010 #7
    Thanks for all your help
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook