Show that any prime number greater than 3 has remainder 1 or 5
when divided by 6;
Every prime number greater than 3 is odd and not divisible by 3.
We will prove a stronger theorem:
Stronger theorem:
Any odd integer greater than 3 which is not divisible by 3
has remainder of 1 or 5 when divided by 6
Every integer greater than 3 which is not divisible by 3 is
of the form 3n+1 or 3n+2.
If n is even, say n = 2k then 3n+1 = 3(2k)+1 = 6k+1, which leaves
a remainder of 1 when divided by 6
If n is even, say n = 2k then 3n+2 = 3(2k)+2 = 6k+2, which is even,
so we don't need to consider this case.
If n is odd, say n = 2k+1, then 3n+1 = 3(2k+1)+1 = 6k+3+1 = 6k+4,
which is even, so we don't need to consider this case either.
If n is odd, say n = 2k+1, then 3n+2 = 3(2k+1)+2 = 6k+3+2 = 6k+5,
which leaves a remainder of 5.
So the theorem is proved.
Edwin
