any number can be
0,1,2,3,4,5 mod 6
because the number is prime - 0,2,3,4 can be ruled out
since .
You could try arguing along these lines: all primes greater than 3 are odd. Therefore, they must be congruent to either -1, 1, or 3 mod 6. (5 and -1 are equivalent). However, any number greater than 3 that is congruent to 3 mod 6 would be divisible by 3, and hence not prime. Therefore, all primes greater than 3 are congruent to 1 or -1 mod 6.
[EDIT]: This is essentially the same as what aman_cc said.
Keep it simple ... I assume that in the whole post by the way ... since the fact does not contradict the primality of ... just adjust what is below as you wish ...
Let , ,
Then it follows that
But if is prime we must have (otherwise there is a contradiction with respect to the definition of a prime number)
Applying this to the current problem with , the only that are coprime to (in the congruence ring of course) are, surprisingly enough, and (which turns out to be congruent to ).
It follows that if is indeed prime then it must be congruent to
...
Interestingly, it is also possible to prove that this implies that for any prime ... This gives me an idea, I'll be right back !