# I don't understand the following proof involving infinitely many primes.

Theorem: There are infinitely many primes congruent to $$3 \mod 4$$.

Proof: Assume that $$p_1 = 3, . . . , p_n$$ are primes of the form $$p_j ≡ 3 \mod 4$$. We will construct a new one by looking at $$N = 4p_1 · · · p_n − 1$$ (putting $$N = 4p_1 · · · p_n+3$$ would also work).

There is more to this proof but the rest of it I understand, what I don't get is where it says "$$N = 4p_1 · · · p_n − 1$$ (putting $$N = 4p_1 · · · p_n+3$$ would also work)".

I do not understand why we are writing $$4p_1 · · · p_n − 1$$. Is there a more clear way to prove this theorem?

• What is the Theorem? (I think one can figure it out by reading the proof, but you should really state it explicitly). – lulu Oct 22 '18 at 12:55
• Please use Jax for readability. – Wuestenfux Oct 22 '18 at 12:55
• And...what is your question? Can you see how writing that expression works? Granted, it might seem a little arbitrary but, really, it's just the classical proof for the infinitude of primes modified (slightly) to work in this case. – lulu Oct 22 '18 at 12:56
• I edited in the theorem, my bad, and my question is that I don't understand the proof. I understand that P = a list of primes that are congruent to 3 mod 4, as we are saying there is a finite amount so we can prove by contradiction. But I dont get why we say N = 4p.... pn 3 – Zdravstvuyte94 Oct 22 '18 at 12:58
• The point is, how do we contradict the statement : "there are finitely many primes of the form $4n+3$"? One way of doing it, is to show that if you write down this set as $p_1,...,p_m$, then there is some prime $p$ which is actually lying outside this set but is of the form $4m+3$. We want that prime $p$, to come out as the prime factor of a large number $N$, like it i done in the proof of the infinitude of primes by Euclid. Ideally, $N$ should be a number that is not a multiple of $p_1,...,p_n$ but must have a prime fact of the form $4n+3$ to give a contradiction. – астон вілла олоф мэллбэрг Oct 22 '18 at 13:03

The point is, how do we contradict the statement : "there are finitely many primes of the form $$4n+3$$"? One way of doing it, is to show that if you write down this set as $$p_1,...,p_m$$, then there is some prime $$p$$ which is actually lying outside this set but is of the form $$4m+3$$. We want that prime $$p$$, to come out as the prime factor of a large number $$N$$, like it is done in the proof of the infinitude of primes by Euclid. Ideally, $$N$$ should be a number that is not a multiple of $$p_1,...,p_n$$ but must have a prime factor of the form $$4m+3$$ to give a contradiction.

That, in part, provides at least a guess for how such an $$N$$ can be produced : take the product of all supposed primes of the form $$4n+3$$, and maybe add/subtract $$1$$ or $$3$$, so that this number is now not divisible by any of the $$p_i$$. At least this much can be ensured. That $$N$$ must have a factor of the form $$4n+3$$ is something brilliantly falling out : you can call it luck or foresight, but it so happens beyond this point that this $$N$$ works (and some other one does not). For example, see what you can do with $$4n+1$$ primes.

The key ideas (colored below) are clarified after a slight amount of abstraction. Below we prove a lemma that includes both Euclid's classical proof, as well as the OP (and others).

Lemma $$\$$ Suppose $$\,S\,$$ is a set of positive integers that is $$\rm\color{#0a0}{closed}$$ under multiplication, and $$\,\color{#c00}{\bf 1}\in S,\,$$ and for any positive integer $$\,n\,$$ there exists a positive integer $$\,c(n)\color{#0af}{\not\in S}\,$$ with $$\,c(n)\,$$ $$\rm\color{#90f}{coprime}$$ to $$\,n.\,$$ Then there exist infinitely many primes not in $$\,S.$$

Proof $$\$$ For induction, let $$\,p_1,\ldots p_k\,$$ be primes $$\,\not\in S.\,$$ Then $$\,c := c(p_1\!\cdots p_k)\color{#0af}{\not\in S}\,$$ so $$\,c >\color{#c00}{\bf 1}\,$$ hence $$\,c\,$$ has a prime factor. Not every prime factor of $$\,c\,$$ lies in $$\,S\,$$ (else their product $$\,c\,$$ would be in $$\,S\,$$ by $$\,S\,$$ $$\rm\color{#0a0}{closed}$$ under multiplication). Thus $$\,c\,$$ has a prime factor $$\,p\not\in S.\,$$ Since $$\,c\,$$ is $$\rm\color{#90f}{coprime}$$ to $$\,p_1\cdots p_k\,$$ so too is its factor $$\,p,\,$$ hence $$\,p\neq p_i\,$$ is a new prime $$\not\in S.$$

Euclid's proof is the special case $$\ S = \{1\}\$$ and $$\,\ c(n) = n+1.$$

The OP is also a special case: $$\, S = 4\,\Bbb N + 1\,$$ and $$\,c(n) = 4n\!-\!1.\$$ Let's trace this particular proof.

Starting with the empty list of primes with product $$= \color{#c00}{\bf 1},$$ we construct the new prime

$$4(\ \ )-1 = 4(\color{#c00}{\bf 1})-1 = 3 =: p_1.\$$ Repeating with the singleton list $$\, p_1\,$$ leads to

$$4(p_1)\!-\!1 = 4(3)\!-\!1 = 11 =: p_2.\$$ Repeating with the list $$\, p_1,p_2\,$$ leads to

$$4(p_1p_2 )-1 = 4(3\cdot 11)-1 = 131 =: p_3.\$$

They remain prime $$\ 3, 11, 131, 17291, 298995971 \$$ till we reach the sixth element

$$n = 89398590973228811 = 8779\cdot 10079\cdot 1010341471$$

where we need to choose a (guaranteed) factor $$\,\not \equiv 1\pmod{4},\,$$ e.g. the least $$= 8779$$.

You can find further terms in OEIS sequence A057205

If we use $$\,c(n) = 4n\!+\!3\,$$ we obtain $$\, 7,31,13,11287,67,\ldots$$ (choosing least prime factors)