# Proof that there are infinitely many primes of the form $4m+3$ [duplicate]

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:

1. Why is $N_k$ congruent to $3 \pmod{4}$?
2. 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!

## marked as duplicate by Jyrki Lahtonen, max_zorn, dantopa, Adrian Keister, JaviMar 29 at 22:45

• To be a valid proof of the requested theorem, the first line should be "Assume there are finitely many primes of the form $4m+3$, and take $p_k$ to be the largest." – Mark Hurd Jun 21 '14 at 6:19
• At the end, why is this primefactor in the form $4m+3$ bigger than $p_k$? – iJup Sep 8 '14 at 18:09
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}$.
1. $\rm\ N\ =\ 4\ M - 1\ \equiv\: -1\ \equiv\ 3\ \ (mod\ 4)\:,\ \$ (where $\rm\ M \ =\ 3\cdot 5\:\cdots\:p_{\:k}\:$)
2. Every prime factor of an odd natural is odd, hence $\rm\equiv \pm 1\ (mod\ 4)\:.\:$ But if every factor is $\rm\equiv 1$ then the number is $\rm\: \equiv\ 1^j\ \equiv\ 1\ \ (mod\ 4)\:.$