Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ?

share|cite|improve this question
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,… – 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
up vote 3 down vote accepted

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.$

share|cite|improve this answer 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 and check for any patterns, for example $\pmod{12}.$ – Will Jagy Dec 6 '11 at 3:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.