フェルマーの二平方和定理

$(x_1^2+y_1^2)(x_2^2+y_2^2)=(x_1y_2-x_2y_1)^2+(x_1y_1+x_2y_2)^2$

より $m, n$ が $2$ つの平方数の和で表せるならその積も $2$ つの平方数の和で表せる。

以下 $\:\mathrm{mod}\:p$ を省略して表記する。

$p$ を $4$ で割った余りが $1$ のとき第一補充法則より

$x^2\equiv -1$ となる $x$ が存在するので例えば $y=1$ とすれば

$x^2+y^2\equiv 0$ となる $(x,y)$ が存在する。

よって $x^2+y^2=kp$

となる自然数 $k$ が存在するのでそのような組 $(x,y,k)$ の中で $k$ が最小なものをとってくる。

$k=1$ であることを背理法で示す。

$x,y$ を $k$ で割る（余りの絶対値が最小となるようにする）：

$x=Ak+B, y=Ck+D$

ただし，$B,D$ の絶対値は $\dfrac{k}{2}$ 以下。つまり $B^2+D^2$ は $\dfrac{k^2}{2}$ 以下。

このとき $x^2+y^2$ は $k$ の倍数なので $B^2+D^2$ も $k$ の倍数：

$B^2+D^2=nk, (n <k)$

以上から，

$pn=\left(\dfrac{x^2+y^2}{k}\right)\left(\dfrac{B^2+D^2}{k}\right)\\ =\left(\dfrac{xB+yD}{k}\right)^2+\left(\dfrac{xD-yB}{k}\right)^2$

となり，$np$ も平方数の和で表される(※)ので $k$ の最小性に矛盾。

（※）最後に $\dfrac{xB+yD}{k},\dfrac{xD-yB}{k}$ が整数であることが以下のように示される：

$xB+yD\equiv x^2+y^2\equiv 0\pmod{k}$

$xD-yB\equiv xy-yx\equiv 0\pmod{k}$