1071 mod 465 は 141。465 mod 141 は 42。141 mod 42 は 15、42 mod 15 は 12、15 mod 12 は 3、そして 12 mod 3 は 0。0 でない最後の余り 3 が最大公約数です。どの段階も同じ理由で正当化されます。a と b の両方を割り切る数は a − qb も割り切るので、組とその余りはまったく同じ約数を持つのです。ここで素因数分解は一切不要で、それが実用上の要点です。1071 がなぜ 3·357 なのかを誰も知らないうちに、3 が答えとして出てきます。
注目すべきは段階の数です。ラメは 1844 年に、整数の組に対するユークリッドの互除法の段階数が、小さいほうの十進桁数のおよそ五倍を決して超えず、最悪の場合は連続するフィボナッチ数であることを証明しました。このページの 141, 42, 15, 12, 3 が急速に縮むのはそのためで、ここにフィボナッチの隣り合わせはありません。同じ余りの表の拡張版は 3 = 1071s + 465t となる係数も与えます。数式処理システムで剰余付き割り算を行うあらゆる手続きの材料です。
答え
3
読み方
15 mod 12、0 でない最後の余りです。最初の二つのリンクは初めの段階、1071 mod 465 = 141 と 465 mod 141 = 42 です。
出典
Euclid, Elements VII.1-2 describes antanairesis — repeatedly subtracting the lesser from the greater until a common measure is reached; the remainder form used here is the same procedure written with division, and 1071 = 3²·7·17 against 465 = 3·5·31 confirms the answer the remainders give
電卓で解いてみる
これらのリンクは、この問題の数値が入力済みの状態で適切な電卓を開きます。上の行は画面に表示されるはずの内容です。ぜひ自分で確認してください。