Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
You don't have to "sign" your name; it's signed already by your user name. Also, you never stated the theorem that was being proven, did you notice that? – Arturo Magidin Mar 3 '11 at 19:10
"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. – Valentino Dec 2 '15 at 22:44
Is this due to the division theorem? – Valentino Dec 2 '15 at 22:55
up vote 10 down vote accepted

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.

share|cite|improve this answer
very good observation. That was my typo. $$p_0 = 3$$ was actually true. Thank you. – Chan Feb 10 '11 at 15:52

That part of the proof is simply a variant of Euclid's classical method for producing a new prime. Instead of $\rm\ 1+ p\cdot p_1\cdots p_n\ $ it employs $\rm\ p+ p_0\cdots p_n\:,\: $ where $\rm\ (p,\ p_i) = 1\:.\: $ (above $\rm\: p=3,\ p_0 = 4\:$)
It is easy to verify that this newly constructed integer is coprime to all the prior $\rm\: p $'s, namely:

$\rm\quad\quad\quad\quad\quad\quad\quad (p,\ \ \: p+p_0\cdots p_n)\ =\ (p,\ p_0\cdots p_n)\ =\ 1\ \ $ via $\rm\ \ (p,\ p_i)\ =\ 1$

$\rm\quad\quad\quad\quad\quad\quad\quad (p_i,\ p+ p_0\cdots p_n)\ =\ (p_i,\ p)\ =\ 1\ $

Essentially this proof relies on the fact that $\rm\ (p\:q,\ p+q) = 1\ \iff\ (p,\ q) = 1\:.\ $ Hence to produce a number coprime to $\rm\ n\ $ we can simply sum the factors $\rm\ p,\:q\ $ from any coprime splitting $\rm\ n = p\:q\:.\ $ Euclid's classic proof uses the trivial splitting where $\rm\ q = 1\ $ (and $\rm\:p\:$ is a product of given primes). Ribenboim credits this splitting-form generalization of Euclid's proof to Stieltjes (1890). For a handful of proofs of said gcd property see my post here.

share|cite|improve this answer
Thanks. – Chan Feb 10 '11 at 15:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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