ユークリッドの互除法は 1071 と 465 から、余り 141, 42, 15, 12 を経て最大公約数 3 に至る

余りが 0 になるまで余りを取ります。0 でない最後の余りが最大公約数です。

方程式と代数 · 難易度: 古典的な結果 · 更新日 2026-11-10

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

電卓で解いてみる

これらのリンクは、この問題の数値が入力済みの状態で適切な電卓を開きます。上の行は画面に表示されるはずの内容です。ぜひ自分で確認してください。

本サイトは独立した第三者のツールサイトです。Casio、Texas Instruments およびその販売代理店とは、提携・スポンサー・承認のいずれの関係もありません。機種名と製品名は各権利者の商標であり、機種を識別する目的でのみ記載しています。

本マニュアルのキー操作手順は、当サイト独自のレイアウトデータ(オンライン電卓の表示に使うものと同じデータ)と公開されている製品情報に基づいて作成しています。仕様と地域別の設定は、実機およびメーカーの最新資料で確認しています。