ユークリッドの互除法
のとき 。割り算をくり返して最大公約数を求める。
つの正の整数 ()の最大公約数 は、 を で割った余り を使って、より小さい組の最大公約数 に置きかえられるよ。これを「余りが になるまで」くり返すと、最後に割り切れたときの「割る数」(=最後の でない余り)がそのまま最大公約数になる。たとえば は から に、 で割り切れて答えは 。素因数分解をしなくても最大公約数が速く求まる。これがいちばんの値打ちだね。
は正の整数。 を で割った商 と余り は 、 で決まる。割るたびに余り は前の割る数より必ず小さくなるので、操作は有限回で必ず終わる(余りはいつか になる)。図では の長方形を「入るかぎり大きい正方形」で順にしきつめることが、この割り算のくり返しに対応するよ。
から「 の公約数の集合」と「 の公約数の集合」がぴったり一致することを示す。集合が同じなら最大公約数も同じ。
を で割った商を 、余りを とするよ。下の式のように移項すれば、余り は と で表せる。この つの見方を行き来して、公約数が移り合うことを見ていこう。
と の公約数 を考えると、 は も も割るから、その差 も割る。つまり の公約数は、そのまま の公約数でもあるんだ()。
逆に と の公約数 なら、 は も も割るから、 も割る。つまり の公約数は、そのまま の公約数でもある()。
両方向が言えたので「 の公約数」と「 の公約数」は完全に同じ集合。だから最大公約数も等しい(下の式)。組を小さくしながらこれをくり返し、余りが になって で割り切れたとき、その割る数 が最大公約数だよ。
最大公約数そのものに「逆」は無いけれど、互除法は逆向きにもたどれる。 のとき、割り算の式を下からさかのぼって代入していくと、 を満たす整数 を作れる(一次不定方程式の解法・拡張ユークリッドの互除法)。「最大公約数を求める道具」が、そのまま「 を解く道具」にもなるんだ。
つまずきやすいのは答えの読み方。最大公約数は「余りが になった割り算の割る数」=最後の でない余り、であって「最後の余り 」ではないよ。また で組がどんどん小さくなるのがしくみの心臓部。図で「最後にしきつめた正方形の一辺」が最大公約数になるのと同じことだね。
言葉で読んだら、動くアニメと自分の手で確かめてみよう。
この定理が、実際の問題でどう効くのかを見てみよう。