Simple prime no. quesiton Prove that any prime number > 3 is either of the form 6n + 1 or 6n - 1,
my attempt,
with my method I didn't know how to deal with the prime number 5, so I done it separately, 5 = 6(1) - 1, which is true
Take any $N\in\mathbb{N}$ $N>5$, and divide it by 6, so we have $N = 6n + r$ where $n\in \mathbb{N}$ and $r = \{x\in\mathbb{Z} | 0 \leq x \leq 5\}$
If $ r=2$ then $2|N$ so $N$ Is not prime
If $r = 3$ then $3|N$ so $N$ is not prime
If $r = 4$ then $2|N$ so $N$ is not prime
So we have either $r = 5, 1$
if $r = 1$ $N = 6n + 1$
if $r = 5$ $N = 6(n+1) - 1$, $n+1 \in \mathbb{Z}$ so we're done
I have a few queries - 
How can I generalise this proof for the prime number 5?
With proofs like this is it mostly practise or do you just "get" it, despite this being an easy proof, I still struggled.
 A: Hint: let $n = 0$; then we have the case that $r = 5$
$$5 = 0\cdot 6 + 5 = 6(0 + 1) - 1, \quad (0 + 1) \in \mathbb N$$ 
Put differently, $5\equiv -1\pmod 6$, so so is congruent to any number of the form is $6n - 1.$
A: Any integer mod 6 maps into $\{0,1,2,3,4,5\}$.  A number which maps to 0, 2, or 4 is divisible by 2, hence not prime.  A number which maps to 0 or 3 is divisible by 3, hence not prime.  Thus, if a number is prime, it must map to 1 or 5.  These correspond to +1 and -1 respectively.
A: The way I can see to generalise is this:
If $a$ and $p$, $a<p$, are not coprime (i.e. they share a factor), then certainly if a number is of the form $kp+a$ it is a multiple of a factor of a, and hence is not prime.
Thus, the primes are always of the form $kp + a$, where $a$ ranges over all the numbers smaller than, and coprime to $p$.
In  number theoretical language we would say the primes are always units modulo $n$ for any $n$ they are not factors of.
A: You can generalize from $\,6\to m\,$ as follows: $\ n$ is coprime to $m$ iff its remainder $r = n\ {\rm mod}\ m\,$ is coprime to $m,\,$ i.e $\,r\,$ takes one of the $\,\phi(m)\,$ values $\in\{1,\ldots,m\!-\!1\}$ that are coprime to $m.\,$ In particular this is true for any prime  $\,n = p\,$  greater than any prime factor of $m$. For example, for $m = 10 = 2\cdot 5\,$ we find that any prime $>5$ has one of the values $\{1,3,7,9\} \equiv \pm\{1,3\}\!\pmod{10}.$
