https://kakomonn.com/gijyutushi/questions/80696

拡張ユークリッドの行列表現から

$$M=\begin{pmatrix}0&1\\1&-1\end{pmatrix},\quad M^3=\begin{pmatrix}-1&2\\2&-3\end{pmatrix}$$

よって底行列成分がイ＝2, ウ＝−3 となり

$$104×2+65×(-3)=208-195=13$$

よってア＝13．選択肢は④です。

 

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

 

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

$$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$ が更新されるか」が明確な形で定式化できるのが最大の利点です。