Question 411738
<pre><font face = "batangche" color = "indigo" size = 4><b>
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:
<i>Any odd integer greater than 3 which is not divisible by 3 
has remainder of 1 or 5 when divided by 6</i>

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</pre>