ユークリッドの互除法計算

a = q * b + r、gcd(a, b) = gcd(b, r)。r = 0になるまで繰り返すと、そのときのbが答え

a = q * b + r

アルゴリズムの1段を等式で書いたものです。aはその段の2つの数のうち大きいほう、bが小さいほう、qはbがaの中に何回ちょうど入るか、rはその残りです。このページの計算の手順の記法がこれそのもので、1,071 = 2 × 462 + 147が1段にあたります

a, b

比べている2つの数です。役割は毎段入れ替わります。ある段のbが次の段のaになり、rが新しいbになります。入力欄の名前が割られる数と割る数ではないのはこのためです。1段目では1,071が割られる数ですが、2段目では462がそうなり、1つの段にしか当てはまらない名前はほかの段で嘘になります

q

商、つまりbがaの中に何回ちょうど入るかです。組を先に大きい順へ並べるので、いつでも1以上になります。ここでq = 0が一度も出てこない理由も同じです。qが目立たないのは最後の段だけで、そこでは余りが0になり、割り算が割り切れます

r

余りで、いつもbより小さく、負にはなりません。アルゴリズムの停止規則はr = 0で、それは省略されず最後の段として印字されます。147 = 7 × 21 + 0が、探索が終わって21が答えだと告げる行です

gcd(a, b)

最大公約数、つまりaとbの両方を割り切る最大の整数です。答えは最終段のbをそのまま取り出したもので、計算し直したものではありません。1,071と462では21で、1,071 = 21 × 51、462 = 21 × 22となり、これより大きい数はどちらも割り切りません

610 = 1 * 377 + 233

最悪の場合の最初の段で、連続するフィボナッチ数です。ここでは商がすべて1で、数はほとんど減りません。13段かかるのはそのためです。ラメの定理は、この大きさの組でこれより多くの段を要するものはないと述べています

約分が日常的な用途です。462と1,071の分数をこれ以上簡単にできない形で書くには、2つの最大公約数が要ります。このページはその数と根拠を同時に渡します。21という数と、それを生んだ3段です。上下を21で割ると22/51になり、印字された手順があれば約分を信じるのではなく確かめられます。比を簡単にしたい場面はほかにもあります。歯車の比、画面の縦横比、縮尺図、そして2つの数を並べるのではなく1つの割合として表したいあらゆる測定です。2つ目はコードと授業で、ここではこのアルゴリズムが最初の面白い例として教えられます。必ず止まり、速く、正しい理由が1本の等式の中に見えています。剰余逆数の標準的な計算法でもあり、拡張版は同じ段に数を2つ余分に載せて運びます。RSA鍵の生成の中身がそれです。3つ目は素因数分解の手間を見積もる検算です。1,071が3 × 357、462が2 × 3 × 7 × 11だと突き止めるのは手間ですが、最大公約数が21だと分かるのは3回の割り算です。先にこのページを走らせておけば、約分が楽かどうかが始める前に分かります。答えだけで手順が要らないときは、最大公約数計算が同じ問いを短い形で聞き、3つ以上の数も一度に扱います。最小公倍数計算はlcm = (a / gcd) * bとしてこの約数から最小公倍数を出し、余りの計算は数が負になりうる場合の余りの流儀を扱います。このページでは数が負になることはありません。

1. 教科書の定番の組：1,071と462

   1. 462は1,071の中に何回入るかを調べる。2回で、2 × 462 = 924、残りは1,071 − 924 = 147
   2. 次は462と147の組。147は462の中に3回入り、3 × 147 = 441、残りは21
   3. 次は147と21の組。21は147をちょうど7回割り切り、残りは0
   4. 余りが0になったので止める。答えは21

   初期値で、このアルゴリズムがふつう導入されるときの例そのものです。結果には2つの確認が効きます。両方を21で割ると51と22になり、この2つは共通の約数を持ちません。それこそが21をただの公約数ではなく最大にしている理由です。そしてここには素因数分解が一度も出てきません。1,071の約数を試し割りで求めるなら32まで試すことになりますが、この手順はすでに手元にある数で割るだけですみます。3段で、しかも1段ごとに前の段より軽くなります。

2. 1段で足りる：12と60

   1. 組を大きい順に並べる。60が先、12が後
   2. 60 = 5 × 12 + 0なので、12は60をちょうど割り切る
   3. 余りがすぐ0になったので、アルゴリズムは1段で止まる
   4. 答えは12。2つのうち小さいほうで、それが大きいほうを割り切るから

   考えられる最短の実行で、最後の段をなぜ省かずに印字するのかが分かる場合です。60 = 5 × 12 + 0の行が答えそのものです。余りが0に達した、つまりこのアルゴリズムが止まる唯一の理由が書いてあります。この行を落とすと手順は空になり、読者は1段で終わった答えと、そもそも動いていないページを区別できません。一方の数が他方をちょうど割り切るときは、最大公約数はいつでも小さいほうの数です。

3. 互いに素な数：9と20

   1. 20 = 2 × 9 + 2なので、組は9と2になる
   2. 9 = 4 × 2 + 1なので、組は2と1になる
   3. 2 = 2 × 1 + 0なので、アルゴリズムは止まる
   4. 答えは1。9と20は1より大きい共通の約数を持たない

   最大公約数が1というのは失敗ではなくれっきとした答えで、名前も付いています。互いに素です。分数9/20がすでに約分できない形だという印でもあります。段が途中でまとまらなかったことにも注目してください。どちらの数も他方をちょうど割り切らないので、3段かけて1まで降りました。数が大きくなるほど互いに素な組がふつうになります。無作為に選んだ2つの数が約数を共有する確率はすぐに下がります。暗号で剰余逆数を組み立てるときにこの方法が役に立つのは、まさにそのためです。

2つの数はどちらも整数で、どちらも1から1,000,000の間でなければなりません。0は特別扱いではなく拒否します。aと0の最大公約数はaで、これはれっきとした答えですが、このページでは示せません。最初の段がa = q * 0 + rになり、そのqが存在しないからです。穴の空いた手順を印字するより、入力を断ります。負の数も同じ理由で拒否します。印字される手順は2つの数がどちらも1以上であることを前提にしていて、負の数が入ると商と余りが何を意味するかの規則が必要になりますが、それはこのページのどこにも書いていません。上限の1,000,000はアルゴリズムの都合ではありません。もっと大きな数でも平気で動きます。途中の引き算・掛け算・余りがふつうの倍精度演算で正確に収まり、印字される手順が読めない長さにならないようにするための上限です。それでも小さめの2つの数が多くの段を生むことはあります。610と377は13段です。ただし実際にはこの上限が段数を抑えていて、参考表に段数の列があるのでその変わり方を見られます。手順は等式として、つまりa = q * b + rをセミコロンでつないだ形で印字され、筆算では出てきません。見慣れた割り算の括弧を期待していると、このページはそれを与えません。入力は入れ替えても同じです。始める前に大きい順へ並べ替えるので、3 = 0 * 5 + 3がどんな形になるかをこのページで見ることはできません。その段が作られないからです。数が負になりうる場合や、余りの流儀を明記してほしい場合は、余りの計算がその問いのためのページです。

最大公約数とは一言でいうと何か

2つの数をどちらも余りなく割り切る最大の整数です。1,071と462なら21で、1,071 = 21 × 51、462 = 21 × 22となり、51と22は共通の約数を持ちません。だから21は最大なのです。3と7も両方を割り切ることに注意してください。それらは公約数ですが、最大ではありません。このページの主役の出力はいつでもこの数で、下の手順はその根拠です。

最後の段がいつも余り0で終わるのはなぜか

余りが0になることが、このアルゴリズムを止める唯一の理由だからです。ループは組をより小さい組（2番目の数と余り）に置き換え、数は毎段下がるので、いつか必ず0に届きます。147 = 7 × 21 + 0がその瞬間の段で、最大公約数はその段の割る数、21です。このページがそれを隠さず印字するのは、最後の0でない余りで手順を打ち切ると、読者がもう終わったと自分で気づかなければならなくなるからです。

2つの数を入力する順番は関係あるのか

いいえ。このページは最初の段の前に大きい順へ並べ替えるので、462と1,071は1,071と462とまったく同じ3行を返します。これはアルゴリズムの性質ではなくこのページの選択です。規則gcd(a, b) = gcd(b, a)により、どちらの順でも正しい答えが出ます。ただし並べ替えがないと、3と5の組の1行目が3 = 0 * 5 + 3になり、これは合法な割り算ですが、小さい数を大きい数で割ることが手順の一部であるかのように読めてしまいます。入力欄の名前が割られる数と割る数ではなく1番目の数と2番目の数なのも同じ理由です。その2つの役割は毎段入れ替わります。

答えが1になるのはどういう意味か

2つの数が1より大きい共通の約数を持たないということで、失敗ではなく完全な答えです。そのような数を互いに素といい、このページの9と20がその例です。実用的なことも分かります。分数9/20はすでに約分できない形なので、これ以上簡単にできません。数が大きくなるほど互いに素な組がふつうになっていくので、この方法は暗号で重要になります。RSA鍵の組み立ては、与えられた数と共通の約数を持たない数を見つけることだからです。

数が大きいほど段数は増えるのか

いいえ。下の参考表がそれを具体的に示しています。1,000,000と999,998は2段で終わり、3桁どうしの610と377は13段かかります。段数を増やすのは大きさではなく、数がどれだけゆっくり小さくなるかです。最もゆっくり縮む組が連続するフィボナッチ数で、そこではどの段の余りも割る数に近い値になります。それがラメの定理で、段数は桁数とともにしか増えないという上限を与えます。だからこのアルゴリズムは速いとされるのです。

2つの数を素因数分解するのとは何が違うのか

素因数分解はずっと手間がかかり、しかもこのページはそれを一度もしません。1,071を試し割りで分解するには平方根のあたり、およそ32まで約数を試すことになりますが、このアルゴリズムはすでに手元にある数で割るだけで、3段で終わります。この程度の数では差が見えませんが、数が大きくなると素因数分解は急に難しくなり、互除法はほとんど影響を受けません。その差がこの方法が今も教えられている理由そのもので、上の答えが2回目の計算ではなくループから出ている理由でもあります。両方走らせると、手順に出てくる最後の余りと、その上に印字された数が食い違う危険があります。

• Euclidean Algorithm — 漸化式gcd(a, b) = gcd(b, a mod b)、それが停止することの証明、連分数とのつながり — Wolfram MathWorld (United States)
• Greatest Common Divisor — 最大公約数とは何か、そしてgcd(a, 0) = aがなぜアルゴリズムの終着点になるのか — Wolfram MathWorld (United States)
• Lamé's Theorem — その大きさの割に最も多くの段を要する組は、いつでも連続するフィボナッチ数の組だという結果 — Wolfram MathWorld (United States)
• 学習指導要領（平成29・30・31年改訂） — 算数・数学の「数と計算」領域における最大公約数と、その求め方としての互除法の位置づけの根拠になる文部科学省の告示・解説 — 文部科学省