A prime
\[p\]
can be expressed as a sum of two squares if and only if \[p \equiv 2 \; (mod \; 4)\]
or \[p \equiv 1 \; (mod \; 4)\]
.Proof>br /> Suppose the equation
\[mp=x^2+y^2\]
such that \[1 \lt m \lt p\]
. Let \[u, \; v\]
be the least absolute residue modulo \[m\]
of \[x, \; y\]
respectively. Then\[u \equiv x \; (mod \; m), \; v \equiv y \; (mod \; m), \; - \frac{m}{2} \lt u, \; v \lt \frac{m}{2}\]
and \[u^2+v^2=x^2+y^2 \; (mod \; m)\]
.\[u, \; v\]
must satisfy \[u^2+v^2=mr\]
If
\[r=0\]
then \[u=v=0\]
so \[m\]
divides both \[x\]
and \[y\]
so \[m\]
divides \[p\]
(using \[mp=x^2+y^2\]
), which is impossible.\[1 \lt r= \frac{u^2+v^2}{m} \lt \frac{1}{m} \times (\frac{m^2+m^2}{4}) = \frac{m}{2} \lt m\]
Multiply
\[mp=x^2+y^2\]
by \[mr=u^2+v^2\]
and write as a sum of squares.\[(mp)(mr)=(x^2+y^2)(u^2+v^2)=(xu+yv)^2+(xv-yu)^2 \]
Now
\[xu+yv \equiv x^2+y^2 \equiv 0 \; (mod \; m) \rightarrow m | (xu+yv)\]
Now
\[xv-yu \equiv xy-xy \equiv 0 \; (mod \; m) \rightarrow m | (xv-yu)\]
Put
\[xu+yv=mX, \; xv-yu=mY\]
and substitute into (1), obtaining \[m^2rp=m^2X^2+m^2Y^2 \rightarrow rp=X^2+Y^2\]
.Repeating if necessary we reach
\[m=1\]
eventually.-1 is a Quadratic Residue of
\[p\]
if \[p \equiv 1 \; (mod \; 4)\]
. The congruence \[x^2 \equiv -1 \; (mod \; p)\]
has a least positive solution \[0 \lt x_1 \le p-1\]
so there exists \[m \gt 0\]
such that \[mp=x_1^1_1^2\]
which is exactly what is required since\[m=\frac{x^2+1+1^2}{p} \lt \frac{(p-1)^2+1}{p}=\frac{p^2-2(p-1)}{p}{p} \lt p\]
>br />
If this solution has \[m \gt 1\]
we cancel down to 1 as above and find a solution.