次のように求めます。

---

1. ユークリッドの互除法

[
\begin{aligned}
104 &= 1\cdot65 + 39 \
65 &= 1\cdot39 + 26 \
39 &= 1\cdot26 + 13 \
26 &= 2\cdot13 + 0
\end{aligned}
]

よって
[
\gcd(104,65)=13
]
なので
[
\boxed{\text{ア}=13}
]

---

2. 行列の計算

問題文より
[
A=
\begin{pmatrix}
0 & 1\
1 & -1
\end{pmatrix}
]
として

[
\left(
\begin{array}{c}
65\39
\end{array}
\right)
=A
\left(
\begin{array}{c}
104\65
\end{array}
\right),\quad
\left(
\begin{array}{c}
39\26
\end{array}
\right)
=A
\left(
\begin{array}{c}
65\39
\end{array}
\right),\quad
\left(
\begin{array}{c}
26\13
\end{array}
\right)
=A
\left(
\begin{array}{c}
39\26
\end{array}
\right)
]

をまとめると

[
\left(
\begin{array}{c}
26\13
\end{array}
\right)
=A^3
\left(
\begin{array}{c}
104\65
\end{array}
\right)
]

なので (A^3) を求める：

[
A^2=
\begin{pmatrix}
1 & -1\
-1 & 2
\end{pmatrix},\quad
A^3 = A^2A=
\begin{pmatrix}
-1 & 2\
2 & -3
\end{pmatrix}
]

したがって

[
A^3=
\begin{pmatrix}
-1 & 2\
\text{イ} & \text{ウ}
\end{pmatrix}

\begin{pmatrix}
-1 & 2\
2 & -3
\end{pmatrix}
]

より
[
\boxed{\text{イ}=2,\quad \text{ウ}=-3}
]

このとき

[
104\times\text{イ}+65\times\text{ウ}
=104\cdot2+65\cdot(-3)
=208-195
=13=\text{ア}
]

---

よって

[
(\text{ア},\text{イ},\text{ウ}) = (13,,2,,-3)
]

正しい選択肢は ④ です。

拡張ユークリッドの行列表現のアルゴリズムを詳しく教えてください

 

拡張ユークリッド互除法を２×２行列の積で表すと，ユークリッドの各剰余計算を行列演算に置き換え，最終的に

$$a x + b y = \gcd(a,b)$$

 

を満たす整数

$x,y$

を一括して得ることができます．以下，そのアルゴリズムを一般の場合についてステップごとに説明します．

---

1. ユークリッド互除法による商と剰余の計算

自然数

$a > b > 0$

に対して，まず通常の互除法を繰り返し，

$$\begin{aligned} r_{-1} &= a,\quad r_{0}=b,\\ r_{k-1} &= q_{k}\,r_{k} + r_{k+1}\quad (0\le r_{k+1}<r_k) \end{aligned}$$

 

という形で商

$q_{1},q_{2},\dots,q_{n}$

と剰余

$r_{1},r_{2},\dots,r_{n+1}$

を求めます．
最終的に

$r_{n+1}=0$

となるので，

$$\gcd(a,b)=r_{n}\,.$$

 

---

2. 各ステップを行列で表現

剰余計算

$$(r_{k-1},\,r_{k})^T \;\mapsto\;(r_{k},\,r_{k+1})^T$$

 

は，次の２×２行列を掛ける操作と同値です：

$$M_k \;=\; \begin{pmatrix} 0 & 1\\ 1 & -\,q_k \end{pmatrix},$$

$$\begin{pmatrix}r_k\\r_{k+1}\end{pmatrix} \;=\; M_k\, \begin{pmatrix}r_{k-1}\\r_k\end{pmatrix}.$$

 

言い換えれば，

$$\begin{pmatrix}r_n\\r_{n+1}\end{pmatrix} = M_n\,M_{n-1}\,\cdots\,M_1 \begin{pmatrix}a\\b\end{pmatrix} = \begin{pmatrix}\gcd(a,b)\\0\end{pmatrix}.$$

 

---

3. 行列の積から係数 $x,y$

 

 

を取り出す

行列の積

$$P \;=\; M_n\,M_{n-1}\,\cdots\,M_1 \;=\; \begin{pmatrix} p_{11} & p_{12}\\ p_{21} & p_{22} \end{pmatrix}$$

 

とすると，

$$\begin{pmatrix}\gcd(a,b)\\0\end{pmatrix} = P \begin{pmatrix}a\\b\end{pmatrix} = \begin{pmatrix} p_{11}\,a \;+\; p_{12}\,b \\[6pt] p_{21}\,a \;+\; p_{22}\,b \end{pmatrix}.$$

 

下段成分が

$0$

になることは互除法の終了条件に一致し，上段から

$$\gcd(a,b)\;=\;p_{11}\,a\;+\;p_{12}\,b$$

 

と読めます。したがって

$$x = p_{11},\quad y = p_{12}$$

 

が求める解です。

---

4. 実装上の注意点

1. 行列積は累積的に更新
   • 最初に
     $P \leftarrow I_2$ 

     （単位行列）とし，各ステップ

     $k=1\ldots n$ 

     で

     $$P \;\leftarrow\; M_k \,P$$と更新すればよい．

2. メモリ量・計算量
   • ２×２行列の掛け算は定数時間の演算なので，全体の計算量は互除法と同じ
     $O(\log\min(a,b))$ 

     ．

3. 係数の負号
   • 商
     $q_k$ 

     の符号は必ず正ですが，行列の下段成分には

     $-q_k$ 

     が入るため，途中で負の係数が出現します．しかし最終的に得られる

     $x,y$ 

     は整数解として正しく機能します．

---

5. 簡易コード例（疑似コード）

function extended_euclid_with_matrix(a, b):
    # P は 2×2 の単位行列
    P = [[1,0],
         [0,1]]
    while b ≠ 0:
        q = ⌊a / b⌋
        # Mq を作る
        M = [[0,  1],
             [1, -q]]
        # P ← M ⋅ P
        P = matrix_mul(M, P)
        # (a, b) ← (b, a - q·b)
        (a, b) = (b, a - q*b)
    # ここで a = gcd(original_a, original_b)
    # P = [[x, y], [..., ...]]
    x = P[0][0]
    y = P[0][1]
    return (a, x, y)

――――――
以上が，拡張ユークリッド互除法を「２×２行列の積」に置き換えて実装する方法の全体像です。行列を使うことで，「どのように

$x,y$

が更新されるか」が明確な形で定式化できるのが最大の利点です。

 

104⋅2+65⋅(−3)のイとウであれば最大公約数になるのですか

 

はい、まさに その通りです。

---

🌟 結論から言うと：

「104⋅イ + 65⋅ウ」

という形で 最大公約数を表せるような整数イ・ウ が存在します。

そして、

[
104\cdot 2 + 65\cdot(-3) = 13
]

となるので、

---

🔹この「2」と「−3」は

104 と 65 の最大公約数 13 を
「整数倍の和で表すための係数」

です。

---

⚠️ポイント

実は数学の定理として

---

✳ ベズーの等式（Bezout identity）

自然数 (a, b) に対し、

[
\gcd(a,b)=ax+by
]

となる整数 (x,y) が必ず存在する

---

ここで

• (a=104)
• (b=65)

なので、

必ず

[
13 = 104x + 65y
]

を満たす整数 (x,y) が存在します。

そのひとつが

[
x=2,\quad y=-3
]

です。

---

🔹「イ」と「ウ」はたまたまではなく、

数学的に意味のある値です。

最大公約数13を作るための係数
＝これが拡張ユークリッド法で求める本体

---

🔥 逆に言うと：

最大公約数13という「答え」だけなら
普通のユークリッド法で求まる。

しかし、

[
104x + 65y = 13
]

を満たす x, y (整数) を求めたい場合は
拡張ユークリッド法が必要。

そして
それが イ と ウ。

---

✔まとめ

値	意味
イ (=2)	ベズー係数 x
ウ (=−3)	ベズー係数 y
ア (=13)	最大公約数

---

必要なら
「なぜこの係数がこう出てくるのか」
をもっと分かりやすく説明しますよ😊