技術士第一次試験｜無料Web版
技術士 基礎科目 令和6年度 Ⅰ－２－５｜問題と解説
問題 Ⅰ－２－５
拡張ユークリッド互除法の計算アルゴリズムについて説明した次の記述の（ ）に入る値の組合せとして、最も適切なものはどれか。
自然数a，bに対して、その最大公約数を記号 gcd（a，b）で表す。 ここでは、ユークリッド互除法と行列の計算によって、ax＋by＝gcd（a，b）を満たす整数x，y を計算するアルゴリズムをa＝104，b＝65の例を使って説明する。 まず、ユークリッド互除法で割り算を繰り返し、次の式を得る。
104÷65＝1 余り39（1）
65÷39＝1 余り26（2）
39÷26＝1余り13（3）
26÷13＝2余り0
したがって、gcd（104，65）＝アである。
1 ア：5 イ：2 ウ：-3
2 ア：5 イ：-3 ウ：5
3 ア：8 イ：3 ウ：-3
4 ア：13 イ：2 ウ：-3
5 ア：13 イ：-3 ウ：5
問題図表
正解と解説
正解：4
解説最大公約数と、104x＋65yでそれを表す整数係数を求める。
1．最後の0でない余りを読む
余りは39、26、13、0と推移する。したがって gcd(104,65)＝13で、アは13。
2．割り算を逆に代入する
13＝39−26
＝39−(65−39)＝2×39−65
＝2(104−65)−65
＝2×104−3×65
3．行列の空欄と照合する
図の行列をQとすると Q2＝1−1−12、Q3＝−122−3。下段は逆代入と同じ係数2、−3になる。
ア＝13、イ＝2、ウ＝−3。104×2＋65×(−3)＝13と検算できる。
拡張ユークリッド互除法は，最大公約数を求めるだけでなく，ax＋by＝gcd（a，b） を満たす係数 x，y を求める。最後の余りから式を逆に代入することで，を得る。公開鍵暗号の逆元計算にも使われる。
問題・正答の出典：公益社団法人 日本技術士会（公式の過去問題・公式正答）
掲載している解説は日本技術士会の公式解説ではありません。