# Proof that there are infinitely many primes of the form $6k+1$. Proof verification

Theorem. there are infinitely many primes of the form $6k+1$.

I've just proved that there are infinitely many primes of the form $6k+1$.

Could you please check my proof?

At first, I proved that

$$for \ \ p:prime, \ p \ge 5 \\\ \\ \left(\frac{-3}{p}\right)= \begin{cases} 1,& \ p \equiv 1 \pmod 6 \\ -1, & \ p \equiv 5 \pmod 6 \end{cases}$$ (I will use this lemma for proving Theorem.)

 NOW assume that there are finite primes of the form $6k+1$.

then we can say $\ p_1, \ p_2, \cdots, p_k \$ : all the primes of the form $6k+1$.

Let

$$n=(p_1\cdot p_2\cdots\ p_k)^2 +3,$$

then (by Fundamental Theorem of Arithmetic) there is prime factor $p$ of $n$.

 Id est, $$(p_1\cdot p_2\cdots\ p_k)^2 \equiv -3 \pmod p$$

So, $$p \equiv 1 \pmod 6$$

Thus $$p=p_i \ for \ some \ i=1, \cdots , k$$

This time

$$p=p_i \ \ \ divides \ \ (p_1\cdot p_2\cdots\ p_k)^2 \\ p=p_i \ \ \ can't \ \ divide \ \ 3 \\$$

So, $$p=p_i \ \ can't \ \ divide \ \ n. \\$$

It is contradiction with "$p$ is prime factor of $n$"

$\therefore \$ There are infinitely many primes of the form $6k+1$.

$Q.E.D.$

 What about my proof?

After proving, I saw someone's proof,

BUT he set $$n=(2p_1\cdot p_2\cdots\ p_k)^2 +3$$

I don't know why he set $n=(2p_1\cdot p_2\cdots\ p_k)^2 +3$, instead of $n=(p_1\cdot p_2\cdots\ p_k)^2 +3$.

Is my proof wrong?

 Please give me some hand. Thanks in advance.

• Your $n$ is congruent to $4$ mod $6$. – Ted Shifrin Jun 8 '14 at 15:12
• @TedShifrin, Ah.. You mean if $n \equiv 4 \pmod 6$, then 2 is prime factor of n... Thus this is wrong, right?? – user143993 Jun 8 '14 at 15:19
• I wouldn't say wrong, but incomplete. Note that you can also solve the issue by noting that $x^2\equiv1\pmod8$ for odd $x$, which means your $n$ cannot be a power of $2$, hence has an odd prime divisor. – punctured dusk Jun 8 '14 at 15:24
• @barto, Ummm $x^2\equiv1\pmod8$ iff $x \equiv1, 3, 5, 7\pmod8$ iff $x \equiv1 \pmod2$.. How does it go "It means your n cannot be a power of 2" Could you explain more , please? – user143993 Jun 8 '14 at 15:36

There is a minor issue. Not every prime divisor of your $n$ is necessarily of the form $6k+1$. (Because, as you noted, the theorem with the Légendre-symbol is only valid for $p\geqslant5$.) You would have to argue that $2$ and $3$ do not divide $n$.
This can be fixed by letting $n=(2p_1,\cdots,p_k)^2+3$ as you noted, or alternatively by observing that $x^2\equiv1\pmod8$ for odd $x$, which means your $n$ cannot be a power of $2$, hence has an odd prime divisor.

• THANKS a lot for answering. I agree "argue that 2 do not divide n", BUT why I argue that '3 do not divide n'? $n=(p_1\cdot p_2\cdots\ p_k)^2 +3$ is the form 6k+1+3=6k+4 .. isn't it? Do I get wrong thing? Give me some advice, please:-) – user143993 Jun 8 '14 at 15:26
• It is indeed obvious that $3$ does not divide $n$, but it's worth noting because it's still a crucial step in your proof. – punctured dusk Jun 8 '14 at 15:28
• THANK you sincerely. :-) AND Just to be sure...I'm sorry if it offended you. – user143993 Jun 8 '14 at 15:33
• Not at all ;-), you're welcome. – punctured dusk Jun 8 '14 at 15:34
• Well done! Apologies for not answering your questions immediately, I wasn't at home last evening. – punctured dusk Jun 9 '14 at 7:03

If we cross out from sequence of positive integers all numbers divisible by $$2$$ and all numbers divisible by $$3$$, then all remaining numbers will be in one of two forms:

$$S1(n)=6n−1=5,11,17,...$$ or $$S2(n)=6n+1=7,13,19,....n=1,2,3,...$$ So all prime numbers also will be in one of these two forms and ratio 0f number of primes in the sequence $$S1(n)$$ to number of primes in the sequence $$S2(n)$$ tends to be $$1$$. see [link]