皆さんは、
\begin{eqnarray}
\displaystyle \frac{68341}{185497}
\end{eqnarray}
のような大きな数を持つ分数を約分できるでしょうか？
小さな数であれば、共通の約数を探して約分できますが、数が大きくなると一目で最大公約数を見つけるのは難しくなります。
そんなときに活躍するのが「ユークリッドの互除法」です。
ユークリッドの互除法を使えば、非常に大きな整数同士であっても効率よく最大公約数を求めることができ、分数の約分やプログラミングなどさまざまな場面で利用されています。
この記事では、
- ユークリッドの互除法による最大公約数の求め方
- 実際の計算例
- ユークリッドの互除法が成り立つ理由（証明）
について、具体例を交えながらわかりやすく解説します。
■ユークリッドの互除法の具体例
冒頭に例で出した、以下の分数を約分する方法について見ていきましょう。
\begin{eqnarray}
\displaystyle \frac{68341}{185497} \tag{1}
\end{eqnarray}
(1)の分数について、以下の手順を繰り返し適用していきます。
約分する数を求める流れ
- 分母と分子のうち、大きい方の値を小さい方の値で割り、余りの数を求める（その余りの数をAとおく）。
- 次に、分母と分子のうち小さい方の値をAで割り、余りの数を求める（その余りの数をBとおく）。
- 次に、AをBで割り、余りの数を求める（その余りの数をCとおく）。
- 上記の操作を、余りの数が0になるまで繰り返す。
- 最後の割り算で、割る数に選ばれた数が分子分母の最大公約数、つまり約分できる数である。
※ちなみに上記操作で余りが 0 にならなかった場合は、その分数は約分できない。
上記の操作を、1つずつ丁寧にやっていきましょう。
まず、(1)の分数は分母の方が分子より値が大きいため、分母の値を分子の値で割ると、
\begin{eqnarray}
\displaystyle 185497 \div 68341=2 \ \ \text{余り} \ \ \color{red}{\underset{A}{\underline{\color{black}{48815}}}} \tag{2}
\end{eqnarray}
となります。余りとして出てきた「48815」はAとおきます。
次に、分母と分子の数値を比較すると今回は分子の方が値が小さいため、分子の値をAの値で割ると、
\begin{eqnarray}
\displaystyle 68341 \div 48815=1 \ \ \text{余り} \ \ \color{red}{\underset{B}{\underline{\color{black}{19526}}}}
\end{eqnarray}
となります。余りとして出てきた「19526」はBとおきます。
次に、Aの値をBの値で割ると、
\begin{eqnarray}
\displaystyle 48815 \div 19526=2 \ \ \text{余り} \ \ \color{red}{\underset{C}{\underline{\color{black}{9763}}}}
\end{eqnarray}
となります。余りとして出てきた「9763」はCとおきます。
次に、Bの値をCの値で割ると、
\begin{eqnarray}
\displaystyle 19526 \div \color{red}{\underset{最大公約数}{\underline{\color{black}{9763}}}}=2 \ \ \text{余り} \ \ \color{red}{0} \tag{3}
\end{eqnarray}
となり、余りが0となります。つまり、(3)が最後の割り算です。
では、(3)の割り算を見て見ましょう。この割り算で割る数として使われている「9763」こそが、分母分子の最大公約数、つまり約分できる数となります。
実際に(1)の分数は「9763」で割り切れ、以下のように約分が可能です。
\begin{eqnarray}
\displaystyle \frac{68341}{185497}=\frac{7 \times \color{red}{9763}}{19 \times \color{red}{9763}}=\frac{7}{19}
\end{eqnarray}
このような手法で、分母分子の最大公約数を調べていく手法は「ユークリッドの互除法」と呼ばれています。
何故この方法が成立するのか、詳しく見ていきましょう。
■ユークリッドの互除法の証明
\(a\) を \(b\) で割った時の商を \(q\), 余りを \(r\) とします。
このとき、\(a\) と \(b\) の最大公約数は、\(b\) と \(r\) の最大公約数に等しくなる性質があります。
(2)式を例にすると、「185497」と「68341」の最大公約数は、「68341」と「48815」の最大公約数に等しくなる、ということを言っています。
この性質が、ユークリッドの互除法の本質であり、これが証明できれば、ユークリッドの互除法を証明したも同然です。
というわけで、この性質が成立することを証明していきましょう。
ユークリッドの互除法の証明
\(a\), \(b\), \(m\) をそれぞれ自然数とする。
\(a\) と \(b\) の最大公約数を \(m\) とすると、\(a\) と \(b\) は自然数 \(a'\)、\(b'\) を利用してそれぞれ
\begin{eqnarray}
\displaystyle a=a'm \tag{4} \\
\displaystyle b=b'm \tag{5}
\end{eqnarray}
と表すことができる。これを利用して、\(a\) を \(b\) で割った時の商を \(q\)、余りを \(r\) とすると、
\begin{eqnarray}
\displaystyle a=bq+r \tag{6}
\end{eqnarray}
の関係性があるので、(6)式に(4)、(5)を代入すると、
\begin{eqnarray}
\displaystyle a'm=b'mq+r \tag{7}
\end{eqnarray}
となる。この(7)式を変形すると、
\begin{eqnarray}
\displaystyle r=a'm-b'mq=m(a'-b'q) \tag{8}
\end{eqnarray}
となるため、\(r\) は \(m\) の倍数（約数）となることがわかる。
つまり、ここまでの議論で、「\(a\) と \(b\) の最大公約数を \(m\) としたとき、\(b\) と \(r\) は公約数として \(m\) を持つ」ということまでは証明できた。
しかし、「\(a\) と \(b\) の最大公約数を \(m\) としたとき、\(b\) と \(r\) は最大公約数として \(m\) を持つ」ことはまだ証明できていないため、以下の議論でこれを証明していく。
\(b\) と \(r\) が最大公約数として \(n\) を持つとすると、\(b\) と \(r\) は自然数 \(b''\)、\(r''\) を利用してそれぞれ
\begin{eqnarray}
\displaystyle b=b''n \tag{9} \\
\displaystyle r=r''n \tag{10}
\end{eqnarray}
と表すことができる。(9), (10)を(1)式に代入して整理していくと、
\begin{eqnarray}
\displaystyle a=b''nq+r''n=n(b''q+r'') \tag{11}
\end{eqnarray}
となる。つまり、「\(b\) と \(r\) の最大公約数を \(n\) としたとき、\(a\) と \(b\) は公約数として \(n\) を持つ」ことが証明できる。
ここまでの議論を整理すると、以下①、②のようになる。
① \(a\) と \(b\) の最大公約数を \(m\) としたとき、\(a\) と \(b\) と \(r\) は公約数として \(m\) を持つ
② \(b\) と \(r\) の最大公約数を \(n\) としたとき、\(a\) と \(b\) と \(r\) は公約数として \(n\) を持つ
ここで①に着目し、「\(a\) と \(b\) の公約数」の観点で \(m\) と \(n\) の大小関係を考えると、\(m\) は \(a\) と \(b\) の最大公約数であるため、
\begin{eqnarray}
\displaystyle m \geqq n \tag{12}
\end{eqnarray}
が成立する。
一方、②に着目し、「\(b\) と \(r\) の公約数」の観点で \(m\) と \(n\) の大小関係を考えると、\(n\) は \(b\) と \(r\) の最大公約数であるため、
\begin{eqnarray}
\displaystyle m \leqq n \tag{13}
\end{eqnarray}
が成立する。
①、②の両方に着目すると、(12) と (13) はどちらも満たしている必要があるため、結果として
\begin{eqnarray}
\displaystyle m = n \tag{14}
\end{eqnarray}
となる。これより、「\(a\) と \(b\) の最大公約数を \(m\) としたとき、\(b\) と \(r\) は最大公約数として \(m\) を持つ」が証明できた。
あとはこの操作を繰り返し行っていくと、先ほどの例題でわかる通り、割り算で使用する数はどんどん小さくなっていきます。
そして最終的に余りが 0 となったら、その時の割り算で使用した「割る数」が、元々の分数の分母分子の最大公約数となります。
以上が、ユークリッドの互除法の証明です。
■まとめ
今回は、ユークリッドの互除法について具体例とともに解説しました。
ユークリッドの互除法を用いることで、大きな整数同士の最大公約数を効率よく求めることができ、分数の約分やプログラミングなどさまざまな分野で活用されています。
また、
「なぜ余りを使った計算を繰り返すだけで最大公約数が求められるのか？」
という点についても、その性質を利用することで数学的に説明できることを確認しました。
一見すると単純な計算方法ですが、2000年以上前から知られている非常に美しく実用的なアルゴリズムです。
大きな数の最大公約数を求める機会があれば、ぜひユークリッドの互除法を活用してみてください。
他のおすすめ記事
面白い数学コラム