Using the Legendre Symbol to Prove There are Infinitely Many Primes
There are infinitely many primes of the form
\[4k+1\]
.Proof
This is a case of Dirichlet's Theorem which implies infinitely many primes of the form
\[ak+b\]
. Suppose there are infinitely many primes of the form \[4k+1\]
, \[p_1, \; p_2,..., \; p_n\]
. Let \[N=4(p_1p_2...p_n)^2+1\]
. \[N\]
is odd, so must be divisible by some odd prime \[p\]
. The \[N=4(p_1p_2...p_n)^2+1 \equiv 0 \; (mod \; p) \rightarrow (p_1p_2...p_n)^2 \equiv -1 \; (mod \; p)\]
. \[(p_1p_2...p_n)^2\]
is a square number so \[(-1/p)=1\]
then by the properties of The Legendre Symbol, \[p\]
is of the form \[4k+1\]
. The assumption that \[p_1, \; p_2,...,p_n\]
are the only primes of this form forces \[p\]
to be one of these, say \[p_i\]
. But the \[p\]
divides \[N=4(p_1p_2...p_n)^2+1\]
and \[4(p_1p_2...p_n)^2\]
so \[p\]
divides \[N-4(p_1p_2...p_n)^2=1\]
which is impossible, so there are infinitely many primes of the form \[4k+1\]
. 
