ユークリッドの互除法 想定問題 1
2つの自然数a，bの最大公約数をgcd(a，b)と書く。互除法の割り算を行列で表して掛け合わせると，a×x＋b×y＝gcd(a，b)となる整数の組x，yを1組求めることができる。a＝91，b＝35の場合について述べた次の文の，【 】に当てはまる値の組合せとして，最も適切なものはどれか。ただし，行列は [[上の段]，[下の段]] の形で書き，(s，t) は s と t を縦に並べた列ベクトルを表す。
91 を 35 で割ると，商2，余り21 (1)
35 を 21 で割ると，商1，余り14 (2)
21 を 14 で割ると，商1，余り7 (3)
14 を 7 で割ると，商2，余り0 (4)
余りが0になったので，最大公約数は【ア】である。
商がqの割り算で（割られる数，割る数）から（割る数，余り）へ移ることは，上の段が (0，1)，下の段が (1，－q) の行列 [[0，1]，[1，－q]] を左から掛けることで表せる。(1)～(3)の行列を，あとの割り算のものほど左に置いて掛けた B ＝ [[0，1]，[1，－1]] × [[0，1]，[1，－1]] × [[0，1]，[1，－2]] ＝ [[－1，3]，[x，y]] を (91，35) に掛けると (14，7) になる。よって x＝【イ】，y＝【ウ】で，91×【イ】＋35×【ウ】＝【ア】となる。
アイウ
解説
ポイント
互除法と割り算の行列から，ax＋by＝gcd となる整数 x，y を求める問題です。
考え方と解き方
余りが0になったときの割る数が最大公約数です。行列 B の下の段 (x，y) について，91x ＋ 35y ＝ gcd が成り立ちます。
ア：式(4)で余りが0になったときの割る数は 7 なので，gcd(91，35) ＝ 7 です。14 は式(4)の割られる数，21 は式(1)の余りで，最大公約数ではありません。
イ：左の2つの行列を掛けると [[1，−1]，[−1，2]] です。これに [[0，1]，[1，−2]] を掛けると，上の段は (−1，3) で問題文と一致します。x は下の段の左の値で，2 です。
ウ：y は下の段の右の値で，−5 です。確かめ：91 × 2 ＋ 35 × (−5) ＝ 7 で，gcd と一致します。91 × (−3) ＋ 35 × 8 ＝ 7 も成り立ちますが，行列の結果とは違う組です。答えは ア 7，イ 2，ウ －5
覚えておくこと
- 余りが 0 になったときの「割る数」が最大公約数（テキスト・覚えること）
- 1回の割り算（商 q）は，(次の組) ＝ 行列 [[0，1]，[1，−q]] × (今の組) と書ける（テキスト・覚えること）
- ax＋by＝gcd を満たす x，y は1組だけではない。ただし，行列の計算結果と違う組は，問題の答えとしては誤り（テキスト・ひっかけ）
- 最後に，選んだ x，y を式に入れて gcd になるか必ず検算する（テキスト・解き方）
類似する過去問：令和6年度 基礎科目 I-2-5、令和元年度（再試験） 基礎科目 I-2-2
テキスト「ユークリッドの互除法」を読む