Prove that there are infinitely many primes of the form ## 6k+1 ##?

[Math100]

Homework Statement

By considering the number $4p_{1}^{2}p_{2}^{2}\dotsb p_{n}^{2}+3$, where $p_{1}, p_{2}, ..., p_{n}$ are primes, prove that there are infinitely many primes of the form $6k+1$.

Relevant Equations

None.

Proof:

Suppose that the only prime numbers of the form $6k+1$ are $p_{1}, p_{2}, ..., p_{n}$,
and let $N=4p_{1}^{2}p_{2}^{2}\dotsb p_{n}^{2}+3$.
Since $N$ is odd, $N$ is divisible by some prime $p$,
so $4p_{1}^{2}\dotsb p_{n}^{2}\equiv -3\pmod {p}$.
That is, $(-3|p)=1$.
So $p\equiv 1\pmod {6}$, and hence $p$ is one of the primes $p_{i}$.
But this is impossible, since $p_{i}\nmid N$.
This contradiction establishes the result.

Above is the proof for this problem in my book. But I do not understand why $(-3|p)=1$ for $p\equiv 1\pmod {6}$. Can anyone please explain why?

 

[andrewkirk]

I agree. I can see no way to conclude that $p\equiv 1\mod 6$ from the steps above that.
Since $N=pk$ for some integer $k$ and $N\equiv 1\mod 6$, we must have $p,k$ either both being 1 or both 5, mod 6 (as 5 is -1 mod 6). But I can see no way to rule out the possibility that they are both 5 mod 6. If they are both 5, they can't conclude that $p$ is one of $p_1, ..., p_n$, in fact it becomes certain that $p$ is not one of those!

 

[nuuskur]

It is true that for primes $p\geqslant 5$ we have
$$\left ( \frac{-3}{p} \right ) = \begin{cases} 1 , &p\equiv 1\pmod{6} \\-1,& p\equiv -1 \pmod{6} \end{cases}$$

1. Show that neither $2$ nor $3$ divide $N$.
2. Conclude $N$ has an odd prime divisor which is of the form $6k+1$.
3. Reach a contradiction.

Take a prime $p=6k+1$ and go through the squares of $1,2,\ldots,3k$. You will find something of the form $6k-2$. Then think of why that argument will not work in the case $p=6k-1$.

Alertness check @Math100 . Why are only $p=6k-1$ and $p=6k+1$ considered? I.e, why aren't we considering the other classes?

 

[andrewkirk]

Why are only $p=6k-1$ and $p=6k+1$ considered? I.e, why aren't we considering the other classes?

Because the other mod 6 equivalence classes (0, 2, 3, 4) are all divisors of zero. Divisors of zero have no inverse and hence cannot be a factor of 1 (a "unit").

 

[Math100]

Okay, so I revised this proof:

Suppose for the sake of contradiction that the only primes of the form $6k+1$ are $p_{1}, p_{2}, ..., p_{n}$.
Consider the integer $N=4p_{1}^{2}p_{2}^{2}\dotsb p_{n}^{2}+3=(2p_{1}p_{2}\dotsb p_{n})^{2}+3$.
Since $N$ is odd, it follows that $N$ has an odd prime divisor of the form $6k+1$.
Observe that $2\nmid N$ and $3\nmid N$.
Let $p$ be a prime divisor of $N$.
Then $4p_{1}^{2}\dotsb p_{n}^{2}\equiv -3\pmod {p}$, so $(-3|p)=1$.
This implies that $(-3|p)=(-1|p)(3|p)$.
If $(-1|p)(3|p)=1$, then $p\equiv 1\pmod {12}$.
But note that $(-1|p)=(3|p)=-1$, so $p\equiv 7\pmod {12}$.
Thus $p\equiv 1\pmod {6}$ and $p$ is one of the primes $p_{i}$.
Hence $p\mid N$ and $p\mid 3$, which contradicts the fact that $3\nmid N$.
Therefore, there are infinitely many primes of the form $6k+1$.

 

[andrewkirk]

What do you mean by the following?

$(-3|p)=1$.

I have never seen notation like this and neither, apparently has whoever compiled this list of uses of the vertical bar symbol for wikipedia.
Under standard notation $-3|p$ means that -3 is a factor of $p$. From which it follows that the above says:

"(-3 is a factor of $p$) equals 1"

which I can make no sense of.

 

[nuuskur]

@andrewkirk Confusing indeed, but I am quite confident that it stands for the Legendre symbol, which is used to designate quadratic residues.
$$(a\mid p) := \left ( \frac{a}{p} \right ) = \begin {cases} -1, & \forall x(x^2 \neq a \pmod{p}) \\ 0, &a=0\pmod{p} \\1, &\exists x(x^2=a\pmod{p}) \end{cases}$$

 

[nuuskur]

Okay, so I revised this proof:

Since $N$ is odd, it follows that $N$ has an odd prime divisor of the form $6k+1$.

Why?

Observe that $2\nmid N$ and $3\nmid N$.

It's clear $N$ is not even, sure, but why wouldn't it be a multiple of $3$?

Thus $p\equiv 1\pmod {6}$ and $p$ is one of the primes $p_{i}$.

You said that already at the start.

Hence $p\mid N$ and $p\mid 3$, which contradicts the fact that $3\nmid N$.

Does it follow from $p\mid N$ and $p\mid 3$ that $3\mid N$ ..? How does this contradiction arise, exactly?

The proof attempt is not convincing.

 

[Math100]

Why?

It's clear $N$ is not even, sure, but why wouldn't it be a multiple of $3$?

You said that already at the start.

Does it follow from $p\mid N$ and $p\mid 3$ that $3\mid N$ ..? How does this contradiction arise, exactly?

The proof attempt is not convincing.

Because $3\nmid 2p_{1}p_{2}\dotsb p_{n}$. And $p\mid N, p\mid 3$ implies $p\mid (N-3)$, so $p\mid (2p_{1}p_{2}\dotsb p_{n})$. Also, how should I show that $N$ has an odd prime divisor of the form $6k+1$? At first, I thought this is so because $N$ itself is odd. But it seems like there exists another reason for this. So how should I write this proof in a much more convincing way?

 

[Math100]

What do you mean by the following?

I have never seen notation like this and neither, apparently has whoever compiled this list of uses of the vertical bar symbol for wikipedia.
Under standard notation $-3|p$ means that -3 is a factor of $p$. From which it follows that the above says:

"(-3 is a factor of $p$) equals 1"

which I can make no sense of.

I apologize for the confusion. What I meant is the symbol for expressing Legendre symbol, not divisibility.

 

[nuuskur]

The fundamental theorem of arithmetic implies that $N$ has a prime factor $p$. Furthermore, it holds that $(2p_1\ldots p_n)^2 = -3$ modulo $p$. Thus, by the lemma it must hold that $p$ is of the form $6k+1$ so $p$ is one of the $p_i$. But then it follows that $p\mid 3$, which is impossible.

If we want to use the lemma, we must make sure that this $p\geqslant 5$. Verify that $N=1$ modulo $6$, which shows that $N$ can't be a multiple of $3$.

And $p\mid N, p\mid 3$ implies $p\mid (N-3)$, so $p\mid (2p_{1}p_{2}\dotsb p_{n})$.

It follows that $p\mid (2p_1\ldots p_n)^2$. Since $p$ is prime, the square can be omitted (Euclid's lemma). Where is $p\mid 3$ given, though?

Also, how should I show that $N$ has an odd prime divisor of the form $6k+1$?

That's the whole point of the quadratic residue lemma. We have that $-3$ is a quadratic residue modulo $p$, which can only happen if $p=6k+1$.

At first, I thought this is so because $N$ itself is odd.

Sure, but then you are arguing in circles. You assume that there is a prime factor of the form $6k+1$ and then later you conclude that there is a prime factor of this form. There is no progress in such an argument.

So how should I write this proof in a much more convincing way?

You should make sure your arguments are correct. It means that if you need to prove $P\Rightarrow Q$, then you assume $P$ and show that $Q$ follows. Proving $P\land Q\Rightarrow Q$ is not a valid tactic.

It is also less convincing if your proof attempt is inconsistent in terms of the complexity of the details you omit. You often leave out details that are important to mention in this context.

 

[Math100]

The fundamental theorem of arithmetic implies that $N$ has a prime factor $p$. Furthermore, it holds that $(2p_1\ldots p_n)^2 = -3$ modulo $p$. Thus, by the lemma it must hold that $p$ is of the form $6k+1$ so $p$ is one of the $p_i$. But then it follows that $p\mid 3$, which is impossible.

If we want to use the lemma, we must make sure that this $p\geqslant 5$. Verify that $N=1$ modulo $6$, which shows that $N$ can't be a multiple of $3$.

It follows that $p\mid (2p_1\ldots p_n)^2$. Since $p$ is prime, the square can be omitted (Euclid's lemma). Where is $p\mid 3$ given, though?That's the whole point of the quadratic residue lemma. We have that $-3$ is a quadratic residue modulo $p$, which can only happen if $p=6k+1$.

Sure, but then you are arguing in circles. You assume that there is a prime factor of the form $6k+1$ and then later you conclude that there is a prime factor of this form. There is no progress in such an argument.

You should make sure your arguments are correct. It means that if you need to prove $P\Rightarrow Q$, then you assume $P$ and show that $Q$ follows. Proving $P\land Q\Rightarrow Q$ is not a valid tactic.

It is also less convincing if your proof attempt is inconsistent in terms of the complexity of the details you omit. You often leave out details that are important to mention in this context.

But how should I verify that $N\equiv 1\pmod {6}$? And I think I made some mistakes in my previous proof attempts, because $p\mid N$ and $p\mid (2p_{1}\dotsb p_{n})^{2}$ implies that $p\mid (N-(2p_{1}\dotsb p_{n})^{2})$, so $p\mid 3$.

 

[nuuskur]

But how should I verify that $N\equiv 1\pmod {6}$?

Basic modular arithmetic you should be familiar with by now. The $p_i$ are all equal to $1$ modulo $6$.

$p\mid N$ and $p\mid (2p_{1}\dotsb p_{n})^{2}$ implies that $p\mid (N-(2p_{1}\dotsb p_{n})^{2})$, so $p\mid 3$.

Mhm, and to have $p\mid 4(p_1\ldots p_n)^2$ it must be shown that $p$ is one of the $p_i$-s.