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?


  • $\begingroup$ "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. $\endgroup$
    – Valentino
    Dec 2, 2015 at 22:44
  • $\begingroup$ Is this due to the division theorem? $\endgroup$
    – Valentino
    Dec 2, 2015 at 22:55
  • $\begingroup$ 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. $\endgroup$ Aug 2, 2020 at 18:14

3 Answers 3


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.

  • $\begingroup$ very good observation. That was my typo. $$p_0 = 3$$ was actually true. Thank you. $\endgroup$
    – roxrook
    Feb 10, 2011 at 15:52
  • $\begingroup$ 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}$. $\endgroup$
    – jiten
    Jan 27, 2018 at 16:15
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 28, 2018 at 1:30
  • $\begingroup$ 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. $\endgroup$
    – jiten
    Jan 28, 2018 at 9:32
  • $\begingroup$ 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. $\endgroup$
    – jiten
    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$


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.