ユークリッドの互除法 想定問題 3

最大公約数と互除法の性質について，最も不適切な記述を選ぶ問題です。

ax ＋ by ＝ gcd(a，b) を満たす整数 x，y はありますが，1組とは限りません。

①：例えば a＝12，b＝18 では gcd ＝ 6，lcm ＝ 36 で，6 × 36 ＝ 216 ＝ 12 × 18。正しい

②：ax ＋ by はいつも gcd の倍数になり，gcd の倍数はどれも作れる。正しい

③：91 × 2 ＋ 35 × (−5) ＝ 7 も 91 × (−3) ＋ 35 × 8 ＝ 7 も成り立つ。x を 5 増やし y を 13 減らすと，ほかにも作れる。「ただ1組」は誤り

④：ax ＋ by ＝ 1 から ax − 1 ＝ −by となり，ax − 1 は b で割り切れる。正しい

⑤：余りは割るたびに小さくなり，0より小さくならないので，有限回で終わる。正しい。答えは ③

• 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以上の整数なので，互除法は有限回の割り算で終わる（テキスト・覚えること）