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

  • $\begingroup$ 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. $\endgroup$
    – stephenkk
    Sep 30, 2021 at 0:24
  • $\begingroup$ The construction omits $p_0 = 3$. $\endgroup$ Sep 30, 2021 at 0:25
  • $\begingroup$ @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 $\endgroup$
    – BoostMatch
    Sep 30, 2021 at 0:35
  • $\begingroup$ 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. $\endgroup$
    – stephenkk
    Sep 30, 2021 at 0:38

2 Answers 2


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.