欧几里得算法以及扩展算法

偏执的太偏执、 2021-11-22 20:22 252阅读 0赞

一、简介

欧几里得算法又称“辗转相除法”，它首次出现于欧几里得的《[几何原本][Link 1]》（第VII卷，命题yⅠ和Ⅱ）中，而在中国则可以追溯至东汉出现的《[九章算术][Link 2]》。它是用来求最大公约数的算法。

二、证明

对于两个整数a，b.假设他们的最大公约数c = gcd( a, b )，则对于b，a mod b的最大公约数也是c，即：gcd( a，b ) = gcd( b，a mod b )。a = kb + r

证明：

（辗转相除法）

1）令c = gcd(a, b），则设a=xc，b=yc

2）r =a - kb=xc - kyc=(x - ky)\*c，则有c也是r的约数，即：c为a mod b的约数。

3）从而可以得到x, ky没有公约数（反证法可以证明）

从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r）。

证毕。

三、算法

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 　　int gcd( int a, int b ) {
    2 　　　　return b ? gcd( b, a % b ) : a;
    3 　　}

四、扩展算法

对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在唯一的整数 x，y （注意：这里是整数，也可以为负数），使得 gcd（a，b）=ax+by。

当b = 0时，gcd(a,b)=1,x = 1, y = 0。

又由于有： gcd（a，b）=  gcd（b，a mod b），则有gcd（a，b）=bx' + (a mod b)y' ,由此容易得出可有递归求出x，y。

算法：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 int exgcd(int a, int b, int &x, int &y) {  //x, y 是全局性的
      2   int r, swap;
     3   if( b == 0 ){
     4      x = 1;
     5      y = 0;
     6      return a;
     7   }
     8   
     9   r = exgcd( b, a%b, x, y );
    10   swap = x
    11   x = y;
    12   y = ( swap - a/b * y);
    13   return r;
    14 }

转载于:https://www.cnblogs.com/jackie-zl/p/3297596.html

[Link 1]: http://baike.baidu.com/view/44606.htm
[Link 2]: http://baike.baidu.com/view/17765.htm
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211122/3f93a26a039a455aaca754e630227978.png