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

$$(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 \quad (n < k)$$

以上から，

$$\begin{aligned} 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 \end{aligned}$$

となり，$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}$ に矛盾する。