技術士 過去問
令和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）＝（ ア ）である。
自然数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）＝（ ア ）である。
このページは閲覧用ページです。
履歴を残すには、 「新しく出題する（ここをクリック）」 をご利用ください。
問題
技術士 第一次試験 令和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）＝（ ア ）である。
自然数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）＝（ ア ）である。
- ア：5 イ：2 ウ：-3
- ア：5 イ：-3 ウ：5
- ア：8 イ：3 ウ：-3
- ア：13 イ：2 ウ：-3
- ア：13 イ：-3 ウ：5
正解！素晴らしいです
残念...
この過去問の解説 （1件）
01
ユークリッド互除法を用いて、2つの整数の最大公約数を求める問題です。
その具体的な方法は問題文の通りで、まとめると以下のようになります。
（１）数の大きい方を小さい方で割り、その余りを大きい方と置き換える。
（２）余りが0になるまでくり返す。
（３）余りが0になったら終了で、最後に割った数が答え。
本選択肢が適切です。
ア：最後に割った数は13なので、答えは13になります。
イ・ウ：
ユークリッド互除法は、一次不定方程式 ax+by=c を解くのに用いることもできます。
参考になった数0
この解説の修正を提案する
前の問題（問10）へ
令和6年度（2024年） 問題一覧
次の問題（問12）へ