出典：公益社団法人 日本技術士会「技術士第一次試験 過去問題」
拡張ユークリッド互除法をa=104, b=65の例で行列計算により実行するアルゴリズムについて、最大公約数の値と行列のべき乗の成分を求める問題。
ユークリッド互除法の割り算の繰り返し(104と65の例)から最大公約数gcd(104,65)を求め、さらにその過程を表す行列の3乗の成分(イ、ウ)を求める問題。
① gcdは互除法の最後の0でない余り。行列の積は「左の行×右の列」を掛けて足す
② gcd(104,65)=13。M²=(1,−1;−1,2)、M³=M²×M=(−1,2;2,−3) → イ=2、ウ=−3
③ ア13・イ2・ウ−3(④)
ユークリッド互除法の計算より、最後の0でない余りである13がgcd(104,65)であるため、ア=13である。行列M=(0,1;1,−1)について、M²=M×M=(1,−1;−1,2)、M³=M²×M=(1,−1;−1,2)×(0,1;1,−1)=(−1,2;2,−3)と計算できる。問題文でM³=(−1,2;イ,ウ)と与えられているので、イ=2、ウ=−3である。式(1)〜(3)を合わせるとM³(104,65)ᵀ=(26,13)ᵀなので、第2行から104×2+65×(−3)=13が得られ、これがax+by=gcd(a,b)を満たす整数解になっている(第1行は104×(−1)+65×2=26)。したがってア=13、イ=2、ウ=−3の組合せである④が正しい。
行列の掛け算(積)のやり方を確認します。ここでは行列を(0,1;1,−1)のように、行を「;」で区切って書きます。
■ 行列×縦ベクトル(式(1)〜(3)の形)
左の行列の各行と縦ベクトルを、同じ位置どうし掛けて足します。式(1)なら
・1行目: 0×104+1×65=65
・2行目: 1×104+(−1)×65=39
となり、確かに(65, 39)が得られます。
■ 行列×行列
左の行列の「行」と右の行列の「列」を同じ位置どうし掛けて足し、これを全ての行・列の組合せについて行います。例えばM=(0,1;1,−1)としてM²=M×Mは
・1行1列目: 0×0+1×1=1
・1行2列目: 0×1+1×(−1)=−1
・2行1列目: 1×0+(−1)×1=−1
・2行2列目: 1×1+(−1)×(−1)=2
となります。同じ手順でM³=M²×Mも計算できます。
■ 「これらの式をまとめて」の意味
式(3)の右辺の(39, 26)に式(2)を、さらにその中の(65, 39)に式(1)を代入すると、(26, 13)=M×M×M×(104, 65)=M³×(104, 65)となります。
ユークリッド互除法での最大公約数は最後の0でない余りである。また、各割り算の商を用いた行列の積を繰り返し計算することで、ax+by=gcd(a,b)を満たす整数x, y(拡張ユークリッド互除法の解)を求められる。解は一意でないため、この問題のように『行列の計算結果として何が得られるか』を確認する必要がある。
キーワード: 拡張ユークリッド互除法、最大公約数、行列、情報・論理