# Infinitely many primes of the form $6\cdot k+1$ , where $k$ is an odd number?

How to prove that there are infinitely many primes of the form $6k+1$ , where $k$ is an odd number ?

Here is a proof that there are infinitely many primes of the form $6k+1$ :

We will assume that there are a finite number of primes of the form $6k+1$ .

Let $p_1 = 6k_1+1, p_2 = 6k_2+1$, ... Then,

$p_1p_2 = (6k_1+1)(6k_2+1) = 36k_1k_2 + 6k_1 + 6k_2 + 1$

$p_1p_2 = 6\cdot f(k_1,k_2) + 1$, where $f(k_1,k_2) = 6k_1k_2 + k_1 + k_2$

i.e. the product of two numbers of the form $6k+1$ is also a number of the form $6k+1$.

Hence $p_1p_2...p_n$ will be a number of the form $6k+1$

i.e. $p_1\cdot p_2...p_n = 6f(k_1,k-2,...,k-n) + 1$

$(2p_1p_2...p_n)^2 = 4(36f^2 +12f + 1) = 6g + 4$, where $g = 24f^2 + 8f$,

$(2p_1p_2...p_n)^2 + 3 = 6g + 4 + 3$

$(2p_1p_2...p_n)^2 + 3 = 6g + 6 + 1$

$(2p_1p_2...p_n)^2 + 3 = 6g' + 1$

i.e. $N = 6g' + 1$, a number of the form $6k+1$

Now, by construction, $N = (2p_1p_2...p_n)^2 + 3$, and is not divisible by any of the $p_i$.

Hence it is either prime itself, or divisible by another prime greater than $p_n$, contradicting the assumption.

I.e. There are an infinite number of primes of the form $6k+1$

Can I use the method of this proof to prove that there are infinitely many primes of the form $6k+1$ , where $k$ is an odd number or to choose some other proof strategy ?

-
Are you looking for a proof, similar to Euclid's argument, which will work exclusively for this case? Else, in case you are not aware, en.wikipedia.org/wiki/… –  user17762 Dec 5 '11 at 8:17
I don't think your proof works. If $N$ is not prime, how do you know that its prime divisors aren't all of the form $6k+5$? –  TonyK Dec 5 '11 at 8:20
@SivaramAmbikasaran,I think that I cannot conclude that there are infinitely many primes of the form $6k+1$ , where $k$ is an odd number if I have proved that there are infinitely many primes of the form $6k+1$... –  pedja Dec 5 '11 at 8:29
@TonyK There is a big step missing at the end of the proof. The number N constructed is a number of the form x^2+3y^2 with (x,y)=1, and all the prime divisors of any such number are of the form 6n+1. –  Ted Dec 5 '11 at 8:34
@pedja: Proving infinitely many primes of the form $6k+1$ where $k$ is odd is equivalent to proving infinitely many primes of the form $6(2m+1)+1 = 12m+7$. –  user17762 Dec 5 '11 at 8:39

edit, Monday, December 5: Pedja's argument can me made to work with the addition of a quadratic reciprocity step...

original: Pedja, you use Dirichlet on the arithmetic progression $12 n + 7,$ which is what you are describing by saying $6k+1$ with $k$ odd. Write $k = 2n+1,$ then $6k+1 = 6 (2n+1) + 1 = 12n + 6 + 1 = 12 n + 7.$

Meanwhile, if you are willing to accept the Cebotarev Density Theorem, asymptotically the two positive quadratic forms $x^2 + 12 y^2$ and $3 x^2 + 4 y^2$ represent the same proportion of primes. The first form represents primes $p \equiv 1 \pmod {12},$ while the second form represents 3 and the primes $q \equiv 7 \pmod {12}.$ I am quoting Theorem 9.12 on page 188 of Primes of the Form $x^2 + n y^2$ by David A. Cox.

EDIT: Actually, your attempt is almost correct, there is an elementary proof of this one. As you write above, take the collection of primes $q_j \equiv 7 \pmod{12}$ that is assumed to be complete, up to some largest we will call $q_r.$ Then, just as you wrote, define $$w = 3 + 4 \left( q_1 q_2 \ldots q_r \right)^2$$ We know that $w \equiv 7 \pmod {12}.$ We also know that $w$ is primitively represented by the quadratic form $3 x^2 + 4 y^2.$ That means that $\gcd(x,y)=1,$ where here $x=1,$ and we are writing $w = 3 x^2 + 4 y^2.$

Now, $w$ is not divisible by 2 or 3. The fact that $\gcd(x,y)=1$ means precisely that $w$ is not divisible by any prime $s \equiv 2 \pmod 3.$ This fact comes under the general heading of quadratic reciprocity. All prime factors of $w$ are, in fact , $1 \pmod 3.$ That is, all prime factors of $w$ are either $1 \pmod {12}$ or $7 \pmod {12}.$ If all prime factors of $w$ were $1 \pmod {12},$ then $w$ itself would also be $1 \pmod {12},$ which it is not.

So, in fact, either $w$ is prime, or $w$ has at least one prime factor, call it $q_{r+1},$ such that $q_{r+1} \equiv 7 \pmod {12}.$ By construction, for any $j \leq r,$ we have $\gcd(q_j,q_{r+1} ) = 1.$ That is, either $w$ itself or $q_{r+1}$ is not in the assumed finite list of primes $7 \pmod {12},$ contradicting the assumption that there is a finite list. $\bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc$

EDIT TOO: Maybe not everyone will know this, so I will give the short proof. Suppose we have some prime $s \equiv 2 \pmod 3,$ with $s \neq 2,$ that divides some $z = 3 u^2 + 4 v^2.$ Then suppose that $s | z,$ which is also written $z \equiv 0 \pmod s.$ I claim that, in fact, both $s | u$ and $s | v,$ with the result that $\gcd(u,v)$ is larger than one. PROOF: We have $3 u^2 + 4 v^2 \equiv 0 \pmod s.$ Assume that $v \neq 0 \pmod s.$ Then $v$ has a multiplicative inverse $\pmod s.$ So we get $$3 u^2 + 4 v^2 \equiv 0 \pmod s,$$ $$3 u^2 \equiv - 4 v^2 \pmod s,$$ $$\frac{3 u^2}{v^2} \equiv - 4 \pmod s,$$ $$\frac{ u^2}{v^2} \equiv \frac{- 4}{3} \pmod s,$$ $$\left(\frac{ u}{v}\right)^2 \equiv \frac{- 4}{3} \pmod s.$$ This says that the right hand side is a quadratic residue $\pmod s.$ It also means that $-12$ is a quadratic residue $\pmod s.$ This is false, though, as we have Legendre symbol $$( -12 | s) = ( -3 | s) = ( -1 | s ) \cdot ( 3 | s).$$ Now, if $s \equiv 1 \pmod 4,$ we can ignore the $-1$ and switch the other pair. If $s \equiv 3 \pmod 4,$ then $( -1 | s ) = -1$ and $(3 | s) = - (s | 3)$. In either case, we get $$(-3 | s) = (s | 3).$$ As $s \equiv 2 \pmod 3,$ we have $$( s | 3) = ( 2 | 3) = -1.$$ So, in the end we have $$( -12 | s) = -1,$$ and this contradicts the assumption that $v$ is nonzero $\pmod s.$ Thus, $v \equiv 0 \pmod s.$ From $3 u^2 + 4 v^2 \equiv 0 \pmod s,$ we then have $u \equiv 0 \pmod s.$ So $s | \gcd(u,v)$ and $\gcd(u,v) \neq 1.$

-
thanks..it is so elementary proof... –  pedja Dec 5 '11 at 8:46
@pedja: No, it relies on Dirichlet's theorem, which is far from elementary! –  TonyK Dec 5 '11 at 8:55
@WillJagy,I think that this fact is necessary condition that there are infinitely many Mersenne primes . Am I correct ? –  pedja Dec 5 '11 at 9:03
Pedja, I am not reading anything that makes any demands about $p$ when $2^p -1$ is also prime. You might look at the tables of the $p$ at primes.utm.edu/mersenne and check for any patterns, for example $\pmod{12}.$ –  Will Jagy Dec 6 '11 at 3:12