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

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.

-
You were visibly confused by the phrase "and also not prime as... form.", and the following "Therefore". Indeed this phrase is not used at all, and moreover together with the "Therefore" wrongly suggests that something more complicated is going on than there is. Another criticism of the proof: it should have either treated the possibility $k=0$ separately (since this would give $N=-1$), or (more cleverly) use ${}+3$ instead of ${}-1$ in the expression for $N$ (since then $N>1$ holds regardless). – Marc van Leeuwen May 14 '13 at 8:21

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.

-

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?)

-
"All integers are divisible by some prime!" - Yes, but the proof meant divisible by a prime less than the number itself. – atulgangwar Jun 18 '15 at 9:56
@calmyoursenses: Indeed, but if a positive integer $d$ divides positive integer $n$, then necessarily $d \le n$. Perhaps you'd already noticed this? – hardmath Feb 6 at 17:05

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$.

-