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$.
 A: (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.
A: (i) $(6n-1)(6m-1) = \cdots = 6(\cdots) + 1$ (find this by expanding and factoring out a 6).
(ii) Fix $n = 6q+r > 3$ (a result of the division algorithm) where $q\ge0$ and $0 \le r < 6$. Examine the possibilities of $r$. Clearly, $0$, $2$, $3$, and $4$ can be eliminated (why?). What are the other possibilities and what do they imply about $n$?
A: Expand: (6j + 1)(6k + 1) = 36jk + 6j + 6k + 1 = 6(6jk + j + k) + 1
Let m = 6jk + j + k
= 6m + 1
To answer the second part, think about what a prime number means. By definition, no prime p > 3 may have 3 or 2 as a factor.
All integers can be written in the form 6q + a, where a is an integer between 0 and 5.
6n - 1 = 6q + 5  for  q = n + 1 
6q + 0 = 6(q)
6q + 1 = 6q + 1
6q + 2 = 2(3q + 1)
6q + 3 = 3(2q + 1)
6q + 4 = 2(3q + 2)
6q + 5 = 6q + 5    
As you can see, the only possible primes above are 6q + 1 and 6q + 5, as they are the only ones that cannot be expressed as a product of two numbers.
