ユークリッドの互除法

イントロ

余りを次へ渡すアルゴリズム

列挙せずに最大公約数を求める

大きな二数の約数をすべて並べるのは大変です。ユークリッドの互除法では、割り算で生まれた余りを次の割る数にし、同じ操作を繰り返して最大公約数へ到達します。誰が行っても同じ手順になるアルゴリズムの例で、長さを共通の単位で測り切る活動にもつながります。

定義

教科書では: 大きい数を小さい数で割り、次に小さい数をその余りで割る操作を、余りが0になるまで繰り返す方法です。
言いかえると: 最大公約数は、二数を割った余りにも受け継がれます。aとbの両方を割る数はa−bqも割るため、余りrも割れます。逆向きにもa=bq+rから同じことがいえます。そのため二数を「小さい数と余り」へ置き換えても最大公約数は変わらず、余りが小さくなるので手順は必ず終わります。

公式

大きい数を、割る数の整数倍と余りに分けます。

割り算の形

a=bq+r

aをbで割った商をq、0以上b未満の余りをrと表します。この範囲の余りは一つに決まります。

使うときのコツ

次の行ではbを割られる数、rを割る数にします。商qは次の二数へ引き継ぎません。

解くコツ

各行で式が成り立つか掛け算と足し算で確かめ、余りを丸で囲んで次の行の右側へ移すと順番を崩しません。

手順

例

場面: 252と105の最大公約数を、互除法で求める。
順に考えると: まず252=105×2+42。次は105=42×2+21、さらに42=21×2+0です。余りが0になったので終了します。0になる直前の余り21が最大公約数です。実際に252÷21=12、105÷21=5で両方を割り切れます。42も共通約数候補に見えますが、105を割り切らないため答えではありません。
ここが結論: 最大公約数は21です。各行の等式と、最後に元の二数を割り切ることの二段階で検算できます。約数の全列挙をしなくても、同じ短い手順で大きな整数まで扱えます。

注意

確認

Q1

252=105×2+42の次に行う割り算はどれですか。

まとめ

桁ごとの重みで数を表す位取り記数法と、量のない位を保って位置を正確に伝える0の役割を理解します。