Understanding that there are infinitely many primes of form $4n+3$
I read the proof of, that there are infinitely many primes of form $4n+3$ and it goes here:
Proof. In anticipation of a contradiction, let us assume that there exist only finitely many primes of the form $4n+3$; call them $q_1,q_2,\ldots ,q_s$. Consider the positive integer $$N=4q_1q_2\cdots q_s -1 = 4(q_1q_2\cdots q_s -1)+3$$ and let $N=r_1r_2\cdots r_t$ be its prime factorization. Because $N$ is an odd integer, we have $r_k\ne 2$ for all $k$, so that each $r_k$ is either of the form $4n+1$ or $4n+3$. By the lemma, the product of any number of primes of the form $4n+1$ is again an integer of this type. For $N$ to take the form $4n+3$, as it clearly does, $N$ must contain at least one prime factor $r_i$ of the form $4n+3$. But $r_i$ cannot be found among the listing $q_1,q_2,\ldots ,q_s$, for this would lead to the contradiction that $r_i \mid 1$. The only possible conclusion is that there are infinitely many primes of the form $4n+3$.
$q_1,q_2,\ldots ,q_s$ I need an explanation from last three line i.e. this.
They said that:
- $q_{1},q_{2}, \cdots ,q_{s}$ is of the form $4n+3$ (let).
- $r_{i}$ is of form $4n+3$ (at least one).
- $r_{i}$ cannot be found in listing $q_{1},q_{2}, \cdots ,q_{s}$
And lemma they used is:
The product of two or more integers of the form $4n+1$ is of the same form.
My problems:
- If above two holds then why $r_{i}$ cannot be found in listing $q_{1},q_{2}, \cdots ,q_{s}$.
- And how $r_{i}|1$
- If all this holds then why $q's$ are infinite.
Please give the most elementary explanation as you can, any help worth a lot to me, Thanks.
(I took this from David M. Burton book).
Solution 1:
The proof assumes that there are only finitely many primes of the form $4n+3.$ They are listed as $q_1,\cdots,q_s.$ From them the number $N=4q_1\cdots q_s-1$ is defined. (Note that the proof argues by reduction ad absurdum. Do you remember Euclid's proof for the existence of infinitely many primes? He assumed that there are finitely many and arrives at a contradiction.)
Then it is shown that $N$ is of the form $4n+3$ and it is considered its prime factorization. Why must be at least one of the $r_i$'s of the form $4n+3?$ If all of them are of the form $4n+1$ then it would be $$N=r_1\cdots r_t=4n+1.$$ This is not possible because $N=4n+3.$
Finally, we have that
$$N=4q_1\cdots q_s-1=r_1\cdots r_t.$$ If $r_i=q_j$ for some $j$ then we have that $r_i$ divides $4q_1\cdots q_s$ and $r_1\cdots r_t.$ So, it must divide $$1=r_1\cdots r_t-4q_1\cdots q_s.$$ And this is not possible.
Thus we conclude that the number of primes of the form $4n+3$ must be infinite. Why? Because if we assume they are finite, say $q_1,\cdots, q_s$ we find a prime number $r_i$ of the form $4n+3$ that is not in the list above. This contradicts the assumption that all prime numbers of the form $4n+3$ are $q_1,\cdots, q_s.$
Solution 2:
Imagine that $r_i=q_k$. Then clearly $r_i \mid 4q_1q_2\cdots q_s$, but we are also given that $r_i \mid N=4q_1q_2\cdots q_s-1$ These two results together imply that $r_i \mid 1$, a contradiction that eliminates $r_i$ from the list of $q$ primes.
This means that $r_i$ is additional to the list of $q$ primes - given any finite list of $4n+3$ primes we can generate another, therefore the number of such primes is infinite.
Solution 3:
Fact: If $x|a$ and $x|b$ then $x|a \pm b$. Therefore if $x|4q_1...q_s$ and $x|4q_1.....q_s - 1$ then $x|(4q_1....q_s) - (4q_1....q_s - 1)=1$. So $x|1$ so $x=1$.
Fact: If $q_i \in \{q_1,....,q_s\}$ then $q_i|4q_1...q_s$.
So if $r > 1$ and $r|N =4q_1....q_s - 1$ then we can not have $r \in \{q_1,....,q_s\}$ because if we did we would have both $r = q_i|4q_1....q_s$ and $r|4q_1....q_s$ which would mean, by the above fact, that $r =1$ which is a contradiction.
Now if $N=4q_1....q_s -1 > 1$ then $N$ has a prime factor $r$ and as $r|N$, $r \not \in \{q_1,....,q_s\}$ by the above facts.
.... And that's the heart of it. If $\{q_1,.....,q_s\}$ have something in common and $r$ has it in common too, then $\{q_1,.....,q_s\}$ can not be ALL the numbers with that in common because $r$ is not in $\{q_1,.....,q_s\}$.
So the proof continues to show that if $q_i$ are all primes of the form $4k+3$ then $N$ has a prime factor $r$ that is also in the form $4k+3$. That's the thrust of the proof. Once we prove that, it follows that there must be an infinite number of primes in that form because... By the facts above $r$ is not in $\{q_1,.....,q_s\}$. So that list can not contain all the primes in that form.
... but we DEFINED $\{q_1,.....,q_s\}$ to be ALL primes of that form by definition.
So.... it is impossible to make such a list.
If the number of primes of that form were finite we could make such a list. But we cant. So there must be an infinite number of primes of that form.