## Expressing Prime Numbers as Sums of Two Squares

Theorem (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.

You have no rights to post comments