基礎科目令和元年度再試験 Ⅰ-2-2

◀︎ 前へ｜次へ ▶︎️

　自然数a，bに対して，その最大公約数を記号gcd(a, b)で表す。ここでは，ユークリッド互除法と行列の計算によって，ax + by = gcd(a, b)を満たす整数x，yを計算するアルゴリズムを，a = 108，b = 57の例を使って説明する。まず，ユークリッド互除法で割り算を繰り返し，次の式（1）〜（4）を得る。

108 ÷ 57 = 1 余り 51　（1）
57 ÷ 51 = 1 余り 6　（2）
51 ÷ 6 = 8 余り 3　（3）
6 ÷ 3 = 2 余り 0　（4）

　したがって，gcd(108, 57) = 　ア　である。

式（1）（2）は行列を使って， $\begin{pmatrix} 57 \\ 51 \end{pmatrix} =\begin{pmatrix} 0　1　 \\ 1　−1　 \end{pmatrix} \begin{pmatrix} 108 \\ 57 \end{pmatrix}$

式（2）（3）は行列を使って， $\begin{pmatrix} 51 \\ 6 \end{pmatrix} =\begin{pmatrix} 0　1　 \\ 1　−1　 \end{pmatrix} \begin{pmatrix} 57 \\ 51 \end{pmatrix}$

式（3）（4）は行列を使って， $\begin{pmatrix} 6 \\ 3 \end{pmatrix} =\begin{pmatrix} 0　1　 \\ 1　−8　 \end{pmatrix} \begin{pmatrix} 51 \\ 6 \end{pmatrix}$ と書けるので，

$A =\begin{pmatrix} 0　1　 \\ 1　−8　 \end{pmatrix} \begin{pmatrix} 0　1　 \\ 1　−1　 \end{pmatrix} \begin{pmatrix} 0　1　 \\ 1　−1　 \end{pmatrix} = \begin{pmatrix} −1　2　 \\ x　y　 \end{pmatrix}$ と置くと，

x = 　イ　，y = 　ウ　　であり，108 × 　イ　 + 57 × 　ウ　 = 　ア　を満たす。

　ア　〜　ウ　　に入る最も適切な値の組合せはどれか。

	ア	イ	ウ
①	6	−1	2
②	6	1	−2
③	6	1	2
④	3	9	−17
⑤	3	−10	19

解答・解説

解答

　④

参考書・問題集

解説

　まず（1）〜（4）より，余りが0になる3が最大公約数になります。

　また，式Aを計算すると，
　　 $\begin{pmatrix} 0　1　 \\ 1　−8　 \end{pmatrix} \begin{pmatrix} 0　1　 \\ 1　−1　 \end{pmatrix} \begin{pmatrix} 0　1　 \\ 1　−1　 \end{pmatrix} = \begin{pmatrix} −1　2　 \\ 9　−17　 \end{pmatrix}$
となります。