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

自然数 a , b に対して、その最大公約数を記号 gcd（ a , b ）で表す。

ここでは、ユークリッド互除法と行列の計算によって、ax + by = gcd（ a , b ）を満たす整数 x , y を計算するアルゴリズムを、a = 108 , b = 57の例を使って説明する。

まず、ユークリッド互除法で割り算を繰り返し、次の式（ 1 ）～（ 4 ）を得る。（ ア ）～（ ウ ）に入る最も適切な値の組合せはどれか。