技術士 過去問
令和6年度（2024年）
問11 (基礎科目「情報・論理に関するもの」 問5)

拡張ユークリッド互除法の計算アルゴリズムについて説明した次の記述の（　　　）に入る値の組合せとして、最も適切なものはどれか。

自然数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）＝（　ア　）である。