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 ?
Best Answer
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.$