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

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