Show that every prime number other than 2 or 3 has the form

Show that every prime number other than 2 or 3 has the form 6k+1 or 6k+5 for k which is an integer

Solution

A prime number that is more than 3 cannot be of the form 6k (divisible by 2,3), 6k±2 (divisible by 2), 6k±3 (divisible by 3), 6k±4 (divisible by 2). So it\'s either of the form 6k±1 or 6k±5. But these two are equivalent of course, since 6k+1 is 6(k+1) - 5. So all prime numbers have to be of the form 6k±1.