there are an infinite number of primes ±1@(\symoperatorsmod4)

Theorem 1.

There are an infiniteMathworldPlanetmath number of primes congruentMathworldPlanetmath to 3(mod4).


Choose any prime p3(mod4); we find a prime of that form that exceeds p.


Clearly N3(mod4), and thus must have at least one prime factorMathworldPlanetmath that is also 3(mod4). But N is not divisible by any prime less than or equal to p, so must be divisible by some prime congruent to 3(mod4) that exceeds p. ∎

Theorem 2.

There are an infinite number of primes congruent to 1(mod4).


Given N>1, we find a prime p>N with p1(mod4). Let p be the smallest (odd) prime factor of (N!)2+1; note that p>N. Now


and therefore


By Fermat’s little theorem, (N!)p-11(modp), so we have


The left-hand side cannot be -1, since then 02(modp). Thus (-1)(p-1)/2=1 and it follows that p1(mod4). ∎

Note that the variant of Euclid’s proof of the infinitude of primes used in the proof of Theorem 1 does not work for Theorem 2, since we cannot conclude that an integer 1(mod4) has a factor of the same kind.


Title there are an infinite number of primes ±1@(\symoperatorsmod4)
Canonical name ThereAreAnInfiniteNumberOfPrimesequivpm1pmod4
Date of creation 2013-03-22 16:56:59
Last modified on 2013-03-22 16:56:59
Owner rm50 (10146)
Last modified by rm50 (10146)
Numerical id 4
Author rm50 (10146)
Entry type Theorem
Classification msc 11N13