扩展欧几里得算法

例子

用类似辗转相除法，求二元一次不定方程 47 x + 30 y = 1 {\textstyle 47x+30y=1} 的整数解。

47 = 30 * 1 + 17

30 = 17 * 1 + 13

17 = 13 * 1 + 4

13 = 4 * 3 + 1

然后把它们改写成“余数等于”的形式

17 = 47 * 1 + 30 * (-1) //式1

13 = 30 * 1 + 17 * (-1) //式2

4 = 17 * 1 + 13 * (-1) //式3

1 = 13 * 1 + 4 * (-3)

然后把它们“倒回去”

1 = 13 * 1 + 4 * (-3)

1 = 13 * 1 + [17 * 1 + 13 * (-1)] * (-3) //应用式3

1 = 17 * (-3) + 13 * 4

1 = 17 * (-3) + [30 * 1 + 17 * (-1)] * 4 //应用式2

1 = 30 * 4 + 17 * (-7)

1 = 30 * 4 + [47 * 1 + 30 * (-1)] * (-7) //应用式1

1 = 47 * (-7) + 30 * 11

得解x=-7, y=11。

这个过程可以用矩阵表示（其中q表示商，r表示余数）

( a b ) = ∏ ∏ --> i = 0 N ( q i 1 1 0 ) ( r N − − --> 1 0 ) {\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}}}

( 47 30 ) = ( 1 1 1 0 ) ( 1 1 1 0 ) ( 1 1 1 0 ) ( 3 1 1 0 ) ( 4 1 1 0 ) ( 1 0 ) = ( 47 11 30 7 ) ( 1 0 ) {\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}}}

( 1 0 ) = ( − − --> 7 11 30 − − --> 47 ) ( 47 30 ) {\displaystyle {\begin{pmatrix}1\\0\end{pmatrix}}={\begin{pmatrix}-7&11\\30&-47\end{pmatrix}}{\begin{pmatrix}47\\30\end{pmatrix}}}

或者用初等变换

( 47 30 1 0 0 1 ) → → --> ( 17 30 1 0 − − --> 1 1 ) → → --> ( 17 13 1 − − --> 1 − − --> 1 2 ) → → --> ( 4 13 2 − − --> 1 − − --> 3 2 ) → → --> ( 4 1 2 − − --> 7 − − --> 3 11 ) ⇒ ⇒ --> 1 = 47 ( − − --> 7 ) + 30 ( 11 ) {\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)}

实现

以下是扩展欧几里德算法的Python实现：

defext_euclid(a,b):if(b==0):return1,0,aelse:x,y,q=ext_euclid(b,a%b)x,y=y,(x-(a//b)*y)returnx,y,q

扩展欧几里得算法C语言实现：

intgcdEx(inta,intb,int*x,int*y){if(b==0){*x=1,*y=0;returna;}else{intr=gcdEx(b,a%b,x,y);intt=*x;*x=*y;*y=t-a/b**y;returnr;}}

参考文献

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 算法导论, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 859–861 of section 31.2: Greatest common divisor.

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。