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<p$ 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$

  • $\begingroup$ 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... $\endgroup$ – 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.

  • $\begingroup$ (+1) for most required reasoning. Can you recommend any book for elementary number theory? $\endgroup$ – M Desmond Feb 21 '19 at 16:57
  • $\begingroup$ @MDesmond: I would recommend David Burton's Elementary Number Theory. $\endgroup$ – 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$.

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.