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

$(x_1^2+y_1^2)(x_2^2+y_2^2)=(x_1y_2-x_2y_1)^2+(x_1x_2+y_1y_2)^2$

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

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

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

$x^2\equiv -1$ となる $\dfrac{p}{2}$ 以下の正の整数 $x$ が存在するので，例えば $y=1$ とすれば

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

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

となる $\dfrac{p}{2}$ 以下の正の整数 $k$ が存在する。

そこで，$x^2+y^2=kp$ を満たす正の整数の組 $(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$ の最小性(※)に矛盾。

ただし，以下2点の確認が必要。

1. $\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}$

2. 「$k$ は正の整数の中で最小」なので $n=0$ なら矛盾しない。つまり $n\geq 1$ の確認が必要。もし $n=0$ と仮定すると，$B=D=0$，つまり $x=Ak,y=Ck$ より $kp=(A^2+C^2)k^2$ となり $p$ は $k$ の倍数。ところが $p$ は素数であり $k\neq 1$ の仮定より $k=p$ となる。これは $k\leq\dfrac{p}{2}$ に矛盾。