# Prove or disprove that all primes except $2$ and $3$ can be expressed in the form $6n\pm1$ which $n\in\mathbb{N}$.

Prove or disprove that all primes except $2$ and $3$ can be expressed in the form $6n\pm1$ which $n\in\mathbb{N}$.

I observe this when I'm reading the prime table. Is this already a theorem or it's new? Thank you.

-
Consider the possible remainders when a prime $p$ is divided by 6. – Ted Sep 30 '12 at 17:09

Note that the form $6n - 1$ is of the same type as $6n + 5$. We have 6 types of integers : $6n , 6n+1 , 6n+2 , 6n+3 , 6n+4 , 6n+5$.

Clearly $6n , 6n+2$ and $6n+4$ are even.

Also clear is that $6n+3$ is divisable by 3.

So we sieve out $6n,6n+2,6n+3,6n+4$.

We are left with $6n+1$ and $6n+5$ and we conclude that all positive integers not divisible by 2 or 3 must thus be of the form $6n+1$ or $6n+5$.

Since primes > 3 are not divisible by 2 or 3 they must thus be of type $6n+1$ or $6n+5$. QED

This is basicly how sieves work , you might be intrested in Sieve of Eratosthenes.

-
THANKS! ~ ${}{}$ – ᴊ ᴀ s ᴏ ɴ Oct 1 '12 at 5:09
@jasoncube : Your welcome. – mick Oct 2 '12 at 20:23

Hints (Not necessarily related to each other!):

== What are the units in the ring $\,\Bbb Z_6:=\Bbb Z/6\Bbb Z\,$ ?

== What is $\,\phi(6)\,$ , with $\,\phi=\,$ Euler's totient function

== For any prime$\,p>3\,\,,\,\,(6,p)=1\,$

-

It is known. Any number greater or equal to than $6$ that is of the form $6n, 6n+2, 6n+3,$ or $6n+4$ will have a factor of $2$ or $3$, so cannot be prime. And $5=6\cdot 1 -1$

-