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).
Best Answer
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.$