# Elementary proof of the primes of the form $4n+3$ [duplicate]

I am a highschool student going through the elementary number theory found the following please help me understanding this.

prove that there are infinitely many primes of the form $$4k+3$$

My book start this way :

Let $$n=4k+3$$ and $$S=\{d\,|\,d\text{ is a divisor of n of the form 4m+3}\}$$. As $$n$$ belongs to $$S$$ so $$S$$ is not the empty set, so there must be a least element say $$p$$. Then $$p=\min\{d\mid d\in S\}$$. Now there are two possibilities that $$p$$ may be prime or composite, say if $$p$$ is composite then $$p=ab$$ as $$p=4m+3$$ at least one of the $$a,b$$ must be in the same form. Say $$a=4l+3$$ for some $$l$$. Hence as $$a it contradicts our assumption of minimum element. Thus $$p$$ is prime.

Up to this I got it but after this I am unable to grasp :

So from this we can conclude that every number in the form $$4k+3$$ must have at least one prime divisor of the same form. Now consider $$4(n!-1)+3=4n!-1$$ so from the above it should have prime divisor of the same form. But $$p$$ does not divide $$4n!-1$$ for any natural number $$p$$ in $$[2,n]$$ so $$p>n$$. Hence there are infinitely many primes.

Please help me in the last part, I did not get why $$p$$ does not divide $$4n!-1$$ when $$p$$ is less than equal to $$n$$

• Let me just say that your book is an exceedingly poor book if you have copied what it said exactly. I know how to prove the claim, and yet the so-called 'proof' in your question is so jumbled that I am not sure whether the author can actually do rigorous mathematics... – user21820 Feb 25 '19 at 8:05

The missing part of the reasoning is:

Assume there are finitely many primes of the form $$4k+3$$. We can define $$n$$ as the highest such prime.

Now consider $$n'=4(n!-1)+3=4(n!)-1$$. That $$n'$$ is of the form $$4m'+3$$, thus we can define $$p$$ as the least positive divisor of $$4(n!)−1$$ of the form $$4m+3$$, and we have seen that such $$p$$ must be prime.

If it held that $$p\le n$$, then $$p$$ would divide $$n!$$, thus would divide $$4(n!)$$, thus would not divide $$4(n!)−1$$. It follows that $$p$$ is larger than $$n$$. By construction, it is also of the form $$4m+3$$, and is prime. That contradicts the assumption in bold.

That assumption is thus false, Q.E.D.

• (+1) for most required reasoning. Can you recommend any book for elementary number theory? – M Desmond Feb 21 '19 at 16:57
• @MDesmond: I would recommend David Burton's Elementary Number Theory. – user21820 Feb 25 '19 at 8:08

If $$p\leqslant n$$, then $$p$$ divides $$n!$$ (since $$n!$$ is the product of all natural numbers up to $$n$$, one of which is $$p$$) and therefore $$p$$ divides $$4n!$$. If it divided also $$4n!-1$$, it would also divide their difference, which is $$1$$.

• Sir ! how $p>n$ guarantee the infinite number of primes ? – M Desmond Feb 21 '19 at 16:46