Infinitely many primes of the form $4n+3$

Question

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.

Answer 1

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.

Answer 2

Therefore, it is divisible by a prime (How did they get to this conclusion?).

All integers are divisible by some prime!

So every prime which divides N must be of the form 4n+1 (Why must it be of this form?).

Because we've assumed that $p_1, \dots, p_k$ are the only primes of the form 4n+3. If none of those divide N, and 2 doesn't divide N, then all its prime factors must be of the form 4n+1.

"Why does a proof of this flavor fail for primes of the form 4n+1? (This is my last question.)

Can you do this yourself now? (Do you understand how the contradiction works in the proof you have? What happens if you multiply together two numbers of the form 4n+3?)

Answer 3

Question 1: Any integer is divisible by a prime (you actually don't even need the full strength of the unique factorization theorem; this is provable by induction).

Question 2: It's not divisible by any of the primes of the form $4n+3$ (namely, $p_1,\ldots,p_k$, which we're assuming is all of them), and it's not divisible by $2$ because it's odd. Thus, any prime dividing it must be of the form $4n+1$.

Question 3: Multiplying an even number of things of the form $4n+3$ together gives something of the form $4n+1$.

Answer 4

1.How did they get to this conclusion?

Well, it already assumed that prime numbers of $4n+3$ are finite. If you multiply all of them and $+3$ (or $-1$, if you like), by assumption, $N$ is not in the prime set of $4n+3$ form. So according to the finite assumption, $N$ is not a prime number.

---

2.Why must it be of this form $(4n+1)$?

We classify all prime numbers into four sets of the form $4n,4n+1,4n+2,4n+3$. from $1$ we already see that prime number in $4n+3$ can't divide $N$ by our assumption. Prime numbers of $4n$ and $4n+2$ contain only $2$, however, $N=4k+3$, so $N$ is odd which can't be divided by $2$. The only result is that prime numbers of the form $4n+1$ could divide $N$.

---

3.Why does a proof of this flavor fail for primes of the form $4n+1$? (This is my last question.)

$(4a+1)(4b+1) = 4(4ab+a+b)+1$ which is still of the form $4n+1$. And that's why our assumption of $N$ is not a prime number fails. So we see $N$ is a new prime number of the form $4n+3$. Repeat this process, we will get the infinite numbers of elements with the form $4n+3$.