# Help understand the proof of infinitely many primes of the form $4n+3$

This is the proof from the book:

Theorem. There are infinitely many primes of the form $4n+3$.

Lemma. If $a$ and $b$ are integers, both of the form $4n + 1$, then the product $ab$ is also in this form.

Proof of Theorem: Let assume that there are only a finite number of primes of the form $4n + 3$, say $$p_0, p_1, p_2, \ldots, p_r.$$
Let $$Q = 4p_1p_2p_3\cdots 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 the Lemma above, this would imply that $Q$ would also be of this form, which is a contradiction. However, none of the prime $p_0, p_1,\ldots, p_n$ divides $Q$. The prime $3$ does not divide $Q$, for if $3|Q$ then $$3|(Q-3) = 4p_1p_2p_3\cdots p_r,$$ which is a contradiction. Likewise, none of the primes $p_j$ can divides $Q$, because $p_j | Q$ implies $p_j | ( Q - 4p_1p_2\cdots p_r ) = 3$, which is absurd. Hence, there are infinitely many primes of the form $4n +3$. END

From "however, none of the prime ...." to the end, I totally lost!

My questions:

• Is the author assuming $Q$ is prime or is not?
• Why none of the primes $p_0, p_1,\ldots, p_r$ divide $Q$? Based on what argument?

Can anyone share me a better proof?

Thanks.

• "this would imply that $Q$ would also be of this form, which is a contradiction." I don't understand why $Q$ being of this form turns into a contradiction. Dec 2, 2015 at 22:44
• Is this due to the division theorem? Dec 2, 2015 at 22:55
• A defect in this proof occurs with $p_0=3$ which would divide the proposed algebraic expression. Use $2\Pi+1$ instead where $\Pi$ is the product of the supposed set of $4n+3$ primes. Aug 2, 2020 at 18:14

This is an adaption of Euclid's classical proof of the infinitude of prime. Suppose that $p_1,...,p_t$ are all the primes and consider the number $N=p_1\cdots p_t+1$. The number $N$ must be divisible by some prime (possibly itself, but this is irrelevant for the argument) but since noone of the $p_i$ divides $N$, this gives a contradiction.

The proof you report is similar in concept but is adapted to show that this "extra prime" obtained by looking at divisors of a suitably constructed auxiliary number (the $Q$ in the proof) is actually of the form $4k+3$.

I believe that a slight correction in the proof is in order: namely, take $p_0=3$. The important technical point is that you DON'T include $p_0=3$ in the product defining $Q$. Thus, you can show that none of the $p_i$ (INCLUDING $p_0$) divides $Q$ and you're done by the Lemma.

• very good observation. That was my typo. $$p_0 = 3$$ was actually true. Thank you. Feb 10, 2011 at 15:52
• Please help me by stating the logical reason behind not having any effect on the representation of $Q$ by ignoring $p_0$. Also, in general can we ignore any term(s) while having the same meaning for $Q$. I mean that do we need consecutive values $p_i p_{i+1} p_{i+2} \cdots p_{n-k}$ for $0\le k\lt i\lt n$ & $i,k,n \in \mathbb {Z+}$; or any number of intervening terms can be ignored, as in $p_2p_3p_6p_9\cdots p_{n-3}p_{n}$. Jan 27, 2018 at 16:15
• @jiten: if you include $p_0=3$ in the product, the number $Q$ is certainly divisible by $3$. Thus, when you argue that a prime $q$ of the form $4n+3$ divides $Q$ you cannot exclude that actually $q=3$ and therefore you cannot conclude that $q$ is a new prime not already listed. Jan 28, 2018 at 1:30
• Do we see representation by the view of need then, and the feasibility of a representation is just a way to to state an axiom. I mean for $4k+3$ basic fact is under modulo $4$, the only alternate odd prime is $4k+1$ which can't be constructed by a number of the form $4k+3$, and vice-versa. Further explaining why called it an axiom, take odd primes of form $8k+7$, here $p_1=3,p_2=5,p_3=7 \cdots$, but multiplication of $8k+3,8k+5$(can include $8k+1$ also) classes leads to $8k+7$ class. So, in this case, 'elementary' proof for $4k+3$ wouldn't work. Hence, new $Q$ representation doesn't matter. Jan 28, 2018 at 9:32
• I mean that if the elementary proof for $4k+3$ works, then need to remove from the left end, else if need to remove from middle (like for $8k+7$ the $p_3$ term), then anew type of proof is needed. So, it is an axiom that $4k+3$ has infinite number of primes, and the representation is just a way to state that. In effect, the feasibility of elementary proof is the key, and based on that have left edge removal case only. Jan 28, 2018 at 10:14

That part of the proof is simply a variant of Euclid's classical method for producing a new prime. Instead of $$\, 1+ \color{#c00}p_{\phantom 1}\!\!\, p_1\cdots p_n$$ it uses $$\, \color{#c00}p+ p_0\cdots p_n,\,$$ where $$\, (p,\ p_k) = 1\$$ (above $$\: p=3,\ p_0 = 4$$), i.e. it moves the first $$\,\color{#c00}p\,$$ from one summand into the other. It is easy to verify that this newly constructed integer is coprime to all the prior $$\: p$$'s (so it has a "new" prime factor), viz.

\begin{align} (p,\ \ \: p+p_0\cdots p_n)& = (p,\ p_0\cdots p_n) = 1\ \ {\rm via} \ \ (p,\ p_k) = 1\\[.2em] (p_k,\ p+ p_0\cdots p_n)& = (p_k,\ p)\ =\ 1 \end{align}\quad

Essentially this proof relies on the fact that $$\ (pq,\ p+q) = 1\! \iff\! (p,\ q) = 1.\$$ Hence to produce a number coprime to $$\ n\$$ we can simply sum the factors $$\ p,q\$$ from any coprime splitting $$\ n = pq.\$$ Euclid's classic proof uses the trivial splitting where $$\ q = 1\$$ (and $$\:p\:$$ is a product of given primes). Ribenboim credits this splitting-form generalization of Euclid's proof to Stieltjes (1890). A slight generalization yields a "coprime" version of Dirichlet's result on primes in arithmetic progression, namely $$\,(a,b,c)=1\,\Rightarrow\,(an+b,c) = 1\$$ for some $$\,n.$$

For a handful of proofs of said gcd property follow "the fact" link above.

I have seen many proofs of this here, but I think a $$basic$$ proof is still lacking. I attempt one below:

(1) First note that $$any$$ integer may be written in the form $$4k, 4k+1, 4k+2$$, and $$4k+3$$. This is the result of the $$Division$$ $$Algorithm$$.

(2) $$Any$$ number is either a prime or a product of primes - Fundamental Theorem of Arithmetic (FTA)

(3) Also note this $$lemma$$: a product of two or more integers of the form $$4n+1$$ is also of the same form. To show this is simple:

Take two numbers of form $$4n+1$$, say $${N}_1=4m+1$$ and $${N}_2=4m'+1$$. Straight multiplication gives $$16mm'+4(m+m')+1$$ = $$4[4mm'+(m+m')]+1$$ = $$4k+1$$, where $$k=4mm'+(m+m')$$, i.e the product is the same $$form$$ as its multiplicands.

Now we have all we need. As already mentioned in many answers here, we use a modified Euclidian proof of the infinitude of primes, which is a proof by contradiction (It is a good idea to familiarize oneself with the said Euclidian proof before proceeding)

In anticipation of a contradiction, we assume there are only a finite number of primes of the form $$4k+3$$. We list them as follows $${q}_1,{q}_2,...,{q}_s$$. Similar to Euclidian Proof, we form a positive integer $$N=4{q}_1{q}_2....{q}_s-1$$.

Note the following about $$N$$:

(1) It is odd (because $$odd*even$$=$$even$$ and $$even-1$$ = $$odd$$)

(2) $$N$$ may be written as $$N=4({q}_1{q}_2....{q}_s-1)+3$$, i.e. $$N$$ is of the form $$4k+3$$

(3) Per FTA, we may write $$N$$ as a product of primes, say $$N={r}_1{r}_2...{r}_t$$. But remember all these primes must be odd (i.e. $${r}_i=2$$ is excluded).

(4) And the only form that $$every$$ $${r}_i$$ may take is either $$4k+1$$ or $$4k+3$$.

(5) This is a $$crucial$$ point: $$N$$ $$cannot$$ contain only primes of the form $$4k+1$$. If this were the case, by the lemma above, $$N$$ would be of the form $$4n+1$$, which is clearly not the case - $$N$$ is of the form $$4n+3$$. Therefore, we conclude that $$N$$ must contain at least $$one$$ factor of the form $$4k+3$$.

(6) Lastly, we show that if $$N$$ had a factor of the form $$4k+3$$, it leads to the anticipated contradiction:

Let's refer to this prime factor of $$N$$ as $${q}_i$$. Since all the prime factors of the form $$4k+3$$ are limited to the list $${q}_1,{q}_2,...,{q}_s$$ by assumption, $${q}_i$$ must belong in this list. But this implies that $${q}_i$$ divides $$N$$:

$${q}_i$$|$$N$$ = $${q}_i$$|$$4{q}_1{q}_2....{q}_s-1$$

$$\rightarrow$$ $${q}_i$$|$$1$$

And we have arrived at a contradiction. Therefore we conclude there exist infinitely many primes of the form $$4k+3$$