技術士過去問
令和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）＝（　ア　）である。問題文の画像

付箋

イエロー
グリーン
ブルー
レッド

付箋は自分だけが見れます（非公開です）。

このページは閲覧用ページです。
履歴を残すには、「新しく出題する（ここをクリック）」をご利用ください。

問題

技術士試験令和6年度（2024年）問11（基礎科目「情報・論理に関するもの」問5）（訂正依頼・報告はこちら）

ア：5　　イ：2　　ウ：-3
ア：5　　イ：-3　　ウ：5
ア：8　　イ：3　　ウ：-3
ア：13　　イ：2　　ウ：-3
ア：13　　イ：-3　　ウ：5

次の問題へ

正解！素晴らしいです

残念...

この過去問の解説（1件）

この問題は「拡張ユークリッドの互除法」を、行列の計算を使って説明する問題です。

普通のユークリッドの互除法では「最大公約数（gcd）」だけを求めますが、拡張ユークリッドの互除法では、それに加えて次の式を満たす整数 x、y を求めます。

　ax＋by＝gcd（a,b）

ここでは、

　a＝104 b＝65

のときの x、y を、行列演算を使って求める手順を説明しています。

選択肢4. ア：13　　イ：2　　ウ：-3

（1）ユークリッドの互除法で割り算を繰り返す。

　104 ÷ 65 ＝ 1 余り 39 ・・・(1)

　 65 ÷ 39 ＝ 1 余り 26　・・・(2)

　 39 ÷ 26 ＝ 1 余り 13　・・・(3)

　 26 ÷ 13 ＝ 2 余り 0

したがって、

　gcd(104、 65) = 13

よって（ア）＝13

（2）行列による表現

各ステップは次の行列で表せます。

　[ b ] [ 0 1 ] [ a ]

　[ r ] = [ 1 －1 ] [ b ]

ここで、r は a ÷ b の余りです。

この操作を3回繰り返すので、次のようになります。

　( [ 0 1 ]

　 [ 1 －1 ] )³

この行列を計算すると、

　[－1 2 ]

　[ 2 －3 ]

となります。

（3）最終式

上の行列の結果を使うと次の関係が得られます。

　104×2 + 65×(－3) = 13

したがって、ア＝13、イ＝2、ウ=－3、となります。

まとめ

ア＝13、イ＝2、ウ=－3

gcd(104、65)＝13、x＝2、y=−3

ユークリッドの互除法は、余りを使って gcd を求める手法です。

行列を用いると、ユークリッド互除法の計算過程が体系的に表現できます。

参考になった数7

この解説の修正を提案する

次の問題は下へ

（訂正依頼・報告はこちら）

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

問題

この過去問の解説 （1件）

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

この過去問の解説（1件）