ユークリッド互除法と行列

ユークリッド互除法で最大公約数を求め，行列の掛け算で 108x＋57y＝最大公約数 となる整数 x，y を求める問題です。

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

行列の積は，左の行列の「行」と右の行列の「列」を順に掛けて足します。

ア：式(4)で余りが0になった時の割る数は 3 なので，最大公約数は 3 です。

• 右の2つの行列を先に掛けます。1行目は (0×0＋1×1，0×1＋1×(－1))＝(1，－1)，2行目は (1×0＋(－1)×1，1×1＋(－1)×(－1))＝(－1，2)
• これに左から [[0，1]，[1，－8]] を掛けます。1行目は (0×1＋1×(－1)，0×(－1)＋1×2)＝(－1，2) で，問題の値と合います

イ：2行1列は x＝1×1＋(－8)×(－1)＝1＋8＝9 です。

ウ：2行2列は y＝1×(－1)＋(－8)×2＝－1－16＝－17 です。確かめると 108×9－57×17＝972－969＝3 で合います。答えは ア 3，イ 9，ウ －17

• ユークリッド互除法：余りで割り算をくり返し，余りが0になった時の割る数が最大公約数。割られる数と取りちがえない
• 2×2行列の積：[[a，b]，[c，d]]×[[e，f]，[g，h]]＝[[ae＋bg，af＋bh]，[ce＋dg，cf＋dh]]
• 行列を3つ掛ける時は，右の2つを先に掛けてから左を掛けてよい
• 出した x，y は，ax＋by＝gcd に入れて確かめる