技術士第一次試験 基礎科目 R06

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

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