$6n+1$ and $6n-1$ prime format I recently stumbled upon a fact that all prime numbers past $3$ are of the form either $6n-1$ or $6n+1$.
Is it true? at least for numbers less than $10^9$.
And does it cover all primes?
 A: All prime numbers past $3$ are of one of those two forms.
Think of it this way:
All integers are of one of this forms:
$$\begin{cases}6n-2 & \Rightarrow&  2·(3n-1) \\ 6n -1 \\6n & \Rightarrow & 2·3·n \\ 6n+1 \\ 6n+2 & \Rightarrow&  2·(3n+1) \\ 6n+3 & \Rightarrow & 3·(2n+1)\end{cases}$$
Note that all other than $6n-1$ and $6n+1$ can be expressed as a product of two integers bigger than $1$. So a prime number cannot be of any form other than $6n\pm 1$.
(That doesn't mean that all numbers of the form $6n\pm 1$ are prime)
A: Hint : By Division Algorithm, any integer can be represented as one of :  $6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5$ and notice below
$2 | 6n+2$
$3 | 6n+3$
$2 | 6n+4$
A: Indeed all primes greater than 3, are in the form of $6n-1$ and $6n+1$. I've studied these a few years ago. Here's a basic visual proof of that using a sieve and isolation method.
First , list down all the numbers in 6 columns :
1-------- 2---------3--------4 ---------5--------6 

7-------- 8-------- 9--------10--------11--------12 

13-------14--------15------- 16--------17------- 18
.....[ the list will be infinite ]  

Then, we cross out the columns of $2, 3, 4$ and $6$ as they are all composite. We are just left out with two columns of 1 and 5.
Using algebraic progression with a difference of 6:

*

*Column 1 generates the prime path of $6n+1$ :  $[ 7, 13, 19, ...]$


*Column 5 generates the prime path of $6n-1$ : $[ 5, 11, 17, 23, ...]$
Thus , by isolation and sieve method, we can see that all primes > 3 must be in the form of $6n+1$ and $6n-1$.
