Proof that there are infinitely many primes congruent to 3 modulo 4

Solution 1:

If there are only finitely many primes $\equiv 3 \pmod 4$, take the product of them and denote that product by $a$. Now look at $2a + 1$, and try to deduce a contradiction.

Solution 2:

Lemma. If $a\equiv 3 \pmod 4$ then there exists a prime $p$ such that $p\mid a$ and $p\equiv 3 \pmod 4$.

Proof. Clearly, all primes dividing $a$ are odd. Suppose all of them would be $\equiv 1 \pmod 4$. Then their product would also be $a\equiv 1\pmod4$, which is a contradiction. $\hspace{3cm}\square$

There exist infinitely many primes $p$ such that $p\equiv 3\pmod 4$.

Suppose that $p_1,\dots,p_n$ would be all such primes. (In particular, we have $p_1=3$.) Consider $a=4p_2\cdots p_n+3$. (Or you can take $a=4p_2\cdots p_n-1$.) Show that $p_i\nmid a$ for $i=1,\dots,n$. (The case $3\nmid a$ is solved differently than the other primes - this is the reason for omitting $p_1$ in the definition of $a$.) Then use the above lemma to get a contradiction.

Solution 3:

Use Euclid's proof showing that there are infinitely many primes, i.e., find an Euclidean polynomial you can use for your arithmetic progression $l \mod k$. Since $l^2\equiv 1 \mod k$ such an Euclidean polynomial exists - see http://www.mast.queensu.ca/~murty/murty-thain2.pdf how to do it (in particular, on page one, the case $4n+3$ is given, see [5]). For $8n+1$ see Infinitely many primes of the form $8n+1$.