there are an infinite number of primes $\equiv \pm 1\mathrm{@}(mod4)$

Theorem 1.

There are an infinite number of primes congruent to $\mathrm{3}\mathrm{(}\mathrm{mod}\mathrm{4}\mathrm{)}$.

Proof.

Choose any prime $p\equiv 3(mod4)$; we find a prime of that form that exceeds $p$.

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

Clearly $N\equiv 3(mod4)$, and thus must have at least one prime factor that is also $\equiv 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 $\mathrm{1}\mathrm{(}\mathrm{mod}\mathrm{4}\mathrm{)}$.

Proof.

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

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

and therefore

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

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

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

The left-hand side cannot be -1, since then $0\equiv 2(modp)$. Thus ${(-1)}^{(p-1)/2}=1$ and it follows that $p\equiv 1(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 $\equiv 1(mod4)$ has a factor of the same kind.

Title	there are an infinite number of primes $\equiv \pm 1\mathrm{@}(mod4)$
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