14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Arturo Magidin Mar 3 '11 at 19:10
  • $\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 '15 at 22:44
  • $\begingroup$ Is this due to the division theorem? $\endgroup$ – Valentino Dec 2 '15 at 22:55
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ very good observation. That was my typo. $$p_0 = 3$$ was actually true. Thank you. $\endgroup$ – Chan Feb 10 '11 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 '18 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$ – Andrea Mori Jan 28 '18 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 '18 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 '18 at 10:14
9
$\begingroup$

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$).
It is easy to verify that this newly constructed integer is coprime to all the prior $\: p $'s, namely:

$$\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}$$

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). For a handful of proofs of said gcd property see my post here.

$\endgroup$

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.