## Expressing Prime Numbers as Sums of Two Squares

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.