扩展欧几里得算法

维基百科,自由的百科全书
跳转至: 导航搜索

扩展欧几里得算法欧几里得算法(又叫辗转相除法)的扩展。已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足貝祖等式ax + by = \gcd(a, b).

通常談到最大公因數時, 我們都會提到一個非常基本的事實: 給予二整數 a 、b, 必存在有整數 x 、 y 使得ax + by = gcd(a,b)[1]

有两个数a,b,对它们进行辗转相除法,可得它们的最大公约数——这是众所周知的。然后,收集辗转相除法中产生的式子,倒回去,可以得到ax+by=gcd(a,b)的整数解。

例子[编辑]

用类似辗转相除法,求二元一次不定方程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) //应用式3
  • 1=13*1+[17*1+13*(-1)]*(-3)
  • 1=13*4+17*(-3) //应用式2
  • 1=[30*1+17*(-1)]*4+17*(-3)
  • 1=30*4+17*(-7) //应用式1
  • 1=30*4+[47*1+30*(-1)]*(-7)
  • 1=30*11+47*(-7)

得解x=-7, y=11。

这个过程可以用矩阵表示


\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}


\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}


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

这个方法就是扩展欧几里德算法。

实现[编辑]

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

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

参考资料[编辑]

  1. ^ 沈淵源. 數論輕鬆遊. [2012-11-27] (中文(台灣)‎). 

參考文獻[编辑]

外部連結[编辑]