# there are an infinite number of primes $\equiv\pm 1\penalty 0@\mskip 8.0mu ({\symoperators mod}\mskip 6.0mu 4)$

###### Theorem 1.

There are an infinite number of primes congruent to $3\pmod{4}$.

###### Proof.

Choose any prime $p\equiv 3\pmod{4}$; we find a prime of that form that exceeds $p$.

 $N=(2^{2}\cdot 3\cdot 5\cdot 7\cdots p)-1$

Clearly $N\equiv 3\pmod{4}$, and thus must have at least one prime factor that is also $\equiv 3\pmod{4}$. But $N$ is not divisible by any prime less than or equal to $p$, so must be divisible by some prime congruent to $3\pmod{4}$ that exceeds $p$. ∎

###### Theorem 2.

There are an infinite number of primes congruent to $1\pmod{4}$.

###### Proof.

Given $N>1$, we find a prime $p>N$ with $p\equiv 1\pmod{4}$. Let $p$ be the smallest (odd) prime factor of $(N!)^{2}+1$; note that $p>N$. Now

 $(N!)^{2}\equiv-1\pmod{p}$

and therefore

 $(N!)^{p-1}\equiv(-1)^{(p-1)/2}\pmod{p}.$

By Fermat’s little theorem, $(N!)^{p-1}\equiv 1\pmod{p}$, so we have

 $(-1)^{(p-1)/2}\equiv 1\pmod{p}$

The left-hand side cannot be -1, since then $0\equiv 2\pmod{p}$. Thus $(-1)^{(p-1)/2}=1$ and it follows that $p\equiv 1\pmod{4}$. ∎

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 $\equiv 1\pmod{4}$ has a factor of the same kind.

## References

Title there are an infinite number of primes $\equiv\pm 1\penalty 0@\mskip 8.0mu ({\symoperators mod}\mskip 6.0mu 4)$ ThereAreAnInfiniteNumberOfPrimesequivpm1pmod4 2013-03-22 16:56:59 2013-03-22 16:56:59 rm50 (10146) rm50 (10146) 4 rm50 (10146) Theorem msc 11N13