問題
（出典：日本技術士会のホームページ 過去問題（第一次試験） 基礎科目 令和6年度）
コーチング対話解答
ツトムさんユークリッド互除法は、過去にも何度かアルゴリズムの問題として出題されましたが、今回、拡張ユークリッド互除法というのはgcdなどという記号も出てきて、難しそうですね。
マナブ先生見た目は難しそうで、問題文も長い、という問題はよく出題されます。
しかし、このような問題こそ、ボーナス問題で、実は簡単ということがあります。
まず、アを求めてみましょう。
ツトムさん「ユークリッド互除法で割り算を繰り返し、次の式を得る。」と書いてあるので、
最後の余りが０になる式の割る数が最大公約数ですね。するとアは13ですね。
マナブ先生そうです。記号gcdというのは単に最大公約数という意味ですので、難しく考える必要は無いのですよ。
ツトムさん次は行列を使っていますね。複雑そうですが．．．。
でも、問題は \(
\begin{pmatrix}
0 & 1 \\
1 & -1
\end{pmatrix}^3
\) を計算してみればいいのですね。
そうすると \(
\begin{pmatrix}
-1 & 2 \\
2 & -3
\end{pmatrix}
\) になり、イが2、ウが－3になりました。
これを最後の式に代入してみると、
104×2＋65×(－3)＝13
になりましたね。
解答は④ ですね。
マナブ先生その通りです。
簡単だったでしょう。
イとウを求めるのは式（３）から式（１）を使って逆代入をしていっても求められます。
ツトムさん式（３）から 13＝39－1×26 が得られて、この26に式（２）を代入ですね。
13＝39－(65－39)=2×39－65 となり、この39に式（１）を代入します。
13＝2×(104－65)－65＝2×104－3×65
だから、104×2＋65×(－3)＝13 になって、イとウが求められるのですね。
マナブ先生そうですね。
