技事録係

IT中心にエンジニアに必要な技術情報・最新動向・資格試験対策等を記録

基礎科目 令和元年度再試験 Ⅰ-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}
となります。

これが,
  \begin{pmatrix} −1 2  \\ x y  \end{pmatrix}
と等しいため,x = 9,y = −17 になります。

参考情報

過去の出題

 なし

オンラインテキスト

(準備中)