Exercise 3.2.21* (There are infinitely many primes of the form $12n+7$)

Proof.

(a)

Let $p$ be any prime factor of $4x^2+3$, where $3\nmid x$.

Since $4x^2+3$ is odd, $p\ne 2$. Moreover $p\ne 3$, otherwise $3\mid 4x^2+1$ implies $x^2\equiv -1(\mathit{mod}3)$, which is impossible since $-1$ is not a quadratic residue modulo $3$.

The congruence ${(2x)}^2\equiv -3(\mathit{mod}p)$, where $p\ne 2$, shows that $-1$ is a quadratic residue modulo $p$, so $\left(\frac{-3}{p}\right)=1$.

We have proved in Problem 20 (or 13), that $\left(\frac{-3}{p}\right)=\left(\frac{p}{3}\right)$, thus $\left(\frac{p}{3}\right)=1$, so $p\equiv 1(\mathit{mod}3)$. This shows that every prime divisor of $4x^2+3$ satisfies

$$p\equiv 1(\mathit{mod}3).$$

On the other hand, if all prime divisors of $4x^2+3$ are of the form $4k+1$, then $4x^2+3$, which is product of such primes, is itself of the form $4k+1$. In this case, $4x^2+3\equiv 1(\mathit{mod}4)$. This is a contradiction, because $4x^2+3\equiv 3\not\equiv 1(\mathit{mod}4)$. Hence there is some prime divisor $p$ of $4x^2+3$ which satisfies $p\equiv 3(\mathit{mod}4)$. Then

$$\{\begin{array}{c}p\equiv 3(\mathit{mod}4),\hfill \\ p\equiv 1(\mathit{mod}3).\hfill \end{array}$$

Therefore $p\equiv 7(\mathit{mod}12)$.

This shows that if $x$ is not divisible by $3$ then $4x^2+3$ has at least one prime factor of the form $12n+7$.

(b)

Let $S=\{p_1,p_2,\dots ,p_k\}$ a finite (non empty) set of primes of the form $12n+7$.

Consider

$$N={(2p_1{p}_2\cdots p_k)}^2+3.$$

Then $N=4x^2+3$, where $x=p_1{p}_2\cdots p_k$, where $3\nmid x$, since $3$ is not of the form $12n+7$. By part (a), $N$ has at least one prime factor $p$ of the form $12n+7$.

Moreover $p\notin S$, otherwise $p\mid 3$, and so $p=3$, but $3$ is not of the form $12n+7$. Hence the finite set $S$ cannot be the set of all primes of the form $12n+7$. This proves that there are infinitely many primes of the form $12n+7$.