<s>[INST] Proof that there are infinitely many primes of the form $4m+3$ I am reading a proof of there are infinitely many primes of the form $4m+3$, but have trouble understanding it. The proof goes like this:  
Assume there are finitely many primes, and take $p_k$ to be the largest prime of the form $4m+3$.
Let $N_k = 2^2 \cdot 3 \cdot 5 \cdots p_k - 1$, where $p_1=2, p_2=3, p_3=5, \dots$ denotes the sequence of all primes.
We find that $N_k$ is congruent to $ 3 \pmod {4}$, so it must have a prime factor of the form $4m+3$, and this prime factor is larger than $p_k$ — contradiction.
My questions are:


*

*Why is $N_k$ congruent to $3 \pmod{4}$?

*Why must $N_k$ have a prime factor of the form $4m+3$ if it's congruent to $3 \pmod{4}$?


It seems that those should be obvious, but I don't see it. Any help would be appreciated!
 [/INST] For the first question, if $N_k=2^2\cdot 3\cdot 5\cdots p_k-1$, then
$$
N_k-3=2^2\cdot 3\cdot 5\cdots p_k-1-3=4(3\cdot 5\cdots p_k-1)
$$
which implies $4|N_k-3$, that is, $N_k\equiv 3\pmod{4}$.
For the second question, suppose instead that $N_k$ has no prime factors of form $4m+3$. Then all its prime factors must be of the form $4m+1$, as they can not be of the form $4m$ or $4m+2$, (except possibly for $2$). But notice $$(4m+1)(4k+1)=16mk+4m+4k+1=4(4mk+m+k)+1$$ so by an inductive argument, you see that a product of primes of the form $4m+1$ again has the form $4m+1$. In terms of congruences, if $p_i\equiv 1\pmod{4}$ and $p_j\equiv 1\pmod{4}$, then $p_ip_j\equiv 1^2\equiv 1\pmod{4}$. This would contradict the fact that $N_k$ has form $4m+3$, since $N_k\equiv 3\pmod{4}$.
</s>