# Establishing infinitely many primes of the form $4k+1$.

Establish that there are infinitely many primes of the form $$4k+1$$.

I was studying primitive roots, and it was recently proven that the odd prime divisors $$n^2 +1$$ are all of the form of $$4k+1$$.

A proof in Burton's Elementary Number Theory assumes that there are finitely many primes of the form $$4k+1$$. The book lets $$N = (2p_1...p_n)^2 +1$$ ($$p_i$$ are the primes of form $$4k+1$$ then proceeds that this number would have a prime of the form $$4k+1$$ that is not $$p_i$$ ($$i$$ between $$1$$ and $$n$$) because $$p_i$$ does not divide 1, thus does not divide $$N$$.

I was wondering why you would use $$N =(2p_1...p_n)^2+1$$, doesn't letting $$N=(p_1...p_n)^2 +1$$ achieve the exact same thing?

• It isn't true that every prime factor of $n^2+1$ is of the form $4k+1$. If $n$ is odd then $2$ is a factor. We want to avoid that case.
– lulu
Sep 14, 2020 at 11:28
• Because $N$ is not generally of a form $4k+1$
– EDX
Sep 14, 2020 at 11:29
• For the purpose of the proof , we could also use the second expression, but we would have to argue more complicated because of the additional factor $2$. Sep 14, 2020 at 11:31
• N does not need to be in the form $4k+1$, just$n^2+1$. I do not get why having a factor of 2 is relevant, since the number N would still have odd divisors, which would be in the form 4k+1? and every prime 4k+1 would still not be able to divide N? Sep 14, 2020 at 11:32
• As @Peter remarks, you can do it without the factor of $2$ if you want to, but then you need a separate argument to the effect that $n^2+1$ can't be a power of $2$ (unless $n=0$). That's an easy exercise and worth doing. Including the factor of $2$ lets you skip that step.
– lulu
Sep 14, 2020 at 13:17

For every integer $$n$$, every odd prime divisor $$p$$ of $$n^2+1$$ is of the form $$p=4k+1$$ for some integer $$k$$. It follows that for every even integer $$n$$, every prime divisor $$p$$ of $$n^2+1$$ is of the form $$p=4k+1$$ for some integer $$k$$.
Let $$p_1,\ldots,p_m$$ be a finite list of primes. Then every odd prime divisor of $$N=(p_1\cdot p_2\cdots p_m)^2+1,$$ is a prime number of the form $$4k+1$$, and is coprime to $$p_1,\ldots,p_m$$. This shows that if $$N$$ has an odd prime divisor, then the finite list $$p_1,\ldots,p_m$$ is incomplete. So it remains to show that $$N$$ has an odd prime divisor, i.e. that $$N$$ is not a power of $$2$$.
On the other hand, every prime divisor of $$M=(2p_1\cdot p_2\cdots p_m)^2+1,$$ is a prime number of the form $$4k+1$$, and is coprime to $$p_1,\ldots,p_m$$. This shows that the finite list $$p_1,\ldots,p_m$$ is incomplete. No further argument is needed.