## 利用基本列運算實現擴展歐幾里得演算法

$a, b$ 為二整數，它們的最大公約數記為 $\gcd(a,b)$。因為 $\gcd(\vert a\vert, \vert b\vert)=\gcd(a,b)$，為了方便，我們可假設 $a\ge b>0$。歐幾里得演算法的基本原理在於這個性質：若 $a=qb+r$，其中 $q$ 是商，$r$ 是餘數且 $0\le r，則 $\gcd(a,b)=\gcd(b,r)$。歐幾里得演算法重複運用此性質輾轉相除以得到最大公約數，運算過程可表示為下列方程組：

\begin{aligned} a&=q_1b+r_1~~~~~0

\begin{aligned} 5892&=3\cdot 1902+186\\ 1902&=10\cdot 186+42\\ 186&=4\cdot 42+18\\ 42&=2\cdot 18+6\\ 18&=3\cdot 6+0 \end{aligned}

\begin{aligned} \gcd(5892,1902)&=\gcd(1902,186)=\gcd(186,42)=\gcd(42,18)\\ &=\gcd(18,6)=\gcd(6,0)=6\end{aligned}

$ax+by=\gcd(a,b)$

\begin{aligned} 6&=42-2\cdot 18\\ &=42-2(186-4\cdot 42)\\ &=(-2)186+9\cdot 42\\ &=(-2)186+9(1902-10\cdot 186)\\ &=9\cdot 1902-92\cdot 186\\ &=9\cdot 1902-92(5892-3\cdot 1902)\\ &=(-92)5892+285\cdot 1902, \end{aligned}

\begin{aligned} 6&=(-92+1902)5892+(285-5892)1902\\ &=1810\cdot 5892-5607\cdot 1902. \end{aligned}

\begin{aligned} r_k&=r_{k-2}-q_kr_{k-1}\\ s_k&=s_{k-2}-q_ks_{k-1}\\ t_k&=t_{k-2}-q_kt_{k-1} \end{aligned}

$\begin{bmatrix} s_{-1}&t_{-1}&r_{-1}\\ s_{0}&t_{0}&r_{0} \end{bmatrix}\to\begin{bmatrix} s_{1}&t_{1}&r_{1}\\ s_{0}&t_{0}&r_{0} \end{bmatrix}\to\begin{bmatrix} s_{1}&t_{1}&r_{1}\\ s_{2}&t_{2}&r_{2} \end{bmatrix}\to\cdots$

$\left[\!\!\begin{array}{cr} 1&-q_k\\ 0&1 \end{array}\!\!\right]\begin{bmatrix} s_{k-2}&t_{k-2}&r_{k-2}\\ s_{k-1}&t_{k-1}&r_{k-1} \end{bmatrix}=\begin{bmatrix} s_{k}&t_{k}&r_{k}\\ s_{k-1}&t_{k-1}&r_{k-1} \end{bmatrix}$

$\left[\!\!\begin{array}{rc} 1&0\\ -q_k&1 \end{array}\!\!\right]\begin{bmatrix} s_{k-1}&t_{k-1}&r_{k-1}\\ s_{k-2}&t_{k-2}&r_{k-2} \end{bmatrix}=\begin{bmatrix} s_{k-1}&t_{k-1}&r_{k-1}\\ s_{k}&t_{k}&r_{k} \end{bmatrix}$

$E_{12}(-c)=\left[\!\!\begin{array}{cr} 1&-c\\ 0&1 \end{array}\!\!\right],~~E_{21}(-c)=\left[\!\!\begin{array}{rc} 1&0\\ -c&1 \end{array}\!\!\right]$

\begin{aligned} \begin{bmatrix} 1&0&5892\\ 0&1&1902 \end{bmatrix}&\xrightarrow[]{E_{12}(-3)}\left[\!\!\begin{array}{crr} 1&-3&186\\ 0&1&1902 \end{array}\!\!\right]\xrightarrow[]{E_{21}(-10)}\left[\!\!\begin{array}{rrr} 1&-3&186\\ -10&31&42 \end{array}\!\!\right]\\ &\xrightarrow[]{E_{12}(-4)}\left[\!\!\begin{array}{rrr} 41&-127&18\\ -10&31&42 \end{array}\!\!\right]\xrightarrow[]{E_{21}(-2)}\left[\!\!\begin{array}{rrr} 41&-127&18\\ -92&285&6 \end{array}\!\!\right]\\ &\xrightarrow[]{E_{12}(-3)}\left[\!\!\begin{array}{rrc} 317&-982&0\\ -92&285&6 \end{array}\!\!\right] \end{aligned}

$\begin{bmatrix} 1&0\\ 0&1 \end{bmatrix} \begin{bmatrix} u\\ v \end{bmatrix}=\begin{bmatrix} 5892\\ 1902 \end{bmatrix}$

$\left[\!\!\begin{array}{rr} 317&-982\\ -92&285 \end{array}\!\!\right] \begin{bmatrix} u\\ v \end{bmatrix}=\begin{bmatrix} 0\\ 6 \end{bmatrix}$

\begin{aligned} 317\cdot 5892-982\cdot 1902&=0\\ (-92)5892+285\cdot 1902&=6. \end{aligned}

[1] Donald E. Knuth, The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, Second Edition, Addison-Wesley, 1981, pp 318. 原文是 “We might call it the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day.”
[2] 維基百科：輾轉相除法