I am almost done with my proof that there are infinitely many primes of the form $4k+3$, but have one remaining concern.

My chosen $N$, the subject of my contradictions, is defined as $4(p_1p_2\cdots p_n-1)+3$ where $p_1p_2\cdots p_n$ are the finite primes of the form $4k+3$ (assumed finite earlier for contradiction.)

My proof hinges on the fact that none of the $p_i$'s can divide $N$ without remainder. I claim that this is by "construction of $N$," but lack the more rigorous proof. Any tips?

  • 2
    $\begingroup$ Notice that $4(p_1 ... p_n -1) +3 = 4p_1 ... p_n -1$ so that $N$ cannot be divisible by any of the $p_i$. $\endgroup$ – 3-in-441 Sep 14 '16 at 20:51
  • $\begingroup$ See my comment under Jack d'Aurizio's answer. $\qquad$ $\endgroup$ – Michael Hardy Sep 14 '16 at 20:59

The usual proof goes along the following lines: assume that $3=p_1,7=p_2,p_3,\ldots,p_m$ are some distinct primes of the form $4k+3$. The huge number $$ N = -1+4\prod_{j=1}^{m}p_j $$ is $\equiv -1\pmod{4}$, hence it must have a prime divisor $\equiv -1\pmod{4}$. However, neither $p_1,p_2,\ldots,p_{m-1}$ or $p_m$ are divisors of $N$, since they all divide $N+1$, hence there must be an extra prime number of the form $4k+3$.

A similar approach is to construct a sequence of integers $\{a_n\}_{n\geq 1}$ with the properties that $a_n\equiv -1\pmod{4}$ for every $n\geq 1$, and for every $m>n\geq 1$ $$ \gcd(a_n,a_m)=1 $$ holds. It follows that there must be at least one different prime of the form $4k+3$ for each element of the sequence. A sequence fulfilling such constraints is, for instance, $$ a_1=3,\qquad a_n = -1+4\prod_{k=1}^{n-1}a_k.$$

  • $\begingroup$ Why make it a proof by contradiction? Don't assume these are all of the primes of the form $4k+3$ that exist; just assume they are $m$ of them. They don't even need to be the smallest $m$ of them. Then conclude that the prime divisor of $N$ that's congruent to $-1$ must be some prime that was not among those $m$ of them; hence there are more primes of that form. $\qquad$ $\endgroup$ – Michael Hardy Sep 14 '16 at 20:57
  • 1
    $\begingroup$ I think you missed the point of the question. The question seems to be asking for tips on how to show that none of the $p_i$s are divisors of $N$. $\endgroup$ – Duncan Sep 14 '16 at 20:59
  • $\begingroup$ @MichaelHardy: a fine way. The constructivist choice? :D $\endgroup$ – Jack D'Aurizio Sep 14 '16 at 20:59
  • $\begingroup$ @Duncan: five words added to explain that point. $\endgroup$ – Jack D'Aurizio Sep 14 '16 at 21:00
  • 1
    $\begingroup$ @JackD'Aurizio : The simpler and less confusing choice. Here are the problems. Euclid wrote that is $S$ is any finite set of primes, then the prime factors of $1+\prod S$ are not in $S$, so there are always more primes than those in $S$. Many modern authors, probably starting with Dirichlet in the 1850s, have ERRONEOUSLY said Euclid wrote it as a proof by contradiction, assuming $S$ contains all primes. Firstly, that makes the proof appear more complicated than it is by adding a pointless complication. Secondly, some authors write "This number, not being divisible by$\,\ldots\qquad$ $\endgroup$ – Michael Hardy Sep 14 '16 at 21:03

Your Answer
