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

So I have seen this proof plastered everywhere, and here is a version of it from my textbook. No matter where I read, I don't understand one step of the proof, and I will highlight below. It surely has something to do with the Lemma that states for $$x=y+z$$, if $$a\mid y$$ and $$a \mid z$$, then $$a\mid x$$. Thank you.

Fact: There are infinitely many primes of the form $$4n+3,$$ where $$n$$ is a positive integer.

Proof: Let us assume that there are only a finite number of primes of the form $$4n+3,$$ say $$p_0=3,p_1,p_2,...,p_r$$.
Let $$Q = 4p_1p_2\cdot\cdot\cdot p_r+3.$$ Then, there is at least one prime in the factorization of $$Q$$ of the form $$4n + 3$$. Otherwise, all of these primes would be of the form $$4n + 1$$, and by Lemma 2.6, this would imply that $$Q$$ would also be of this form, which is a contradiction. However, none of the primes $$p_0,p_1,...p_n$$ divides $$Q$$. The prime $$3$$ does not divide $$Q$$, for if $$3|Q$$, then $$3|(Q-3)=4p_1p_2...p_r,$$ (How did they reach this? I don't understand why $$3$$ does not divide $$4p_1p_2...!$$ ) which is a contradiction.

Likewise, none of the primes $$p_j$$ can divide $$Q$$, because $$p_j|Q$$ implies $$p_j|Q-(4p_1p_2...p_r)=3$$ which is absurd. Hence, there are infinitely many primes of the form $$4n + 3$$.

• If 3 divides 4p1p2...pr, then at least one must be divided by 3 but p1,...,pr>3 as defined. Consider tha 4=2 times 2. And 2 2 p1p2...pr are just prime factorization of this number. And this factorization must be unique. So 3 must be in it. Sep 30, 2021 at 0:24
• The construction omits $p_0 = 3$. Sep 30, 2021 at 0:25
• @stephenkk Could it be said that p_1,...p_r can't be divisible by 3 because they are all prime? I'm not sure I quite understand the logicafter 4=2*2. Thanks Sep 30, 2021 at 0:35
• For any number n greater than 1, there are unique sequence of primes p0,...,pr, such that n=p0p1...pr. So if 3 is a prime dividng n, then it must be that one of p0...pr must be 3 since 3 is also a prime. Sep 30, 2021 at 0:38

It's actually a rearrangement ( or alteration) of that lemma : $$x=y+z\implies x-y=z\land x-z=y$$
So we get by factoring out that: $$a\mid x \land a\mid y \implies a\mid z$$ and $$a\mid x \land a\mid z\implies a\mid y$$
This is equivalent to $$a\nmid x \land a\mid y\implies a\nmid z$$ and $$a\nmid x \land a\mid z\implies a\nmid y$$
I prefer saying the primes in the list are $$4n-1,$$ then defining
$$Q = 4p_1p_2\cdot\cdot\cdot p_r-1.$$