本页使用了标题或全文手工转换

扩展欧几里得算法

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

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

如果a是负数,可以把问题转化成

为a的绝对值),然后令

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

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

例子[编辑]

用类似辗转相除法,求二元一次不定方程的整数解。

  • 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。

这个过程可以用矩阵表示(其中q表示商,r表示余数)

或者用初等变换

[2]

实现[编辑]

以下是扩展欧几里德算法的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

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

 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);
         int t = *x;
         *x = *y;
         *y = t - a/b * *y;
         return r;
     }
 }

参考资料[编辑]

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

參考文獻[编辑]

外部連結[编辑]