拡張ユークリッド互除法

ユークリッド互除法で最大公約数を求め，行列の計算で ax＋by＝gcd となる x，y を求める問題です。

互除法では，余りが0になった時の割る数が最大公約数です。

商が1の割り算1回は，上の段 (0，1)，下の段 (1，−1) の行列 M をかけることと同じなので，3回分は M³ で表せます。

ア：余りが0になった時の割る数は13なので，gcd(104，65)＝13 です。

• M²＝M×M：上の段 (0×0＋1×1，0×1＋1×(−1))＝(1，−1)，下の段 (1×0＋(−1)×1，1×1＋(−1)×(−1))＝(−1，2)
• M³＝M²×M：上の段 (1×0＋(−1)×1，1×1＋(−1)×(−1))＝(−1，2)，下の段 ((−1)×0＋2×1，(−1)×1＋2×(−1))＝(2，−3)
• 下の段が「13＝104×□＋65×□」の係数なので，イ＝2，ウ＝−3 です
• 確かめ：104×2＋65×(−3)＝208−195＝13 で，gcd と一致します。答えは ア 13，イ 2，ウ −3

⑤（イ −3，ウ 5）：104×(−3)＋65×5＝13 も成り立ちますが，これは M³ の下の段の値ではなく，問題の手順で出る組ではありません。

• ユークリッド互除法：大きい数を小さい数で割り，「割る数」と「余り」でくり返す。最後に割り切った数が gcd
• gcd は a×x＋b×y の形（x，y は整数）でいつも書ける。出した x，y は元の式に入れて検算する
• gcd が選択肢で分かれている時は，まず gcd で候補をしぼってから計算する