Proving the Divisibility Rule for Prime Numbers: A Homework Statement

[scottstapp]

Homework Statement

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

Homework 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 don't 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

 

[rasmhop]

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.

 

[scottstapp]

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

 

[rasmhop]

Thank you, is this what I would do? ...

Yes that is the approach I would suggest.

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?

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

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.

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.

 

[scottstapp]

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.

 

[rasmhop]

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.

Yes you need to add this case, and then you're done.

 

[scottstapp]

Thanks for all your help