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