正則連分数展開とユークリッドの互除法

今回は、正則連分数展開とユークリッドの互除法に関する関係、そして、それに関連する命題の証明を解説します。

これらは、高校では扱わないような、少々発展的な内容ではありますが、主張自体は全く難しくありません。
また、難関大学の入試では、これらを背景にした問題も出題されるなど、知ってるだけでちょっとお得な場合があるかも！といったテーマです。

少し余力のある方向けのテーマにはなりますが、発展的な内容に触れたい！という方や、数学を楽しみたい方には刺さる内容になっていますので、ぜひ楽しんでいただければうれしいです。

なお、こちらのページは、正則連分数展開と、ユークリッドの互除法の知識を前提に解説しています。よくわからないよー、という方は、先にこちらのページをご覧ください。

解説

（復習）有理数の正則連分数展開

まずは簡単に、有理数の正則連分数展開について復習してみましょう。

【例題】
\(\frac{64}{11}\) を正則連分数展開せよ

【解答】

• \(64\div \textcolor{#FF0000}{11}=\textcolor{#00B050}{5}\) 余り \(\textcolor{#00B0F0}{9}\) なので、\[\frac{64}{\textcolor{#FF0000}{11}}\stackrel{\mathrm{①}}{=}\textcolor{#00B050}{5}+\frac{\textcolor{#00B0F0}{9}}{\textcolor{#FF0000}{11}}\stackrel{\mathrm{②}}{=}\textcolor{#00B050}{5}+\frac{1}{\frac{\textcolor{#FF0000}{11}}{\textcolor{#00B0F0}{9}}}\]
• \(11\div \textcolor{#FF0000}{9}=\textcolor{#00B050}{1}\) 余り \(\textcolor{#00B0F0}{2}\) なので、\[\frac{11}{\textcolor{#FF0000}{9}}\stackrel{\mathrm{①}}{=}\textcolor{#00B050}{1}+\frac{\textcolor{#00B0F0}{2}}{\textcolor{#FF0000}{9}}\stackrel{\mathrm{②}}{=}\textcolor{#00B050}{1}+\frac{1}{\frac{\textcolor{#FF0000}{9}}{\textcolor{#00B0F0}{2}}}\]
• \(9\div \textcolor{#FF0000}{2}=\textcolor{#00B050}{4}\) 余り \(\textcolor{#00B0F0}{1}\) なので、\[\frac{9}{\textcolor{#FF0000}{2}}\stackrel{\mathrm{①}}{=}\textcolor{#00B050}{4}+\frac{\textcolor{#00B0F0}{1}}{\textcolor{#FF0000}{2}}\]

したがって、

\[\begin{alignat*}{3}
64\div 11&=5+\frac{1}{\frac{11}{9}} \\
&=5+\frac{1}{1+\frac{1}{\frac{9}{2}}} \\
&=5+\frac{1}{1+\frac{1}{4+\frac{1}{2}}} \\
&=[5;1,4,2]
\end{alignat*}\]

正則連分数展開と、ユークリッドの互除法の関係

前の章の例題を、もう少し深堀してみましょう。

\(64\div \textcolor{#FF0000}{11}=\textcolor{#00B050}{5}\) 余り \(\textcolor{#00B0F0}{9}\) なので、\[\frac{64}{\textcolor{#FF0000}{11}}=\textcolor{#00B050}{5}+\frac{1}{\frac{\textcolor{#FF0000}{11}}{\textcolor{#00B0F0}{9}}}\]

としたのでした。これをもう少し一般化して、

• (分子) \(=a\)，(分母) \(=b\)
• (商) \(=q\)，(余り) \(=r\)

とすると、

\[\frac{a}{\textcolor{#FF0000}{b}}=\textcolor{#00B050}{q}+\frac{1}{\frac{\textcolor{#FF0000}{b}}{\textcolor{#00B0F0}{r}}}\]

となります。

この、左辺の \(\frac{a}{\textcolor{#FF0000}{b}}\) と、右辺の \(\frac{1}{\frac{\textcolor{#FF0000}{b}}{\textcolor{#00B0F0}{r}}}\) という形に着目すると、

【分子 \(a\) と 分母 \(b\) の議論】を、
【分母 \(b\) と 余り \(r\) の議論】にすり替えている

と言えます。

そして、このことと、【③：①②を、「余り」が \(1\) になるまで繰り返す】と合わせると、まさに、

• 有理数の正則連分数展開
• ユークリッドの互除法

が、1：1の関係になることがわかります。

先ほどの例題で見てみると、以下のように、表し方が違うだけです。

	有理数の正則連分数展開	ユークリッドの互除法
1	\[\frac{64}{\textcolor{#FF0000}{11}}=\textcolor{#00B050}{5}+\frac{1}{\frac{\textcolor{#FF0000}{11}}{\textcolor{#00B0F0}{9}}}\]	\[64= \textcolor{#FF0000}{11}\cdot\textcolor{#00B050}{5}+\textcolor{#00B0F0}{9}\]
2	\[\frac{11}{\textcolor{#FF0000}{9}}=\textcolor{#00B050}{1}+\frac{1}{\frac{\textcolor{#FF0000}{9}}{\textcolor{#00B0F0}{2}}}\]	\[11=\textcolor{#FF0000}{9}\cdot\textcolor{#00B050}{1}+\textcolor{#00B0F0}{2}\]
3	\[\frac{9}{\textcolor{#FF0000}{2}}=\textcolor{#00B050}{4}+\frac{\textcolor{#00B0F0}{1}}{\textcolor{#FF0000}{2}}\] ※余りが \(\textcolor{#00B0F0}{1}\) となったため、 操作は終了	\[9=\textcolor{#FF0000}{2}\cdot\textcolor{#00B050}{4}+\textcolor{#00B0F0}{1}\]
4	ユークリッドの互除法　 →→→ の方が、1回だけ多い	\[2=\textcolor{#FF0000}{1}\cdot\textcolor{#00B050}{2}+\textcolor{#00B0F0}{0}\] ※余りが \(\textcolor{#00B0F0}{0}\) となったため、 操作は終了

そして、この1：1であるという事実を利用すると、有理数の正則連分数展開の回数についての重要な命題が証明できます。

有理数 ⇔ 有限の連分数で表せることの証明

それでは、こちらの重要な命題を証明してみましょう。

（※）背理法（無限降下法）を用いれば、以下のようになります。

• 【ユークリッドの互除法が、無限回の操作になる場合がある】と仮定する
• 割り算の定義から、ユークリッドの互除法を繰り返す毎に、必ず余りは小さくなるため、操作によりいくらでも小さな余りを得られる
• これは、余り \(\geqq 0\) という割り算の定義に矛盾するため、【ユークリッドの互除法が、無限回の操作になる場合がある】という仮定は否定される
• したがって、ユークリッドの互除法は、高々有限回の操作で終了する

おわりに

お疲れさまでした！正則連分数展開とユークリッドの互除法に関する関係と、「有理数 ⇔ 有限の連分数で表せる」という命題を解説しました。

こちらの、「有理数 ⇔ 有限の連分数で表せる」という命題については、そのまま使う、というよりは、対偶をとった、

無理数 ⇔ 有限の連分数で表せない（連分数が無限に続く）

という形で使うことが多い気がします。

例えば、高校に入学したての数学Iで勉強する「\(\sqrt{2}\) が無理数であることを証明せよ」という問題を考えてみます。

こちらの問題は、通常は、【\(\sqrt{2}\) は有理数（既約分数）である】とおいて、互いに素の矛盾を導くと思いますが、今回証明した命題を使えば、以下のような形で証明することができます。

1. \(\sqrt{2}\) を正則連分数展開する
2. 1の結果が、無限に続く
   ※2次無理数の場合は、必ず同型が現れます
3. \(\sqrt{2}\) は有限の連分数で表せないため、無理数であることが示される（今回の命題を利用）

※詳細は、以下のページで扱っていますので、よろしければ、併せてご覧ください

このように、いろいろな命題や定理を知っていると、それだけで問題へのアプローチの幅が大きく広がることがあります。
こちらのブログでは、そのような命題・定理を、なるべく興味を持っていただけるように楽しく解説していきますので、ぜひ、今後も興味を持って学習を進めていただけるととてもうれしいです！