0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What is the Theorem? (I think one can figure it out by reading the proof, but you should really state it explicitly). $\endgroup$ – lulu Oct 22 '18 at 12:55
  • $\begingroup$ Please use Jax for readability. $\endgroup$ – Wuestenfux Oct 22 '18 at 12:55
  • $\begingroup$ 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. $\endgroup$ – lulu Oct 22 '18 at 12:56
  • $\begingroup$ 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 $\endgroup$ – Zdravstvuyte94 Oct 22 '18 at 12:58
  • $\begingroup$ 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. $\endgroup$ – астон вілла олоф мэллбэрг Oct 22 '18 at 13:03
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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)

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