[Math] Infinitely many primes of the form $4n+3$

arithmetic-progressionselementary-number-theoryprime numbers

I've found at least 3 other posts$^*$ regarding this theorem, but the posts don't address the issues that I have.

Below is a proof that for infinitely many primes of the form $4n+3$, there's a few questions I have in the proof which I'll mark accordingly.

Proof: Suppose there were only finitely many primes $p_1,\dots, p_k$, which are of the form $4n+3$. Let $N = 4p_1\cdots p_k – 1$. This number is of the form $4n+3$ and is also not prime as it is larger than all the possible primes of the same form. Therefore, it is divisible by a prime $ \color{green}{ \text{(How did they get to this conclusion?)}}$. However, none of the $p_1,\dots, p_k$ divide $N$. So every prime which divides $N$ must be of the form $4n+1$ $ \color{green}{ \text{(Why must it be of this form?)}}$. But notice any two numbers of the form $4n+1$ form a product of the same form, which contradicts the definition of $N$. Contradiction. $\square$

Then as a follow-up question, the text asks "Why does a proof of this flavor fail for primes of the form $4n+1$? $ \color{green}{ \text{(This is my last question.)}}$


$^*$One involves congruences, which I haven't learned yet. The other is a solution-verification type question. The last one makes use of a lemma that is actually one of my questions, but wasn't a question in that post.

Best Answer

Every number $n>1$ is divisible by some prime $p$ (which includes the case $n=p$). Assume otherwise and let $n$ be the smallest such number. As this $n$ is not prime, it has a nontrivivial divisor $d$ with $1<d<n$. By minimality of $n$, $d$ is divisible by some prime $p$. But then $p$ also divides $n$.

All numbers are of the form $4n$, $4n+1$, $4n+2$, or $4n+3$. This is also true for primes $p$, but $p=4n$ is not possible and $p=2n$ only for $p=2$. Here, we have excluded $p=2$ as well as $p=4n+3$ by construction, which leaves only primes $p=4n+1$.

This proof fails for $p=4n+1$ because a number of the form $4n+1$ may well be the product of two numbers of the form $4n-1$. For example $3\cdot 7=21$. Therefore the step that at least one divisor must be of form $4n+1$ fails.