Fermatの二平方定理

整数 $a$ が偶数なら $a=2k$ として $a^2=4k^2\equiv0\pmod4$、奇数なら $a=2k+1$ として $a^2=4(k^2+k)+1\equiv1\pmod4$ である。よって $a^2+b^2$ を $4$ で割った余りは $0+0$、$0+1$、$1+1$ のいずれか、すなわち $0,1,2$ のいずれかであり、$3$ にはならない。

$m^2\equiv-1\pmod p$ とする。$p\nmid m$ なので、Fermatの小定理により $m^{p-1}\equiv1\pmod p$ である。一方 $p-1$ は偶数なので $m^{p-1}=(m^2)^{(p-1)/2}\equiv(-1)^{(p-1)/2}\pmod p$ である。よって $(-1)^{(p-1)/2}\equiv1\pmod p$ であり、$p\geq3$ より $-1\not\equiv1\pmod p$ だから $(-1)^{(p-1)/2}=1$、すなわち $(p-1)/2$ は偶数で $p\equiv1\pmod4$ である。
逆に $p=4k+1$（$k\geq1$）とする。$\mathbb{Z}/p\mathbb{Z}$ は体であり（有限体）、体の上の次数 $d\geq1$ の多項式の根は $d$ 個以下である。したがって $x^{2k}-1$ の根は $\mathbb{Z}/p\mathbb{Z}$ に $2k$ 個以下しかなく、$2k<4k=p-1$ なので、$a^{2k}\not\equiv1\pmod p$ を満たす $a\in\{1,2,\dots,p-1\}$ がある。$m:=a^k$ とおくと、Fermat の小定理により
$$ (m^2-1)(m^2+1)=m^4-1=a^{4k}-1=a^{p-1}-1\equiv0\pmod p $$
である。$m^2-1=a^{2k}-1\not\equiv0\pmod p$ であり、$p$ は素数なので $p\mid m^2+1$、すなわち $m^2\equiv-1\pmod p$ である。

$p\equiv1\pmod4$ とし、正の整数の 3 つ組の集合
$$ S:=\{(x,y,z)\in\mathbb{Z}_{>0}^3\mid x^2+4yz=p\} $$
を考える。$S$ の元の成分はどれも $p$ 未満なので、$S$ は有限集合である。
段階 1：$S$ 上の写像 $f\colon S\to S$ を次で定める。
$$ f(x,y,z):=\begin{cases}(x+2z,\ z,\ y-x-z) & (x< y-z\ \text{のとき}),\\ (2y-x,\ y,\ x-y+z) & (y-z< x<2y\ \text{のとき}),\\ (x-2y,\ x-y+z,\ y) & (x>2y\ \text{のとき}).\end{cases} $$
境目の場合は起こらない。実際、$x=y-z$ なら $p=(y-z)^2+4yz=(y+z)^2$ は平方数になり、$x=2y$ なら $p=4y^2+4yz=4y(y+z)$ は偶数になって、どちらも $p$ が奇素数であることに反する。よって $S$ の各元はちょうど 1 つの場合に属する。
各場合の値が $S$ に属することを確かめる。第 1 の場合、$(x+2z)^2+4z(y-x-z)=x^2+4yz$ で、$y-x-z>0$ である。第 2 の場合、$(2y-x)^2+4y(x-y+z)=x^2+4yz$ で、$2y-x>0$、$x-y+z>0$ である。第 3 の場合、$(x-2y)^2+4(x-y+z)y=x^2+4yz$ で、$x-2y>0$、$x-y+z>x-2y>0$ である。
$f\circ f$ が恒等写像であることを確かめる。第 1 の場合の値 $(x',y',z')=(x+2z,z,y-x-z)$ は $x'-2y'=x>0$ を満たすので第 3 の場合に属し、$f(x',y',z')=(x'-2y',\,x'-y'+z',\,y')=(x,y,z)$ である。第 3 の場合の値 $(x',y',z')=(x-2y,\,x-y+z,\,y)$ は $y'-z'=x-2y+z>x'$ を満たすので第 1 の場合に属し、同様に計算して $f(x',y',z')=(x,y,z)$ である。第 2 の場合の値 $(x',y',z')=(2y-x,\,y,\,x-y+z)$ は $y'-z'=2y-x-z< x'<2y'$ を満たすので第 2 の場合に属し、$f(x',y',z')=(x,y,z)$ である。よって $f$ は対合である。
段階 2：$f$ の不動点を求める。第 1 の場合の値は $x'=x+2z\neq x$、第 3 の場合の値は $x'=x-2y\neq x$ なので、不動点は第 2 の場合にしかなく、$2y-x=x$、すなわち $x=y$ である。このとき $p=x^2+4xz=x(x+4z)$ で、$x+4z>1$ なので $p$ が素数であることから $x=1$、$z=(p-1)/4$ である。逆に $(1,1,(p-1)/4)$ は $S$ に属し（ここで $p\equiv1\pmod4$ を使う）、$y-z<1<2$ なので第 2 の場合に属して $f$ で動かない。したがって $f$ の不動点はちょうど 1 個である。
段階 3：対合 $f$ は、不動点でない $S$ の元を $\{s,f(s)\}$ という 2 元の組に分ける。よって $\#S$ は不動点の個数 $1$ と偶奇が一致し、奇数である。
段階 4：$g(x,y,z):=(x,z,y)$ も $S$ 上の対合である。段階 3 と同じ理由で、$g$ の不動点の個数は $\#S$ と偶奇が一致するので奇数であり、特に $0$ でない。$g$ の不動点 $(x,y,y)$ をとれば
$$ p=x^2+4y^2=x^2+(2y)^2 $$
であり、$p$ は 2 つの平方数の和である。

まず次の事実（Thue の補題）を示す：$p$ を素数、$m$ を整数、$k:=\lfloor\sqrt p\rfloor$ とするとき、$(a,b)\neq(0,0)$、$|a|\leq k$、$|b|\leq k$、$a\equiv mb\pmod p$ を満たす整数の組 $(a,b)$が存在する。
$p\equiv1\pmod4$ とし、lem-fermat-two-sq-minus-one により $m^2\equiv-1\pmod p$ となる整数 $m$ をとる。$p$ は素数なので平方数でなく、$k<\sqrt p< k+1$ である。
$0\leq u,v\leq k$ を満たす整数の組 $(u,v)$ は $(k+1)^2>p$ 個ある。それぞれの組に $u-mv$ を $p$ で割った余りを対応させると、余りは $p$ 通りしかないので、鳩の巣原理により異なる 2 組 $(u_1,v_1)\neq(u_2,v_2)$ で $u_1-mv_1\equiv u_2-mv_2\pmod p$ となるものがある。$a:=u_1-u_2$、$b:=v_1-v_2$ とおくと、$(a,b)\neq(0,0)$、$|a|\leq k$、$|b|\leq k$ であり、$a\equiv mb\pmod p$ である（これで Thue の補題が示された）。したがって
$$ a^2+b^2\equiv m^2b^2+b^2=(m^2+1)b^2\equiv0\pmod p $$
である。一方 $0< a^2+b^2\leq2k^2<2p$ なので、$p$ の倍数である $a^2+b^2$ は $p$ に等しい。

$d'$ が $a$ と $b$ の正の公約数なら $d'^2\mid p$ なので $d'=1$ であり、$\gcd(a,b)=1$ である（最大公約数）。同様に $\gcd(c,d)=1$ である。また $p$ は平方数でないので、$a,b,c,d$ はいずれも $\sqrt p$ より小さい。
$$ (ad-bc)(ad+bc)=a^2d^2-b^2c^2=a^2(c^2+d^2)-c^2(a^2+b^2)=(a^2-c^2)p $$
なので、$p$ は $ad-bc$ か $ad+bc$ を割り切る（素数の記事の補題「Euclidの補題」）。
$p\mid ad-bc$ の場合：$|ad-bc|<\sqrt p\cdot\sqrt p=p$ なので $ad=bc$ である。$a\mid bc$ と $\gcd(a,b)=1$ から $a\mid c$ であり（互いに素）、$c\mid ad$ と $\gcd(c,d)=1$ から $c\mid a$ である。よって $a=c$ で、$ad=bc$ から $b=d$ である。
$p\mid ad+bc$ の場合：$0< ad+bc<2p$ なので $ad+bc=p$ である。上の恒等式から $p^2=(ac-bd)^2+p^2$ となり、$ac=bd$ である。前の場合と同様に $a\mid d$ かつ $d\mid a$ となり、$a=d$、$b=c$ である。

まず次を示す：$q\equiv3\pmod4$ を満たす素数 $q$ が $a^2+b^2$ を割り切るならば、$q\mid a$ かつ $q\mid b$ である。実際、$q\nmid a$ なら $aa'\equiv1\pmod q$ となる整数 $a'$ があり、$a^2+b^2\equiv0$ に $a'^2$ を掛けると $(ba')^2\equiv-1\pmod q$ となって、lem-fermat-two-sq-minus-one に反する。よって $q\mid a$ であり、$q\mid b^2$ から $q\mid b$ である。
必要性を $n$ に関する強い数学的帰納法で示す。$n=a^2+b^2$ とし、$q\equiv3\pmod4$ を $n$ を割り切る素数とする。上により $q\mid a$、$q\mid b$ なので、$n':=n/q^2=(a/q)^2+(b/q)^2$ は $n$ より小さい正の整数で、2 つの平方数の和である。帰納法の仮定により $n'$ における $q$ の指数は偶数であり、$n$ における指数はそれに $2$ を足したものなので偶数である。$n$ を割り切らない $q$ については指数 $0$ で偶数である。
十分性を示す。上の恒等式により、2 つの平方数の和で書ける整数どうしの積はまた 2 つの平方数の和で書ける。$n=2^e\prod_ip_i^{f_i}\prod_jq_j^{2g_j}$（$p_i\equiv1$、$q_j\equiv3\pmod4$）とすると、$1=1^2+0^2$、$2=1^2+1^2$、$p_i$ は thm-fermat-two-sq により、$q_j^{2g_j}=(q_j^{g_j})^2+0^2$ はいずれも 2 つの平方数の和なので、$n$ もそうである。