# Clarification needed for proof of infinitely many primes of the form $4k+3$

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?

• 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$. – 3-in-441 Sep 14 '16 at 20:51
• See my comment under Jack d'Aurizio's answer. $\qquad$ – 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.$$
• 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$ – Michael Hardy Sep 14 '16 at 20:57
• 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$. – Duncan Sep 14 '16 at 20:59
• @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$ – Michael Hardy Sep 14 '16 at 21:03