Fermatの二平方和定理の初等的な証明

$N = a^2 + b^2, \gcd(a, b) = 1$とおく．このとき，素数$p$は整数
\begin{align} x^2 N - a^2 p &= x^2 (a^2 + b^2) - a^2 (x^2 + y^2)\\ &= x^2 b^2 - a^2 y^2\\ &= (xb - ay)(xb + ay) \end{align}
を割り切る．よって，必要ならば$a$の符号を置き換えることにより，$p \mid xb - ay$であると仮定してよい．$xb - ay = dp$とおく．このとき, $x$は$a + dy$を割り切る．実際，これは$x \mid (a + dy)y$と同値であり，
\begin{align} (a + dy)y &= ay + dy^2\\ &= xb - dp + dy^2\\ &= xb - dx^2 \end{align}
は明らかに$x$で割り切れる．よって，$a + dy = cx$とおけば，上の等式により
\begin{align} a &= cx - dy\\ b &= cy + dx \tag{$\ast$} \end{align}
であることがわかる．ゆえに
\begin{align} N / p &= (a^2 + b^2) / (x^2 + y^2)\\ &= [(cx - dy)^2 + (cy + dx)^2] / (x^2 + y^2)\\ &= (c^2 + d^2)(x^2 + y^2) / (x^2 + y^2)\\ &= c^2 + d^2 \end{align}
だから，$N / p$は2つの平方数の和として表せる．そして ($\ast$) により，$c$と$d$は互いに素である．

2段にわけて証明する．
(第1段) 合同方程式$x^2 + y^2 \equiv 0 \pmod{p}$に整数解が存在するならば$p$は2つの平方数の和として表せることを示す．$N = x^2 + y^2, p \mid N$とする．$x, y$にそれぞれ$p$の整数倍を加えても$p \mid N$であるから, $\abs{x} < p / 2, \abs{y} < p / 2$であるとしてよい．さらに，$\gcd(x, y) = d > 1$のときは，$x, y$をそれぞれ$d$で割っても$p \mid N$なので，$\gcd(x, y) = 1$であるとしてよい．($x, y$はどちらも$p$より小さいので$d$は$p$の倍数ではない.) このとき$N < p^2 / 2$であるので，$N$の正の約数は全て$p$以下である．もし$p$が2つの互いに素な平方数の和として表せないならば，補題により$N$の$p$以外の素因数で，2つの互いに素な平方数の和として表せないものが存在する．それを$p_1$とすれば明らかに$x^2 + y^2 \equiv 0 \pmod{p_1}$である．そして，同様にして$p_2, p_3 \dotsc$を作っていくことができ，素数の真減少列$p_1 > p_2 > \cdots$ができる．しかし，素数全ての集合は下に有界なのでこれは矛盾である．ゆえに，合同方程式$x^2 + y^2 \equiv 0 \pmod{p}$が整数解をもつならば，$p$は2つの平方数の和として表すことができる．
(第2段) 合同方程式$x^2 + y^2 \equiv 0 \pmod{p}$が整数解をもつことを示す．$p \equiv 1 \pmod{4}$だから，$p = 4n + 1$とおけば，Fermatの小定理により
$$ (X^{2n} - 1)(X^{2n} + 1) = X^{4n} - 1 \equiv 0 \pmod{p} $$
が任意の$p$の倍数でない整数$X$に対して成り立つ．よって，$X^{2n} - 1 \not\equiv 0$ならば$X^{2n} + 1 \equiv 0$となって証明が完了するが，平方剰余の第一補充則によって$p \equiv 1 \pmod{4}$であるときそのような整数$X$が存在する．