# infinitude of primes that are $11 \bmod 12$

Suppose there are finitely many primes $\{p_1, \ldots, p_k\}$ which are $11 \pmod {12}$ and consider $p = (p_1 \cdots p_k)^2 + 10$. Then $p_i \nmid p$ for any $i \leq k$, and $p \equiv 1 + 10 \equiv 11 \bmod 12$. Then $p$ is either a prime itself, contradiction, or $p$ has all prime divisors of the form $12n + 1, 12n + 5, 12n + 7, 12n + 11$. Not all prime factor are of the forms $12n + 1, 5, 7$ because then $p \equiv 1, 5, 7 \mod 12$. So it must have a prime factor $12n + 11$, but $p_i \nmid p$ and so we have a contradiction.

Is this proof valid?

• $5\times 7\equiv -1\pmod {12}$ – lulu Apr 1 '18 at 13:11
• Here is a very nice proof, which you can compare with: Theorem $3.12$ here. I think, taking $N=3(p_1p_2···p_k)^2 −4$ is better. Your proof is not correct. – Dietrich Burde Apr 1 '18 at 13:13
• $5 \times 7 \equiv 11(mod 12)$ – mandella Apr 1 '18 at 13:13
• $11$ is the same as $-1 \pmod {12}$. My point was that your argument is incorrect. For instance, $11,47,107$ are all $11\pmod {12}$ but $(11\times 47\times 107)^2+10$ has no prime factor which is $11\pmod {12}$. – lulu Apr 1 '18 at 13:15
• $-1(mod12)=11(mod(12)$ – Rudi_Birnbaum Apr 1 '18 at 13:15

Suppose there are finitely many primes $\{p_1, \ldots, p_k\}$ which are $11 \pmod {12}$ and consider $p = (p_1 \cdots p_k)^2 + 10$.

So far so good. No, wait, $-1 \equiv 11 \pmod {12}$, but then squaring and adding $10$... okay, you're good at this point. Love the wonderfully confusing use of $p$ without subscript where duller minds would go with a capital letter like $P$ or $N$. Mwahahahahahahahaha!

Then $p_i \nmid p$ for any $i \leq k$, and $p \equiv 1 + 10 \equiv 11 \bmod 12$. Then $p$ is either a prime itself, contradiction, or $p$ has all prime divisors of the form $12n + 1, 12n + 5, 12n + 7, 12n + 11$. Not all prime factor are of the forms $12n + 1, 5, 7$ because then $p \equiv 1, 5, 7 \mod 12$.

I think this is where the problem arises. $5 \times 7 = 3 \times 12 - 1$. Of course $25$ can't arise from a finite sequence of primes of the form $12k - 1$.

Or let's say $47$ is the only prime of the prescribed form. Then $47^2 + 10 = 2219 = 7 \times 317$, and $317 \equiv 5 \pmod {12}$, so this is precisely a $5 \times 7$ situation.

Unless you explicitly say $k > 1$, the proof has to work for $k = 1$, and this one doesn't. Go back to the drawing board.

I see what you are trying to do. Here is the bad news. Generalizing a similar proof of that of Euclid's for the infinitude of primes isn't going to work. If you have a number $n=11\pmod {12}$, the first thing to realize is there exists a prime $p | n$ that is either congruent to $5$, $7$, or $11 \pmod {12}$. If there is no prime $p = 11 \pmod {12}$ dividing $n$, then there are two primes $q$ and $q_2$ such that $q = 5 \pmod {12}$ and $q_2 = 7 \pmod {12}$. The good news is that we can restrict integers $n$ of certain forms to only have prime factors congruent to $1$ or $11 \pmod {12}$ (excluding $2$ or $3$). Let $p$ be a prime and consider weather $x^2 = 3 \pmod p$ is solvable or not solvable. By the law of quadratic reciprocity, $p = 1$ or $11 \mod {12}$. Therefore, each prime $p$ dividing $x^2-3$ is either $1$ or $11 \pmod {12}$. If $x = 12k$ is a multiple of $12$, then $(12k)^2-3$ = $144k^2-3$ which is divsible by $3$. Removing this factor of $3$, we have $48k^2-1$, which is congruent to $11 \pmod {12}$. By the previous conditions, all primes $p$ dividing $48k^2-1$ are congruent to $1$ or $11 \pmod {12}$. It is simple to show that not all primes dividing $48k^2-1$ are of the form $1 \pmod 12$ because if this were true it would imply the $48k^2-1$ is cognruent to $1 \pmod {12}$, and $48k^2$ is congruent to $2 \pmod 12$, but $48$ is a multiple of $12$, and so $48k^2$, a contradiction, therefore there is at least one prime $p$ dividing $48k^2-1$ congruent to $11 \pmod {12}$, which is relatively prime to $k$ obviously. At this point you'd see how this is similar to Euclid's Proof of infinitely many primes.

$p\equiv 11\pmod {12}\iff p=11+12n$. The statement is then an application of Dirichlet's theorem on arithmetic progressions. However you are asking here about your proof.

Well, look at the four first primes equal to $11$ modulo $12$ i.e. $11,23,47$ and $59$. Do you have

$$p=11^2\cdot23^2\cdot47^2\cdot59^2+10=492199062971=7\cdot11^3\cdot127\cdot415969$$ And you have these four prime factors are of the form $12n+7,12n+11,12n+5$ and $12n+1$ respectively.

Following your reasoning, in fact $492199062971\equiv{11}\pmod{12}$ however, no fifth prime of the required form appears in your expression for $p$.

I fear your nice attempt is not correct.