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?


  • 11
    $\begingroup$ 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. $\endgroup$ Nov 26, 2012 at 12:00
  • $\begingroup$ @GerryMyerson can you show me a way to prove it? $\endgroup$ Nov 26, 2012 at 12:10
  • 1
    $\begingroup$ 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. $\endgroup$
    – lee
    Nov 26, 2012 at 12:12
  • $\begingroup$ 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. $\endgroup$
    – WimC
    Nov 26, 2012 at 12:31
  • 6
    $\begingroup$ @lee, Dirichlet is truly overkill for this problem. $\endgroup$ Nov 26, 2012 at 21:58

7 Answers 7


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.

  • 2
    $\begingroup$ 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? $\endgroup$ Sep 15, 2014 at 21:52
  • 1
    $\begingroup$ It's from the $(n!)^{p - 1}$. $\endgroup$
    – zscoder
    Sep 22, 2014 at 13:28
  • 4
    $\begingroup$ 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$. $\endgroup$
    – Math101
    Jul 22, 2019 at 10:17
  • $\begingroup$ 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… $\endgroup$
    – 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.

  • $\begingroup$ Do you mean $N = (2p_1 \dots p_n)^2 + 1$? $\endgroup$
    – Robin
    Jun 7 at 17:10
  • $\begingroup$ @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. $\endgroup$
    – Robin
    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.

  • $\begingroup$ Please use MathJax to make your maths look pretty. Also, you are better focusing on more recent questions (this one is 9 years old). $\endgroup$
    – user1729
    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.

  • 3
    $\begingroup$ 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. $\endgroup$
    – user296602
    Jan 12, 2016 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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