令和元年度(再試験) I-2-2

解説

この問題で問われていること

ユークリッドの互除法でgcd(108,57)を求め、互除法の各ステップを表す行列の積Aから、ax+by=gcd(a,b)を満たす整数x、yを求める空欄補充問題。

解き方

① 互除法で最後に割り切った数(余り0の直前の割る数)が最大公約数。x・y は行列の積をそのまま計算して読む
② gcd=3 で④⑤。[[0,1],[1,−1]]² = [[1,−1],[−1,2]]、これに左から[[0,1],[1,−8]]を掛けると2行目 = [1+8, −1−16] = [9, −17]。検算 108×9+57×(−17)=972−969=3
③ 3・9・−17(④)

正解が正しい理由

互除法の各式より、108=57×1+51、57=51×1+6、51=6×8+3、6=3×2+0であり、余りが0になる直前の値が最大公約数なのでgcd(108,57)=3(ア)。次にA=[[0,1],[1,−8]]·[[0,1],[1,−1]]·[[0,1],[1,−1]]を計算する。後ろの2つの積は[[0,1],[1,−1]]·[[0,1],[1,−1]]=[[1,−1],[−1,2]]。これに左から[[0,1],[1,−8]]を掛けると、1行目は[−1,2]、2行目は[1×1+(−8)(−1), 1×(−1)+(−8)×2]=[9,−17]となる。よってx=9(イ)、y=−17(ウ)。実際、108×9+57×(−17)=972−969=3=gcd(108,57)を満たす。したがってア=3、イ=9、ウ=−17の④が正しい。

各選択肢について

• ① アが「6」となっている点が誤り。6は互除法の途中の余りであり、最後に割り切れる直前の余りである3が最大公約数である。
• ② アが「6」となっている点が誤り。gcd(108,57)=3であり、6は最大公約数ではない(57は6で割り切れない)。
• ③ アが「6」となっている点が誤り。108と57はどちらも6の倍数ではなく(57=6×9+3)、共通の約数は3が最大である。
• ④ ア=3、イ=9、ウ=−17であり、108×9+57×(−17)=972−969=3となって式を満たしており、これが正答。
• ⑤ ア=3は正しいが、イ=−10、ウ=19としている点が誤り。108×(−10)+57×19=−1080+1083=3で式自体は成立するが、行列Aの計算結果(1行目が[−1,2]、2行目が[9,−17])とは一致しない。

覚えるべきポイント

拡張ユークリッド互除法では、互除法の各ステップを2×2行列で表し、その積を求めることでax+by=gcd(a,b)を満たすx、yが得られる。行列の積はゆっくり確実に計算し、最後に元の式へ代入して検算するとよい。