# Prime Numbers and Divisibility

• Oct 11th 2009, 10:21 AM
dude15129
Prime Numbers and Divisibility
How do I go about proving this statement.

Use the division theorem to show that every prime except 2 and 3 is of the form 6n+1 or 6n+5.

The division theorem states:
For integers a and b, with b>0, there exist unique integers q and r satisfying a=qb+r, 0≤r<b.
• Oct 11th 2009, 12:21 PM
clic-clac
Let $p>3$ be a prime.

Use the division theorem with $a=p$ and $b=6$. You obtain $q$ and $r$ such as stated in the theorem.
Since $p$ is odd, what can you say about $r$ ?
Finally, try to find a reason to eliminate the cases you don't want (A good way to show something isn't prime is to find a divisor different from $1$ and the thing)