扩展欧几里得算法

（重定向自擴展歐幾里得演算法

${\displaystyle ax+by=\gcd(a,b).}$

${\displaystyle \left|a\right|(-x)+by=\gcd(|a|,b)}$${\displaystyle \left|a\right|}$为a的绝对值），然后令${\displaystyle x'=(-x)}$

例子

• ${\displaystyle 47=30\times 1+17}$
• ${\displaystyle 30=17\times 1+13}$
• ${\displaystyle 17=13\times 1+4}$
• ${\displaystyle 13=4\times 3+1}$

• ${\displaystyle 17=47\times 1+30\times (-1)}$ //式1
• ${\displaystyle 13=30\times 1+17\times (-1)}$ //式2
• ${\displaystyle 4=17\times 1+13\times (-1)}$ //式3
• ${\displaystyle 1=13\times 1+4\times (-3)}$

• ${\displaystyle 1=13\times 1+4\times (-3)}$
• ${\displaystyle 1=13\times 1+[17\times 1+13\times (-1)]*(-3)}$ //应用式3
• ${\displaystyle 1=17\times (-3)+13\times 4}$
• ${\displaystyle 1=17\times (-3)+[30\times 1+17\times (-1)]\times 4}$//应用式2
• ${\displaystyle 1=30\times 4+17\times (-7)}$
• ${\displaystyle 1=30\times 4+[47\times 1+30\times (-1)]\times (-7)}$ //应用式1
• ${\displaystyle 1=47\times (-7)+30\times 11}$

${\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}=\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}}$

${\displaystyle {\begin{pmatrix}47\\30\end{pmatrix}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}{\begin{pmatrix}1&1\\1&0\end{pmatrix}}{\begin{pmatrix}1&1\\1&0\end{pmatrix}}{\begin{pmatrix}3&1\\1&0\end{pmatrix}}{\begin{pmatrix}4&1\\1&0\end{pmatrix}}{\begin{pmatrix}1\\0\end{pmatrix}}={\begin{pmatrix}47&11\\30&7\end{pmatrix}}{\begin{pmatrix}1\\0\end{pmatrix}}}$

${\displaystyle {\begin{pmatrix}1\\0\end{pmatrix}}={\begin{pmatrix}-7&11\\30&-47\end{pmatrix}}{\begin{pmatrix}47\\30\end{pmatrix}}}$

${\displaystyle {\begin{pmatrix}47&30\\1&0\\0&1\end{pmatrix}}\rightarrow {\begin{pmatrix}17&30\\1&0\\-1&1\end{pmatrix}}\rightarrow {\begin{pmatrix}17&13\\1&-1\\-1&2\end{pmatrix}}\rightarrow {\begin{pmatrix}4&13\\2&-1\\-3&2\end{pmatrix}}\rightarrow {\begin{pmatrix}4&1\\2&-7\\-3&11\end{pmatrix}}\Rightarrow 1=47(-7)+30(11)}$ [2]

实现

def ext_euclid(a, b):
if b == 0:
return 1, 0, a
else:
x, y, q = ext_euclid(b, a % b) # q = gcd(a, b) = gcd(b, a%b)
x, y = y, (x - (a // b) * y)
return x, y, q


 int gcdEx(int a, int b, int *x, int *y)
{
if(b==0)
{
*x = 1,*y = 0;
return a;
}
else
{
int r = gcdEx(b, a%b, x, y); /* r = GCD(a, b) = GCD(b, a%b) */
int t = *x;
*x = *y;
*y = t - a/b * *y;
return r;
}
}


参考资料

1. ^ 沈淵源. 數論輕鬆遊 (PDF). [2017-09-25] （中文（台灣）‎）.
2. ^ 张慧玲. 介绍多项式带余除法的矩阵形式及其应用. 太原大学教育学院学报. 2014, (1): 第103–105页.