Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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

Consider $N$ = 4$p_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 => $q_1,...,q_r$ are odd => $q_i$ ≡ 1 (mod 4) or $q_i# ≡ 3 (mod 4)

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

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

Therefore, at least one of $q_i$ ≡ 3 (mod 4). Suppose $q_j$ ≡ 3 (mod 4)

=> $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$ = 4$p_1...p_k$ + 3 => $q_j$=3 Contradiction!

If $q_j$=3 (≠$p_i$ , 1$\leq$i $\leq$ k) then $q_j$ | $N$ = 4$p_1...p_k$ + 3 => $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?


share|cite|improve this question
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. – Gerry Myerson Nov 26 '12 at 12:00
@GerryMyerson can you show me a way to prove it? – Amadeus Bachmann Nov 26 '12 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 '12 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 '12 at 12:31
@lee, Dirichlet is truly overkill for this problem. – Gerry Myerson Nov 26 '12 at 21:58
up vote 16 down vote accepted

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.

share|cite|improve this answer
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? – Koenraad van Duin Sep 15 '14 at 21:52
It's from the $(n!)^{p - 1}$. – zscoder Sep 22 '14 at 13:28

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.))

share|cite|improve this answer
Didn't you get a warning that you were overriding my edit? – joriki Nov 26 '12 at 12:30

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.

share|cite|improve this answer
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. – T. Bongers Jan 12 at 20:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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