Infinitely many primes of the form $6n - 1$ Prove there are infinitely many primes of the form $6n - 1$ with the following: (i) Prove that the product of two numbers of the form $6n + 1$ is also of that form. That is, show that $(6j + 1)(6k + 1) = 6m + 1$, for some choice of $m$. (ii) Show that every prime $p$ greater than $3$ is necessarily of the form $6n + 1$ or $6n − 1$.

(i) $(6m+1)\times(6n+1) = 36mn + 6m + 6n + 1 = 6(6mn + m + n) + 1$
(ii)  To prove all primes are of the form $6n + 1$ or $6n - 1$, consider:


*

*$6x+0 = 6x$

*$6x+2 = 2(3x+1)$

*$6x+3 = 3(2x+1)$

*$6x+4 = 2(3x+2)$

*$6x+5 = 6(x+1) - 1$


(iii) To prove that there are infinitely many primes of the form $6n-1$ consider:
$(6m+1)\times(6n-1) = 36mn - 6m + 6n - 1 = 6(6mn -m +n) - 1$
$(6m-1)\times(6n-1) = 36mn - 6m - 6n + 1 = 6(6mn - m - n) + 1$
So, if we only consider numbers that are a product of primes $p > 3$, their product will always be $6x+1$ or $6x-1$
Assume $y$ is the greatest prime of the form $6x-1$
Let $v = $ product of all primes $p$ where $3 < p \le y$ so that $v$ is of the form $6x-1$ or $6x+1$
if $v$ is of the form $6x-1$, then $v+6$ is of the form $6(x+1)-1$ and is not divisible by any prime $\le y$.  If it is not prime, then it must be divisible by at least one prime of the form $6x-1$.  Otherwise, its form would be $6x+1$
if $v$ is of the form $6x+1$, then $v-2$ is of the form $6x+1-2 = 6x-1$ and is not divisible by any prime $\le y$.  If it is not prime, then it must be divisible by at least one prime of the form $6x-1$ for the same reason as above.
Therefore, it follows that $y$ cannot be the highest prime of this form and we have proven that there are infinitely many.
