扩展欧几里德算法的原理与实现 - sbw Blog

扩展欧几里德算法的原理与实现

来源: 石博文博客 | 浏览: 11671 | 评论: 2 发表时间: 2013-08-01

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。而扩展欧几里德算法是用来在已知a, b求解一组x,y使得ax+by = gcd(a, b) =d(解一定存在,根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。



在介绍扩展欧几里德算法之前,先来看一下欧几里德算法.


欧几里德算法

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。C++语言实现如下:


而扩展欧几里德算法是给两个整数 a,b 必然存在 一对整数 x,y 使得 ax + by = gcd(a,b) .(又叫贝祖定理).


由朴素的欧几里德算法可以得道, gcd(a,b) == gcd(b,a%b); 那么就有了如下的推断:


欧几里德算法

在上式中.两个等式右边满足欧几里德算法,所以有了a*x1+b*y1=b*x2+(a%b)*y2; 经过化简,得到x1,y1与x2,y2的关系.(最后两个等式)


扩展欧几里德算法

下面来看扩展欧几里德算法,以这个题目为例:


已知等式 47x + 30y = 1;求x,y的整数解.


设扩展欧几里德算法为gcdEx(a,b,x,y); 其中a,b为已知,x,y为所求.那么gcdEx(a,b,x,y)函数就有如下的计算过程:


扩展欧几里德算法

左边,是利用朴素欧几里德算法相除得到一系列中间值,直到b=0.当b=0时,开始倒回去,令x=1;y=0;往上一步的x,y看作x1,y1.下面'旧'的x,y看作x2,y2.利用朴素欧几里德算法推导出的结论,x1=y2,y1=x2-(a/b)*y2;其中,a,b就是当前gcdEx中的a,b.当这样递归回去到了第一个调用点时,所得到的x,y就是结果,即x=-7,y=11;


当然,此题目刚好满足ax+by=gcd(a,b); 其实,对于任意的ax+by=c;若c为gcd(a,b)的整数倍,即存在整数解.


C++ 语言实现扩展欧几里德算法



  • 声明: 评论属于其发表者所有,不代表本站的观点和立场.
  • 路人甲 回复该留言 时间: 2016-03-26

    okay

已有 1 位网友发表了一针见血的评论,你还等什么?
  • 昵称: *
  • 邮箱:
  • 网址:
  • 记住我的信息
  • Color
  • Red
  • Blue
  • Code
  • bash
  • cpp
  • css
  • java
  • js
  • perl
  • php
  • python
  • ruby
  • sql
  • xml