# Proof explanation of There are Infinitely many primes of the form $4n+3$.

There are infinitely many primes of the form $$4n+3$$. Proof: Define $$q$$ by $$q=2^2.3.5...p-1$$. Then $$q$$ is of the form $$4n+3$$, and is not divisible by any of the primes up to $$p$$. It cannot be product of primes $$4n+1$$ only, since the product of two numbers of this form is of same form; and therefore it is divisible by a prime $$4n+3$$, greater than $$p$$.

I don't understand how "It cannot be product of primes $$4n+1$$ only, since the product of two numbers of this form is of same form"have conclusion "therefore it is divisible by prime greater than $$p$$" ? Also how $$4n+1$$ came out from thin air? Mine version of explanation will exclude $$4n+1$$ since you can literally say $$4n+3$$ is prime the nothing to prove else there are prime not included in that weird $$q$$ so using fundamental theorem of arithmetic there is one more prime number. Also how $$q$$ is derived? My may is you first have multiple of prime then you need to force this to be of form $$4n+3$$ by $$4(d+q)+3$$ where $$q$$ is $$-1$$ and $$d$$ is multiple of prime number finite amount I think it should be prime number of form $$4n+3$$ in $$d$$ which is missing from textbook definition. I hope I get absolute correct and detailed explanation. Thanks for attention!

• A product of numbers of the form $4n+1$ also has this form. This is the key for this proof. This guarantees that there must be a prime factor of the form $4n+3$ – Peter Sep 14 '20 at 12:18
• A prime $>2$ is either in the form of $4n+1$ or $4n+3$. Suppose $q$ has no prime factor of the form $4n+3$. Then all prime factors of $q$ is of the form $4n+1$. – player3236 Sep 14 '20 at 12:23
• OK, $q$ is odd, so it only has odd prime factors. But every odd prime number (in fact every odd number) is either of the form $4n+1$ or of the form $4n+3$. If all prime factors were of the form $4n+1$ , $q$ would be of the form $4n+1$ as well which is not the case. – Peter Sep 14 '20 at 12:23
• We can reduce $4n+5,4n+7$ etc. to the case $4n+1$ or $4n+3$ if we choose $n$ suitable. And in fact, Euklid's idea is imitated. $q$ cannot have a prime factor less than or equal to $p$. – Peter Sep 14 '20 at 12:32
• If we multiply two numbers of the form $4n+1$ , we have $$(4a+1)\cdot(4b+1)=16ab+4a+4b+1=4(4ab+a+b)+1$$ so we again get a number of the form $4n+1$ – Peter Sep 14 '20 at 12:40

Summarizing the comments, note that all odd numbers and therefore all primes greater than $$2$$ can be expressed as $$4n+1$$ or $$4n+3$$. A number of the form $$4n+5=4(n+1)+1$$ is of the first form.
Second, the product of numbers of the form $$4n+1$$ is again of the form $$4n+1$$. We can see that by writing $$(4n+1)(4m+1)=16nm+4(n+m)+1$$
Third, assume that there are a finite number of primes of the form $$4n+3$$. Among them are $$3,7,11,19 \ldots$$. Let the greatest of them be $$p$$. Form the number $$N=2^2\cdot 3 \cdot 5 \cdot 7 \ldots p-1$$ where the factors are all the primes up to $$p$$. $$N$$ is of the form $$4n+3$$ and is not divisible by any of the primes up to $$p$$. By our hypothesis it must be a product of primes of the form $$4n+1$$ because all the primes of form $$4n+3$$ are less than or equal to $$p$$. Since the product of numbers of the form $$4n+1$$ is again of the form $$4n+1$$ we have a contradiction.
Therefore there are infinitely many primes of the form $$4n+3$$.