# Prove that any prime p > 3 is either of the form 6k + 1 or of the form 6k + 5 for some integer k.

## Solution

By the division algorithm, any integer can be written in one of the forms 6k, 6k + 1, 6k + 2, 6k + 3, 6k + 4, 6k + 5.

Of these, 6k, 6k + 2 and 6k + 4 are even, and 6k +3 is divisible by 3.

Thus, none of these can represent a prime > 3.

Thus p must be of the form 6k + 1 or 6k + 5.