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

• Math100
In summary: I agree. I can see no way to conclude that ##p\equiv 1\mod 6## from the steps above that.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!

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

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?

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!

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##.
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?

Last edited:
Math100
nuuskur said:
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").

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

What do you mean by the following?
Math100 said:
## (-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.

@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}$$

Last edited:
Math100 and andrewkirk
Math100 said:
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?
Math100 said:
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##?
Math100 said:
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.

Last edited:
Math100
nuuskur said:
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?

andrewkirk said:
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.

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##.
Math100 said:
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?

Math100 said:
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##.
Math100 said:
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.
Math100 said:
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.

Last edited:
Math100
nuuskur said:
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 ##.

Math100 said:
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.

Last edited: