Exercise 3.2.13* ( There are infinitely many primes of each of the forms $3n+1$ and $3n-1$)

Proof.

(a)

Let $S=\{p_1,p_2,\dots p_k\}$ a finite (non empty) set of prime numbers of the form $3n-1$.

Consider the integer

$$N=3\left(\underset{i=1}{\overset{k}{\prod }}{p}_i\right)-1.$$

Then $N>1$. If all prime divisors of $N$ are of the form $3n+1$, then $N\equiv 1(\mathit{mod}3)$. But $N\equiv -1(\mathit{mod}3)$. Therefore there is some prime $p$ of the form $3n-1$ such that $p\mid N$.

Moreover $p\notin S$, otherwise $p\mid 1$. Therefore $S$ cannot be the set of all primes $p$ of the form $3n-1$. This shows that there are infinitely many primes of the form $3n-1$.

(b)

For any odd prime $p$, using the law of quadratic reciprocity, $$\begin{array}{llll}\hfill \left(\frac{-3}{p}\right)& =\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)& \hfill & \\ \hfill & ={(-1)}^{\frac{p-1}{2}}{(-1)}^{\frac{3-1}{2}\frac{p-1}{2}}\left(\frac{p}{3}\right)& \hfill & \\ \hfill & =\left(\frac{p}{3}\right).& \hfill & \end{array}$$

Therefore

$$\left(\frac{-3}{p}\right)=1⟺p\equiv 1(\mathit{mod}3).$$

Let $T=\{p_1,p_2,\dots p_k\}$ a finite (non empty) set of prime numbers of the form $3n+1$, and consider the integer

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

Then $N>1$. Let $p$ be any prime divisor of $N$. The congruence $x^2\equiv -3(\mathit{mod}p)$ has a solution $x=p_1{p}_2\cdots p_k$. Therefore $\left(\frac{-3}{p}\right)=1$. Hence $p\equiv 1(\mathit{mod}3)$.

If $p\in T$, then $p\mid 3$, thus $p=3$. But $N\equiv 1(\mathit{mod}3)$, so $p\ne 3$. This contradiction shows that $p\notin T$. Therefore $T$ cannot be the set of all primes $p$ of the form $3n+1$. This shows that there are infinitely many primes of the form $3n+1$.