# Infinitely number of primes in the form $4n+1$ proof

Question: Are there infinitely many primes of the form $$4n+3$$ and $$4n+1$$?

My attempt: Suppose the contrary that there exist finitely many primes of the form $$4n+3$$, say $$k+1$$ of them: $$3,p_1,p_2,....,p_k$$

Consider $$N = 4p_1p_2p_3...p_k+3$$, $$N$$ cannot be a prime of this form. So suppose that $$N$$=$$q_1...q_r$$, where $$q_i∈P$$

Claim: At least one of the $$q_i$$'s is of the form $$4n+3$$:

Proof for my claim: $$N$$ is odd $$\Rightarrow q_1,...,q_r$$ are odd $$\Rightarrow q_i \equiv 1\ (\text{mod }4)$$ or $$q_i ≡ 3\ (\text{mod }4)$$

If all $$q_1,...q_r$$ are of the form $$4n+1$$, then $$(4n+1)(4m+1)=16nm+4n+4m+1 = 4(\cdots) +1$$

Therefore, $$N=q_1...q_r = 4m+1$$. But $$N=4p_1..p_k+3$$, i.e. $$N≡3\ (\text{mod }4)$$, $$N$$ is congruent to $$1\ \text{mod }4$$ which is a contradiction.

Therefore, at least one of $$q_i \equiv 3\ (\text{mod }4)$$. Suppose $$q_j\equiv 3\ (\text{mod }4)$$

$$\Rightarrow$$ $$q_j=p_i$$ for some $$1\leq i \leq k$$ or $$q_j =3$$

If $$q_j=p_i≠3$$ then $$q_j$$ | $$N = 4p_1...p_k + 3 \Rightarrow q_j=3$$ Contradiction!

If $$q_j=3$$ ($$\neq p_i$$, $$1\leq i \leq k$$) then $$q_j | N = 4 p_1...p_k + 3 \Rightarrow q_j=p_t$$ for some $$1 \leq i \leq k$$ Contradiction!

In fact, there must be also infinitely many primes of the form $$4n+1$$ (according to my search), but the above method does not work for its proof. I could not understand why it does not work. Could you please show me?

Regards

• It doesn't work, because it doesn't work. A product of numbers 1 mod 4 can't be 3 mod 4, but a product of numbers 3 mod 4 can be 1 mod 4. There are other methods. Nov 26, 2012 at 12:00
• @GerryMyerson can you show me a way to prove it? Nov 26, 2012 at 12:10
• Use the Dirichlet's theorem which states that for a pair of numbers a, b satisfying gcd(a,b)=1, then the series {an+b} must contain infinitely many primes. Your problem is pointed out by Gerry Myerson.
– lee
Nov 26, 2012 at 12:12
• A prime divisor of $m^2+1$ for an integer $m$ is either $2$ or equal to $1$ ($\bmod$ $4$). Then your argument can be adapted a bit to show that a finite number of such primes is insufficient to produce all numbers of this form.
– WimC
Nov 26, 2012 at 12:31
• @lee, Dirichlet is truly overkill for this problem. Nov 26, 2012 at 21:58

Suppose $n>1$ is an integer. We define $N=(n!)^2 +1$. Suppose $p$ is the smallest prime divisor of $N$. Since $N$ is odd, $p$ cannot be equal to $2$. It is clear that $p$ is bigger than $n$ (otherwise $p \mid 1$). If we show that $p$ is of the form $4k+1$ then we can repeat the procedure replacing $n$ with $p$ and we produce an infinite sequence of primes of the form $4k+1$.

We know that $p$ has the form $4k+1$ or $4k+3$. Since $p\mid N$ we have $$(n!)^2 \equiv -1 \ \ (p) \ .$$ Therefore $$(n!)^{p-1} \equiv (-1)^{ \frac{p-1}{2} } \ \ (p) \ .$$ Using Fermat's little Theorem we get $$(-1)^{ \frac{p-1}{2} } \equiv 1 \ \ (p) \ .$$ If $p$ was of the form $4k+3$ then $\frac{p-1}{2} =2k+1$ is odd and therefore we obtain $-1 \equiv 1 \ \ (p)$ or $p \mid 2$ which is a contradiction since $p$ is odd.

• Could you explain me how you deduce the equality in the last display? I don't get how it follows from Fermat. How do you exclude the righ hand side to be -1? Sep 15, 2014 at 21:52
• It's from the $(n!)^{p - 1}$. Sep 22, 2014 at 13:28
• I think the last two display formulas can be replaced by the following. According to the Fermat little theorem $n!^{p-1}\equiv 1$ $\,(p)$. We know that $p-1$ is the form of $2k$. Therefore, $n!^{2k}\equiv (-1)^k\equiv 1$, $(p)$. Hence $k=2m$ and $p=4m+1$. Jul 22, 2019 at 10:17
• Where does this proof come from (like how would someone come up with it)? Does it generalize beyond just 4k+1? I do like the proof a lot, but perhaps it is a bit “too cute” for its own good…
– D.R.
Sep 10, 2021 at 7:56

There's indeed another elementary approach:

For every even $n$, all prime divisors of $n^2+1$ are $\equiv 1 \mod 4$. This is because any $p\mid n^2+1$ fulfills $n^2 \equiv -1 \mod p$ and therefore $\left( \frac{-1}{p}\right) =1$, which is, since $p$ must be odd, equivalent to $p \equiv 1 \mod 4$.

Assume that there are only $k$ primes $p_1,...,p_k$ of the form $4m+1$. Then you can derive a contradiction from considering the prime factors of $(2p_1...p_k)^2+1$.

(There's also an elementary approach to show that there are infinitely many primes congruent to $1$ modulo $n$ for every $n$, but that one gets rather tedious. (See: Wikipedia as a reference.))

There are infinite primes in both the arithmetic progressions $$4k+1$$ and $$4k-1$$.
Euclid's proof of the infinitude of primes can be easily modified to prove the existence of infinite primes of the form $$4k-1$$.

Sketch of proof: assume that the set of these primes is finite, given by $$\{p_1=3,p_2=7,\ldots,p_k\}$$, and consider the huge number $$M=4p_1^2 p_2^2\cdots p_k^2-1$$. $$M$$ is a number of the form $$4k-1$$, hence by the fundamental theorem of Arithmetics it has a prime divisor of the same form. But $$\gcd(M,p_j)=1$$ for any $$j\in[1,k]$$, hence we have a contradiction.

Given that there are infinite primes in the AP $$4k-1$$, is that possible that there are just a finite number of primes in the AP $$4k+1$$? It does not look as reasonable, and indeed it does not occur. Let us define, for any $$n\in\mathbb{N}^+$$, $$\chi_4(n)$$ as $$1$$ if $$n=4k+1$$, as $$-1$$ if $$n=4k-1$$, as $$0$$ if $$n$$ is even. $$\chi_4(n)$$ is a periodic and multiplicative function (a Dirichlet character) associated with the $$L$$-function $$L(\chi_4,s)=\sum_{n\geq 1}\frac{\chi_4(n)}{n^s}=\!\!\!\!\prod_{p\equiv 1\!\!\pmod{4}}\left(1-\frac{1}{p^s}\right)^{-1}\prod_{p\equiv 3\!\!\pmod{4}}\left(1+\frac{1}{p^s}\right)^{-1}.$$ The last equality follows from Euler's product, which allows us to state $$L(\chi_4,s)=\prod_{p}\left(1+\frac{1}{p^s}\right)^{-1}\prod_{p\equiv 1\!\!\pmod{4}}\frac{p^s+1}{p^s-1}=\frac{\zeta(2s)}{\zeta(s)}\prod_{p\equiv 1\!\!\pmod{4}}\frac{p^s+1}{p^s-1}.$$ If the primes in the AP $$4k+1$$ were finite, the limit of the RHS as $$s\to 1^+$$ would be $$0$$.
On the other hand, $$\lim_{s\to 1^+}L(\chi_4,s)=\sum_{n\geq 0}\frac{(-1)^n}{2n+1}=\int_{0}^{1}\sum_{n\geq 0}(-1)^n x^{2n}\,dx=\int_{0}^{1}\frac{dx}{1+x^2}=\frac{\pi}{4}\color{red}{\neq} 0$$ so there have to be infinite primes of the form $$4k+1$$, too.

With minor adjustments, the same approach shows that there are infinite primes in both the APs $$6k-1$$ and $$6k+1$$. I have just sketched a simplified version of Dirichlet's theorem for primes in APs.

Suppose that there are only fitely many primes of the form $4k+1$, say $p_{1}, ..., p_{n}$, and consider $N =(p_{1} ...p_{n})^{2}+ 1$. $N>p_{i}$, for $1 ≤i≤n$, hence $N$ cannot be prime. Any number of the form $a^{2}+1$ has, except possibly for the factor $2$, only prime factors of the form $4m+1$.Since division into $N$ by each prime factor of the form $4k+1$ leaves a remainder $1$, $N$ cannot be composite, a contradiction. Hence, the number of primes of the form $4k +1$ must be infinite.

• Do you mean $N = (2p_1 \dots p_n)^2 + 1$? Jun 7 at 17:10
• @Robin nevermind - we know $p_1 = 2$ so $N$ is of the form $4n+1$, this just wasn't written as explicitly as other answers. Jun 7 at 17:14

A much simpler way to prove infinitely many primes of the form 4n+1.

Lets define N such that $N = 2^2(5*13*.....p_n)^2+1$ where $p_n$ is the largest prime of the form $4k+1$. Now notice that $N$ is in the form $4k+1$. $N$ is also not divisible by any primes of the form $4n+1$ (because k is a product of primes of the form $4n+1$).

Now it is also helpful to know that all primes can be written as either $4n+1$ or $4n-1$. This is a simple proof which is that every number is either $4n, 4n+1, 4n+2$ or $4n+3$. Thus all odd primes are of the form $4n+1$ or $4n+3$, the only prime ones. $4n+3$ can me written as $4n-1$ and thus all odd primes are of the form $4n+1$ or $4n-1$.

Now there is a theorem (we can prove this if needed) which says $$x^2\equiv-a^2\pmod p$$ then $p\equiv1\pmod4$ or that $4m+1=p$ where a and p are relatively prime

Now another way to state this theorem is that $x^2+a^2=pk$ for some integer k. Notice that our definition of $N$ is in the form of $x^2+a^2$ so it must equal $pk$ where $p\equiv1\pmod4$. Thus we have a contradiction and $p_n$ cannot be a largest prime of the form $4n+1$.

The approach we did in high school consisted of two parts.

(a) First prove that all prime divisors of $$a^2$$ are in the form of $$4m+1$$.

If $$p$$ is prime, then $$p|a^2+1 \implies a^2 ≡ -1 \mod p$$, so $$a^4 ≡ 1 \mod p$$

We know $$a^{p-1} ≡ 1 \mod p$$ from Fermat's little theorem, so $$4|p-1$$.

(b) There are infinitely many primes in the form of $$4m+1$$. Assume the opposite - there is k numbers of that form and let them be $$\{p_1, ... , p_k\}$$. Consider the number a = $$2*p_1*p_2...*p_k$$. The number $$a^2 + 1 = 4*(p_1^2)\cdot(p_2^2)\cdot \ldots\cdot(p_k^2) + 1$$ has at least one prime divisor of the form $$4m+1$$ (which we proved in (a)) and it isn't any of the numbers $$p_1,...,p_k$$, a contradiction.

Hope this helps, Zlata.

• Please use MathJax to make your maths look pretty. Also, you are better focusing on more recent questions (this one is 9 years old). May 25, 2021 at 21:11

Actually there is an even more elegant proof that shows that this holds true for all primes>2:

∀ primes,p ∈P & p>2,∃ k∈Q| k=(p-1)/4 or k= (p+1)/4

Proof: By definition every 4th integer, k ≥ 4, must have 2^2 (2 squared) as a factor. This means that every other even integer > 2 must have 2^2 as a factor.

For all primes p>2, the prime itself is odd and therefore p-1 and p+1 are both even.

Since p-1 and p+1 represent consecutive even integers, one and only one of them must have 2^2 as factors and thus (p±1)/4 is an integer. ∎

This applies to all primes greater than 2.

• This shows that there are infinitely many primes which are of the form $4k \pm 1$, not that there are infinitely many primes of each form individually. Rather, this answer needs only the fact that there are infinitely many odd primes.
– user296602
Jan 12, 2016 at 20:47