情報・アルゴリズムのテーマ一覧へ

基礎科目・情報・アルゴリズム

ユークリッドの互除法

高校

4問H26・R1再・R5・R6

最大公約数を求める互除法の流れ図の空欄と、行列を使って ax＋by＝最大公約数 となる x, y を求める問題が出ます。

よく出る形

  • ユークリッドの互除法の流れ図で，くり返しの条件と出力する変数を選ぶ
  • 互除法の割り算を行列で表し，ax＋by＝gcd(a，b) となる整数 x，y を求める（拡張ユークリッド互除法）
  • 流れ図と拡張互除法の2型が交互に出る。同じ型どうしは文がほぼ同じで，a，b の数字だけが替わる

覚えること

  • gcd(a，b) は a と b の最大公約数，lcm(a，b) は最小公倍数
  • 互除法は「A を B で割った余り R を求め，次は B と R で同じことをくり返す」方法
  • 余りが 0 になったときの「割る数」が最大公約数
  • 流れ図では，R≠0 なら A←B，B←R としてくり返し，R＝0 になったら B を出力する
  • 1回の割り算（商 q）は，(次の組) ＝ 行列 [[0，1]，[1，−q]] × (今の組) と書ける
  • 2×2の行列の掛け算は「左の行 × 右の列」を順に掛けて足す
gcd(a，b) × lcm(a，b) ＝ a × b
  • ax＋by＝c を満たす整数 x，y があるのは，c が gcd(a，b) の倍数のときだけ
  • ax＋by＝gcd(a，b) を満たす整数の組 (x，y) は1組ではなく，いくつもある
  • 余りは割るたびに小さくなる0以上の整数なので，互除法は有限回の割り算で終わる

解き方

  • 例：48 と 18 → 48÷18＝2 余り12 → 18÷12＝1 余り6 → 12÷6＝2 余り0。最大公約数は 6
  • 手順をたどる問題は，A，B，R の表を作って1行ずつ書く
  • 行列の問題は，まず互除法で gcd を出す。これで選択肢がかなり減る
  • 例：104 と 65 → 104÷65＝1 余り39 → 65÷39＝1 余り26 → 39÷26＝1 余り13 → 26÷13＝2 余り0。gcd は 13
  • 割り算ごとの行列を，あとの割り算のものほど左に置いて掛け合わせる
  • できた行列の下の段 (x，y) が「ax＋by＝gcd」の x と y。例では 104×2＋65×(−3)＝208−195＝13
  • 最後に，選んだ x，y を式に入れて gcd になるか必ず検算する

ひっかけ

  • gcd を，余りが 0 になった割り算の「割られる数」や「余り（0）」と取り違えない
  • ax＋by＝gcd を満たす x，y は1組だけではない。ただし，行列の計算結果と違う組は，問題の答えとしては誤り
  • 「解は1組に決まる」「どの c でも解がある」のような言い切りは誤り
このテーマの想定問題を解く

想定問題：1・2・3

このテーマの過去問（このサイトに解説がある 3問）

X で共有LINE で送る

平成に出た同じテーマ（1問）

このサイトにはまだ解説がありません。年度と題だけです。