この記事では、「ユークリッドの互除法」についてわかりやすく解説していきます。
ユークリッドの互除法の証明や利用方法（最小公倍数、不定方程式など）も説明していきますので、ぜひこの記事を通してマスターしてくださいね。
目次
ユークリッドの互除法とは？
ユークリッドの互除法とは、\(2\) つの自然数の最大公約数を求める方法の \(1\) つです。
なんと紀元前 \(300\) 年頃には明示されており、「世界最古のアルゴリズム」としても知られています。
互除法のやり方
具体的には、「割り切れるまで、余りでお互いを割り続ける」という方法です。
- \(2\) つの自然数のうち、大きい数を小さい数で割る。
- 前の手順の除数を前の手順の余りで割る。
これを余りが \(0\) となるまで繰り返す。
余りが \(0\) のときの除数が最大公約数である。
このように、割り算を繰り返すだけで最大公約数を求められます。
互除法の裏ワザ
ユークリッドの互除法は、次のような筆算の形で簡易的に行うこともできます。
選択式など、筆記ではないテストで活用するとよいですね。
なぜ互除法が必要？
最大公約数を求める方法には、すだれ算（素因数分解）もあります。
一方、ユークリッドの互除法は、大きな数同士の最大公約数を見つけるのに適しています。
大きな数同士になると、そもそも共通因数を探し出すのが大変だからです。
例えば、次の問題ではユークリッドの互除法が適しています。
\(629\) と \(481\) の最大公約数を求めよ。
ユークリッドの互除法を使うと、
\(629 \div 481 = 1 \cdots 148\)
\(481 \div 148 = 3 \cdots 37\)
\(148 \div 37 = 4 \cdots 0\)
余りが \(0\) のとき（割り切れたとき）の除数 \(\color{red}{37}\) が、最大公約数です。
実際に両者を \(37\) で割ってみると、
\(629 \div 37 = 17\)
\(481 \div 37 = 13\)
となり、確かに \(37\) が最大公約数だとわかりますね。
すだれ算で求めようと思ったら、初めから \(37\) が共通因数であることを見つけないといけませんね。
「最大公約数」のすだれ算（素因数分解）による求め方については以下の記事で詳しく説明しています。
最大公約数とは？意味や簡単な求め方、計算問題
ユークリッドの互除法の原理【証明】
ユークリッドの互除法は、次の原理にしたがっています。
\(2\) つの自然数 \(a, b\) \((a > b)\) について、\(a\) を \(b\) で割ったときの商を \(q\)、余りを \(r\) \((\neq 0)\) とすると、「\(a\) と \(b\) の最大公約数」は、「\(b\) と \(r\) の最大公約数」に等しい。
\begin{align}\color{red}{a = bq + r \iff \gcd(a, b) = \gcd(b, r)}\end{align}
\(a\) と \(b\) の最大公約数のことを「\(\gcd(a, b)\)」と記号で表すことができます。
この原理を証明してみましょう。
\(a, b\) の最大公約数を \(G\)、\(b, r\) の最大公約数を \(g\) とすると、
\(a = Ga’\), \(b = Gb’ = gb’’\), \(r = gr’’\)
(\(a’, b’, b’’, r’’\) はそれぞれ自然数)
と表せる。
条件から、
\(\begin{align} a &= bq + r \\ &= gb’’q + gr’’ \\ &= g(b’’q + r’’) \end{align}\)
より、\(a\) は \(g\) で割り切れる。
よって、\(g\) も \(a, b\) の公約数である。
\(a, b\) の最大公約数は \(G\) であるから、
\(g \leq G\) …①
また、\(a = bq + r\) を変形して
\(\begin{align} r &= a − bq \\ &= Ga’ − Gb’q \\ &= G(a’ − b’q) \end{align}\)
より、\(r\) は \(G\) で割り切れる。
よって、\(G\) も \(b, r\) の公約数である。
\(b, r\) の最大公約数は \(g\) であるから、
\(G \leq g\) …②
①、②より、
\(G = g\)
したがって \(a\) と \(b\) の最大公約数 \(G\) と \(b\) と \(r\) の最大公約数 \(g\) は等しい。
（証明終わり）
この関係性を繰り返し用いる方法が、ユークリッドの互除法なのです。
ユークリッドの互除法の利用問題
ユークリッドの互除法は、最大公約数を求めるだけでなく、以下のことにも活用できます。
- 最小公倍数を求める
- 二元一次不定方程式の整数解を得る
それぞれについて、詳しく見てみましょう。
利用問題①「最大公約数と最小公倍数を求める」
最大公約数と最小公倍数には以下の関係があります。
\(2\) つの自然数 \(A, B\) の最大公約数が \(G\) であるとき、
\(A = Ga\), \(B = Gb\)（\(a, b\) は互いに素な自然数）と表せ、
\(A, B\) の最小公倍数 \(L\) は
\begin{align}\color{red}{L = Gab = \displaystyle \frac{AB}{G}}\end{align}
と表すことができる。
\(2\) つの自然数を最大公約数で割ったものが最小公倍数となるのですね。
そのため、ユークリッドの互除法を使って最小公倍数も求められます。
「最小公倍数」については、以下の記事で説明しています。
最小公倍数とは？求め方や計算問題をわかりやすく解説
この性質を利用して、問題を解いてみましょう。
\(2832\) と \(3776\) の最大公約数および最小公倍数を求めよ。
大きい数なので、すだれ算で共通因数を探すのは骨が折れそうです。
ユークリッドの互除法で最大公約数を求めたあと、最小公倍数を求めましょう。
ユークリッドの互除法より、
\(3776 \div 2832 = 1 \cdots 944\)
\(2832 \div 944 = 3 \cdots 0\)
よって、最大公約数は \(944\)
\(3776 \div 944 = 4\)
したがって、最小公倍数は
\(\begin{align} \frac{2832 \times 3776}{944} &= \frac{944 \times 3 \times 944 \times 4}{944} \\ &= 944 \times 3 \times 4 \\ &= 11328 \end{align}\)
答え：
最大公約数 \(\color{red}{944}\)、最小公倍数 \(\color{red}{11328}\)
利用問題②「二元一次不定方程式の整数解を求める」
ユークリッドの互除法は、二元一次不定方程式の整数解の \(1\) つを探り当てるときに活用できます。
「不定方程式」とは、方程式の数よりも未知数の数が多く、解が無数に存在する方程式です。
そのうち、未知数が \(2\) 種類で、次数が \(1\) のものを「二元一次不定方程式」といいます。
\(ax + by = c\) （\(a, b, c\) は係数）
不定方程式とは？問題の解き方を種類別にわかりやすく解説！
特に、次の特徴をもつ二元一次不定方程式で有効です。
- \(a, b\) が互いに素である
- \(a, b\) の絶対値が大きい
\(a, b\) の絶対値が小さいときは、互除法よりも直接適当な数値を代入した方が早いです。
また、「互いに素」の詳しい性質については、以下の記事で説明しています。
互いに素とは？意味や証明問題を簡単にわかりやすく解説！
互いに素な \(2\) 数の最大公約数が \(1\) であることに着目すると、\(a, b\) に対して余り \(\bf{1}\) となるまでユークリッドの互除法を使うことで特殊解を求められます。
問題を通して、使い方を見てみましょう。
\(92, 197\) と係数が大きく、適当に \(x, y\) に値を代入していくのは大変そうです。
\(92\) と \(197\) は互いに素なので、ユークリッドの互除法が活用できます。
余りが両者の最大公約数 \(1\) になるまで、互除法を使います。
\(92x + 197y = 1\) …① とする。
ユークリッドの互除法を利用して、
\(197 \div 92 = 2 \cdots 13\) …②
\(92 \div 13 = 7 \cdots 1\) …③
互除法で行った各割り算の結果を「~ = (余り)」の形の式に変形します。
②より、\(197 − 92 \times 2 = 13\) …②’
③より、\(92 − 13 \times 7 = 1\) …③’
変形できたら、後ろの式に手前の式を順番に代入して整理します。
このとき、注目している係数 \(197, 92\) が左辺に残るように変形します。
③’に②’を代入
\(92 − (197 − 92 \times 2) \times 7 = 1\)
\(92 − (197 \times 7 − 92 \times 2 \times 7) = 1\)
\(92 − 197 \times 7 + 92 \times 14 = 1\)
\(92 \times 15 + 197 \times (− 7) = 1\) …④
①と④を見比べると、同じ形になっていることがわかります。
したがって、\((x, y) = (15, −7)\) は与えられた不定方程式を満たす解の \(1\) つです。
④は①を満たすから、\((x, y) = (15, −7)\) は①の整数解の \(1\) つである。
答え： \(\color{red}{(x, y) = (15, −7)}\)
互除法の割り算、その後の式変形を一行ずつ書くのはなかなか大変です。
互除法を筆算で行い、余りを商や除数で置き換えるように変形すると簡単です。
最後に着目している係数が残れば完成です！
利用問題③「右辺が 1 以外の二元一次不定方程式」
もう \(1\) 問見てみましょう。
右辺が \(1\) 以外の場合は、まず右辺を \(1\) としたときの特殊解を求めます。
今回は筆算で互除法をやってみましょう。
\(157x − 68y = 3\) …① とおく。
\(157x − 68y = 1\) について、ユークリッドの互除法より
\(\begin{align} 1 &= 21 − 5 \times 4 \\ &= 21 − (68 − 21 \times 3) \times 4 \\ &= 21 − 68 \times 4 + 21 \times 12 \\ &= 21 \times 13 − 68 \times 4 \\ &= (157 − 68 \times 2) \times 13 − 68 \times 4 \\ &= 157 \times 13 − 68 \times 26 − 68 \times 4 \\ &= 157 \times 13 − 68 \times 30 \end{align}\)
よって
\(157 \times 13 − 68 \times 30 = 1\) …②
得られた②の式を \(3\) 倍してあげると、①を満たす整数解の \(1\) つがわかります。
②の両辺を \(3\) 倍して、
\(157 \times 39 − 68 \times 90 = 3\)
したがって、
①の整数解の \(1\) つは \((x, y) = (39, 90)\)
答え： \(\color{red}{(x, y) = (39, 90)}\)
以上で問題も終わりです。
初めは頭がこんがらがるユークリッドの互除法ですが、使いこなせるととても役に立ちます。
計算のコツをつかんで、ぜひマスターしてくださいね！