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:
- 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!
Solution 1:
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}$.
Solution 2:
$\rm\ N\ =\ 4\ M - 1\ \equiv\: -1\ \equiv\ 3\ \ (mod\ 4)\:,\ \ $ (where $\rm\ M \ =\ 3\cdot 5\:\cdots\:p_{\:k}\:$)
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)\:.$