Infinitely many primes of the form 4k + 3

Idea. An integer $\equiv3\pmod4$ cannot be a product of primes all $\equiv1\pmod4$.

Proof. Suppose the primes $\equiv3\pmod4$ are exactly $p_1,\dots,p_r$, and let $N=4p_1\cdots p_r-1$. Then $N\ge11$, $N$ is odd, and $N\equiv3\pmod4$.

• If all prime factors of $N$ were $\equiv1\pmod4$, their product $N$ would be $\equiv1\pmod4$. Contradiction.
• So $N$ has a prime factor $q\equiv3\pmod4$, hence $q=p_i$ for some $i$.

But then $p_i$ divides both $N$ and $4p_1\cdots p_r$, hence divides their difference $1$. Contradiction.

Remark. The same trick fails for primes $\equiv1\pmod4$ (a product of primes $\equiv3$ can be $\equiv1$); a different argument (using $x^2+1$) is needed there. Dirichlet's theorem handles all progressions $a\bmod m$ with $\gcd(a,m)=1$.

Lesson. Euclid's construction works whenever one can arrange the residue of the auxiliary number so that some prime factor must lie in the class under study.