フェルマの二平方和定理の初等的証明

〔フェルマの二平方和定理, 直角三角形の基本定理〕
奇素数 𝒑 について, 𝒑 がある二つの平方数の和で表せることと 𝒑 が 4 で割って 1 余ることは同値である.

この記事は以下を目標として記しています.

二平方和定理に対して, 合同式論と鳩の巣原理を用いた初等的な証明を与える.

前提知識

整数部分, 合同式, 鳩の巣原理など

実験
(2) の証明
(1) の証明
補題 2 の証明
補足
演習問題

実験

まずは, $\ p=3,\ 5,\ 7,\ \ldots,\ 97\$ として具体的に確かめてみます. $\ p\$ は奇素数としていたので $\ p=2\$ は考えません. \begin{align} &3=\\ &5=1^2+2^2\\ &7=\\ &11=\\ &13=2^2+3^2\\ &17=1^2+4^2\\ &19=\\ &23=\\ &29=2^2+5^2\\ &31=\\ &37=1^2+6^2\\ &41=4^2+5^2\\ &43=\\ &47=\\ &53=2^2+7^2\\ &59=\\ &61=5^2+6^2\\ &67=\\ &71=\\ &73=3^2+8^2\\ &79=\\ &83=\\ &89=5^2+8^2\\ &97=4^2+9^2 \end{align} 空白になっている箇所はどのような $\ 2\$ つの平方数の和でも表せないということです. たとえば, $\ 3=x^2+y^2\$ を満たす整数 $\ x,y\$ の組は存在しません.

$\ p\$ は奇素数としていたので $\ {\rm mod}\ 4\$ では $\ p\equiv1\$ または $\ p\equiv3\$ のいずれかとなりますが, 上記の結果から,

$\ (1)\$ $\ p\equiv1\$ のとき, $\ p\$ は $\ 2\$ つの平方数の和で表せる.

$\ (2)\$ $\ p\equiv3\$ のとき, $\ p\$ は $\ 2\$ つの平方数の和で表せない.

が成り立つであろうという予想を立てることができます. 以下では, $\ (1)\$ と $\ (2)\$ のそれぞれについて, 初等的な証明を紹介したいと思います.

(2) の証明

こちらは簡単です. いわゆる平方剰余というものに着目します.

定理 1 素数 $\ p\$ が $\ p\equiv3\ \ ({\rm mod}\ 4)\$ を満たすとき, $\ p\$ は $\ 2\$ つの平方数の和で書き表せない.

証明. ある整数 $\ n\$ を $\ 4\$ で割ったときの余りは $\ 0,1,2,3\$ の $\ 4\$ 通りであるが, \begin{align} &0^2=0\equiv0\ \ ({\rm mod}\ 4)\\ &1^2=1\equiv1\ \ ({\rm mod}\ 4)\\ &2^2=4\equiv0\ \ ({\rm mod}\ 4)\\ &3^2=9\equiv1\ \ ({\rm mod}\ 4) \end{align} より $\ n^2\$ を $\ 4\$ で割ったとときの余りは $\ 0,1\$ 以外にありえない. もし $\ p=x^2+y^2\$ を満たす整数 $\ x,y\$ が存在していたと仮定すると, $\ x^2,\ y^2\$ を $\ 4\$ で割った余りは $\ 0\$ または $\ 1\$ であることから \begin{align} &p\equiv0+0\equiv0\ \ ({\rm mod}\ 4)\\ &p\equiv1+0\equiv1\ \ ({\rm mod}\ 4)\\ &p\equiv0+1\equiv1\ \ ({\rm mod}\ 4)\\ &p\equiv1+1\equiv2\ \ ({\rm mod}\ 4) \end{align} のいずれかになり, $\ p\equiv3\ \ ({\rm mod}\ 4)\$ では不適である.

$\Box$

(1) の証明

$\ (1)\$ の証明には少しテクニカルな方法が必要です. 無限降下法を用いる証明方法が有名かもしれませんが, ここでは鳩の巣原理を利用して証明します.

補題 2 $\ p\$ が $\ p\equiv1\ \ ({\rm mod}\ 4)\$ を満たす素数であるとき, 合同方程式 \begin{align} x^2\equiv-1\ \ ({\rm mod}\ p) \end{align} は $\ 0\le x\lt p\$ の範囲に解を持つ.

たとえば $\ p=5\$ のとき, \begin{align} &2^2=4\equiv-1\ \ ({\rm mod}\ 5)\\ &3^2=9\equiv-1\ \ ({\rm mod}\ 5) \end{align} なので $\ x=2,3\$ が解になります.

この補題は議論の途中で必要になるものです. この補題の証明は次の項で扱います.

定理 3 素数 $\ p\$ が $\ p\equiv1\ \ ({\rm mod}\ 4)\$ を満たすとき, $\ p\$ はある $\ 2\$ つの平方数の和で表せる.

証明. $\ (x,y)\$ 平面上で, $\ 0\le x\le \sqrt{p},\ 0\le y\le \sqrt{p}\$ で表現される正方形型の領域 $\ \mathcal{D}\$ を考える.

このような領域を考える理由は後々わかります*1.

ここで次の事実を確認する.

事実. 領域 $\ \mathcal{D}\$ に含まれる格子点は $\ p\$ 個よりも多い.

図より, 格子点の個数を数えると $\ (\lfloor\sqrt{p}\rfloor+1)^2\$ 個である. ただし, $\ \lfloor\sqrt{p}\rfloor\$ で $\ \sqrt{p}\$ の整数部分を表している. このとき \begin{align} (\lfloor\sqrt{p}\rfloor+1)^2\gt(\sqrt{p}-1+1)^2=p \end{align}より格子点の数は $\ p\$ 個よりも多いことがわかる.

ここで補題 2 より $\ x^2\equiv-1\ \ ({\rm mod}\ p)\$ を満たす整数 $\ x\ \ (0\le x\lt p)\$ が存在するので, その解のうちの $\ 1\$ つを $\ r\$ とおく.

このような整数 $\ r\$ を使うと都合が良い理由は後々わかります.

領域 $\ \mathcal{D}\$ に含まれる格子点 $\ (x,y)\$ のそれぞれに対し, 「 $\ x+yr\$ を $\ p\$ で割った余り」を考えると, これらは $\ 0,1,2,\ldots,p-1\$ の $\ p\$ 個の値以外をとらない. ところが, 事実より格子点の数は $\ p\$ 個を上回るので, 「 $\ x+yr\$ を $\ p\$ で割った余り」が等しいような $\ 2\$ つの格子点が存在する.

ここで鳩の巣原理を使いました. $\ p\$ 個よりも多い「 $\ x+yr\$ を $\ p\$ で割った余り」という鳩が, $\ p\$ 個の巣 \begin{align} 0,1,2,\ldots,p-1 \end{align} に割り振られるので, その中には同じ巣に入るような鳩が, 少なくとも $\ 1\$ 組はいるはずです.

つまり, $\ \mathcal{D}\$ に含まれる $\ 2\$ つの異なる格子点 $\ (x_1,y_1),\ (x_2,y_2)\$ であって, \begin{align} x_1+y_1r&\equiv x_2+y_2r\ \ ({\rm mod}\ p)\\ (x_1-x_2)+(y_1-y_2)r&\equiv0\ \ ({\rm mod}\ p) \end{align} を満たすようなものが存在する. $\ x_1-x_2=X,\ y_1-y_2=Y\$ とおくと $\ X+Yr\equiv0\ \ ({\rm mod}\ p)\$ となり, 両辺に $\ X-Yr\$ をかけると \begin{align} X^2-Y^2r^2&\equiv0\ \ ({\rm mod}\ p)\\ X^2+Y^2&\equiv0\ \ ({\rm mod}\ p) \end{align} となるので $\ X^2+Y^2\$ は $\ p\$ の倍数である.

これでほとんど証明は完了しました. あとは $\ X^2+Y^2=p\$ を示せばよいですが, 領域 $\ \mathcal{D}\$ の点をとって考えていたことから, $\ X^2+Y^2\$ の値の範囲を絞り込んで限定することができます.

加えて, $\ (x_1,y_1),\ (x_2,y_2)\$ は $\ \mathcal{D}\$ に含まれる格子点としていたから \begin{align} &X^2=(x_1-x_2)^2\lt\sqrt{p}^2=p\\ &Y^2=(y_1-y_2)^2\lt\sqrt{p}^2=p \end{align} より $\ X^2+Y^2\lt2p\$ がいえる. また $\ (x_1,y_1),\ (x_2,y_2)\$ は異なる $\ 2\$ 点としていたから $\ X,Y\$ がともに $\ 0\$ であることはない. よって \begin{align} 0\lt X^2+Y^2\lt2p \end{align} が成り立つが, この範囲にある $\ p\$ の倍数は $\ p\$ のみなので $\ X^2+Y^2=p.\$ すなわち, $\ p\$ を $\ 2\$ つの平方数の和で表すことができた.

$\Box$

補題 2 の証明

最後に, 前の項で仮定した補題 2 の証明に入ります.

補題 4 $\ p\$ を素数, $\ a,b\$ を整数とする. $\ a\$ が $\ p\$ で割り切れないならば, 合同方程式 \begin{align} ax\equiv b\ \ ({\rm mod}\ p) \end{align} は $\ 0\le x\lt p\$ の範囲にただ $\ 1\$ つの解を持つ.

証明. $\ p\$ 個の数 \begin{align} 0a,\ 1a,\ 2a,\ 3a,\ \ldots,\ (p-1)a \end{align} を考え, これらが $\ {\rm mod}\ p\$ においてすべて異なる値をとることを示す. もし $\ sa\$ と $\ ta\$ $(0\le s\lt t\lt p)\$ が $\ {\rm mod}\ p\$ において合同であったとすると, その差 $\ ta-sa=(t-s)a\$ は $\ p\$ の倍数になるが, $\ a\$ は仮定より $\ p\$ で割り切れず, また $\ 0\lt t-s\lt p\$ より $\ t-s\$ も $\ p\$ の倍数になりえないので矛盾. よって, $\ p\$ 個の数 \begin{align} 0a,\ 1a,\ 2a,\ 3a,\ \ldots,\ (p-1)a \end{align} を $\ p\$ で割った余りを並べれば, $\ 0\$ から $\ p-1\$ までのすべてが現れる. その中にただ $\ 1\$ つだけ存在する, $\ b\$ と合同なものを $\ xa\$ とおけば, $\ xa\equiv b\ \ ({\rm mod}\ p)\$ となる.

$\Box$

以降, このような $\ x\$ を「（ $\ {\rm mod}\ p\$ における） $\ a\$ の $\ b$ -ペア」と呼ぶことにします.

補題 5 素数 $\ p\$ に対し $\ (p-1)!\equiv-1\ \ ({\rm mod}\ p).\$

$\ p=2,3,5,7\$ を代入すると \begin{align} &1!\equiv-1\ \ ({\rm mod}\ 2)\\ &2!\equiv-1\ \ ({\rm mod}\ 3)\\ &4!\equiv-1\ \ ({\rm mod}\ 5)\\ &6!\equiv-1\ \ ({\rm mod}\ 7) \end{align} となって, 確かに成り立っています. $\ p\$ がこれくらい小さな値であれば $\ (p-1)!\$ を計算してから $\ p\$ で割った余りを考えてもよいのですが, たとえば $\ p=11\$ の場合, $\ 10!\$ を計算すると大きな値になってしまうので, 次のように工夫します. \begin{align} 10!&=1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10\\ &=1\cdot(2\cdot6)\cdot(3\cdot4)\cdot(5\cdot9)\cdot(7\cdot8)\cdot10\\ &\equiv1\cdot1\cdot1\cdot1\cdot1\cdot(-1)\ \ ({\rm mod}\ 11)\\ &\equiv-1\ \ ({\rm mod}\ 11). \end{align} つまり, それぞれの因数をその $\ 1$ -ペアと組にして, $\ 1\$ にしてしまうということです. ただし, $\ 1\$ と $\ 10\$ だけは $\ 1$ -ペアが自分自身になるので, 分けて考える必要があります. 一般の $\ p\$ についても全く同様です.

証明. $\ (p-1)!\$ の $\ 1,\ p-1\$ 以外の各因数を, その $\ 1$ -ペアと組にして計算すると \begin{align} (p-1)!\equiv1\cdot1\cdot1\cdot\cdots\cdot1\cdot(p-1)\equiv-1\ \ ({\rm mod}\ p) \end{align} となる. ただし, $\ 2,3,\ldots,p-2\$ のそれぞれに唯一の $\ 1$ -ペアが存在することは補題 4 からしたがう.

$\Box$

これで準備は完了です.

証明. $\ p\$ が奇素数であることを前提とし, 対偶をとって

$\ x^2\equiv-1\ \ ({\rm mod}\ p)\$ が解を持たないならば $\ p\equiv3\ \ ({\rm mod}\ 4)\$

を証明する. そのために, $\ (p-1)!\$ を $\ p\$ で割った余りについて考える.

補題 5 より, $\ (p-1)!\$ を $\ 1$ -ペアごとに組にして計算すると $\ -1\$ に合同になることがわかりました. 今度は $\ (p-1)!\$ の各因数を $\ -1$ -ペアごとに組にして計算してみます.

補題 4 より, $\ {\rm mod}\ p\$ において $\ 1,2,\ldots,p-1\$ はそれぞれ唯一の $\ -1$ -ペアを持ち, また $\ x^2\equiv-1\ \ ({\rm mod}\ p)\$ となるような $\ x\$ が存在しないことから $\ -1$ -ペアが自分自身になるものはない. よって \begin{align} (p-1)!\equiv(-1)^{\frac{p-1}{2}}\ \ ({\rm mod}\ p). \end{align} 補題 5 の結果と合わせると $\ (-1)^{\frac{p-1}{2}}\equiv-1\ \ ({\rm mod}\ p)\$ となるが, $\ p\neq1,2\$ より $\ 1\equiv-1\ \ ({\rm mod}\ p)\$ が成り立つことはないので $\ (-1)^{\frac{p-1}{2}}=-1\$ がいえる. これは $\ \dfrac{p-1}{2}\$ が奇数であること, すなわち $\ p\equiv3\ \ ({\rm mod}\ 4)\$ であることを表している. したがって対偶が示されたので, もとの命題も真である.

$\Box$

補足

実は, 補題 5 および補題 6 の逆もそれぞれ成り立つことが知られています.

定理 6（ウィルソンの定理） 整数 $\ p\ge2\$ に対し, $\ p\$ が素数 $\ \Longleftrightarrow\ (p-1)!\equiv-1\ \ ({\rm mod}\ p).\$

定理 7（平方剰余の第一補充則） 奇素数 $\ p\$ に対し, 合同方程式 \begin{align} x^2\equiv-1\ \ ({\rm mod}\ p) \end{align} が解を持つために必要かつ十分な条件は, $\ p\equiv1\ \ ({\rm mod}\ 4)\$ が成り立つことである.

定理 6 の（ $\Longleftarrow$ ）の証明はあまり難しくありません. 定理 7 の必要性（ $\Longrightarrow$ ）については, 十分性の証明のときとほとんど同じですが, $\ -1$ -ペアが自分自身になるようなものがあるという点で少し厄介なので補填しなければなりません. これらの証明の詳細については省略しますので, 考えてみてください.

演習問題

問. 以下の命題を示せ.

$\ (1)\$ $\ a,b\$ を互いに素な整数とするとき, $\ a^2+b^2\$ は $\ 4\$ で割って $\ 3\$ 余る素因数を持たない.

$\ (2)\$ $\ 8\$ で割って $\ 5\$ 余る素数は無数に存在する.

問. 以下の命題を示せ.

$\ (1)\$ 整数 $\ n\ge2\$ が $\ 2\$ つの平方数の和で表せるために必要かつ十分な条件は, $\ n\$ を素因数分解したときに $\ 4\$ で割って $\ 3\$ 余る素因数の冪指数がすべて偶数であることである.

$\ (2)\$ 整数 $\ n\ge2\$ が $\ 2\$ つの三角数の和で表せるために必要かつ十分な条件は, $\ 4n+1\$ を素因数分解したときに $\ 4\$ で割って $\ 3\$ 余る素因数の冪指数がすべて偶数であることである. ただし三角数には $\ 0\$ を含めて考えるものとする.

*1:以降に示す事実を満たすような広さの領域で, かつ後の $\ X^2+Y^2\$ の値の範囲をうまく限定できるような狭さの領域であるから, ということが理由です.

Arithmetica

フィボナッチ数と平方数, 記数法.

フェルマの二平方和定理の初等的証明

実験

(2) の証明

(1) の証明

補題 2 の証明

補足

演習問題