When an Integer Can be Expressed as a Sum of Two Squares
A number can be expressed as a sum of two squares if and only if and only if every prime factor of the form
\[4k+3\]
has an even power.Let
\[m^2\]
be the largest square factor of \[n\]
then we can write \[n=m^2r\]
, where \[r\]
is square free. The theorem asserts that \[n\]
can be written as the sum of two squares if and only if \[r\]
is not divisible by any prime of the form \[4k+3\]
.Suppose
\[r\]
has no prime divisors of the form \[4k+3\]
. If \[r=1\]
then \[n=m^2=m^2+0^2\]
so we are done. If \[r \gt 1\]
then \[r\]
is the product of at least one prime each of which is either 2 or of the form \[4k+1\]
. Any product of primes of this form can be expressed as a sum of two squares using Primes of Form 4k+1 as Sum of Two Squares and Primes of Form 4k+1 as Sum of Two SquaresSuppose
\[n\]
can be expressed as a sum of two squares \[n=m^2r=a^2+b^2\]
. Any common divisor of \[a\]
and \[b\]
can be cancelled by writing \[m^2r=d^2(a_1^2+b_1^2) \rightarrow ( \frac{m}{d} )^2 r =m_1^2r a_1^2+b_1^2\]
.Suppose
\[p=4k+3\]
divides \[r\]
, then \[a_1^2+b_1^2 \equiv 0 \; (mod \; p) \rightarrow a_1^2 \equiv -b_1^2 \; (mod \; p)\]
.If
\[p | a_1\]
then \[p | b_1\]
contradicting that \[gcd(a_1, b_1) =1\]
so we must have \[gcd(a_1,b_1)=1\]
and we can apply Fermat's Little Theorem.\[a_1^{p-1} \equiv b_1^{p-1} \equiv 1 \; (mod \; p)\]
\[a_1^{4k+3-1} \equiv b_1^{4k+3-1} \equiv 1 \; (mod \; p)\]
\[a_1^{4k+2} \equiv b_1^{4k+2} \equiv 1 \; (mod \; p)\]
\[(a^2_1)^{2k+1} \equiv ((-b_1)^2)^{2k+1} \equiv 1 \; (mod \; p)\]
\[ (-1)^{2k+1}(b_1^2)^{2k+1} \equiv -b_1^{p-1} \equiv - 1 \; (mod \; p)\]
This cannot possibly be true for an odd prime so we have a contradiction and the theorem is proved.
