10
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Your $n$ is congruent to $4$ mod $6$. $\endgroup$ Commented Jun 8, 2014 at 15:12
  • $\begingroup$ @TedShifrin, Ah.. You mean if $n \equiv 4 \pmod 6$, then 2 is prime factor of n... Thus this is wrong, right?? $\endgroup$
    – user143993
    Commented Jun 8, 2014 at 15:19
  • $\begingroup$ 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. $\endgroup$ Commented Jun 8, 2014 at 15:24
  • $\begingroup$ @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? $\endgroup$
    – user143993
    Commented Jun 8, 2014 at 15:36

2 Answers 2

9
$\begingroup$

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.

$\endgroup$
11
  • 1
    $\begingroup$ 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:-) $\endgroup$
    – user143993
    Commented Jun 8, 2014 at 15:26
  • $\begingroup$ 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. $\endgroup$ Commented Jun 8, 2014 at 15:28
  • $\begingroup$ THANK you sincerely. :-) AND Just to be sure...I'm sorry if it offended you. $\endgroup$
    – user143993
    Commented Jun 8, 2014 at 15:33
  • $\begingroup$ Not at all ;-), you're welcome. $\endgroup$ Commented Jun 8, 2014 at 15:34
  • 1
    $\begingroup$ Well done! Apologies for not answering your questions immediately, I wasn't at home last evening. $\endgroup$ Commented Jun 9, 2014 at 7:03
3
$\begingroup$

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]

$\endgroup$
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .