tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 学科竞赛 >>

扩展欧几里得算法详细举例解析


扩展欧几里得算法
什么是 GCD?
GCD 是最大公约数的简称(当然理解为我们伟大的党也未尝不可)。在开头,我们先下几 个定义: ①a|b 表示 a 能整除 b(a 是 b 的约数) ②a mod b 表示 a-[a/b]b([a/b]在 Pascal 中相当于 a div b)。即有 a|b <=> b mod a=0。 ③gcd(a,b)表示

a 和 b 的最大公约数 ④a 和 b 的线性组合表示 ax+by(x,y 为整数)。我们有:若 d|a 且 d|b,则 d|ax+by(这很重 要!)

线性组合与 GCD
现在我们证明一个重要的定理:gcd(a,b)是 a 和 b 的最小的正线性组合。

例:a=6 b=4,最小正线性组合为 1*a+(-1)*b=2=gcd(a,b)。

证明: 设 gcd(a,b)为 d,a 和 b 的最小的正线性组合为 s ∵d|a 且 d|b, ∴d|s。 而 a mod s=a-[a/s]s =a-[a/s](ax+by) =a(1-[a/s]x)-b[a/s]y 亦为 a 和 b 的线性组合 ∵a mod s<s,a mod s 不能是 a 和 b 的最小的正线性组合 ∴a mod s=0,即 s|a 同理由 s|b ∴s 为 a,b 的公约数 ∴s<=d ∵d|s ∴d=s。证毕。

-1-

由这条定理易推知:若 d|a 且 d|b,则 d|gcd(a,b)

Euclid 算法
现在的问题是如何快速的求 gcd(a,b)。穷举明显不是一个好方法(O(n)),所以需要一个更 好的方法。 首先我们先提出一个定理:gcd(a,b)=gcd(b,a-bx)(x 为正整数)。 证明: 设 gcd(a,b)=d,gcd(b,a-bx)=e,则 ∵d|a,d|b ∴d|a-bx ∴d|gcd(b,a-bx),即 d|e ∵e|b,e|a-bx ∴e|bx+(a-bx),即 e|a ∴e|gcd(a,b),即 e|d ∴d=e。证毕。 这个定理非常有用,因为它能快速地降低数据规模。 当 x=1 时,gcd(a,b)=gcd(b,a-b)。这就是辗转相减法。 当 x 达到最大时,即 x=[a/b]时,gcd(a,b)=gcd(b,a mod b)。这个就是 Euclid 算法。它是不是 Euclid 提出的我不知道,但听说是在 Euclid 时代形成的,所以就叫 Euclid 算法了。程序非 常的简单: function Euclid(a,b:longint):longint; begin if b=0 then exit(a) else exit(Euclid(b,a mod b)); end; Euclid 算法比辗转相减法好,不仅好在速度快,而且用起来也方便。两种算法都有一个隐含 的限制:a>=b。用辗转相减法时,必须先判断大小,而 Euclid 算法不然。若 a<b,则一次递 归就会转为 gcd(b,a),接着就能正常运行了。

扩展 Euclid
前面我们说过,gcd(a,b)可以表示为 a 和 b 的最小的正线性组合。现在我们就要求这个最小 的正线性组合 ax+by 中的 x 和 y。这个可以利用我们的 Euclid 算法。 从最简单的情况开始。 当 b=0 时,我们取 x=1,y=0。 例:a=5,b=0,最小正线性组合为 5*1+y*0=5,y 为任意整数。这里为方便起见规定此时 y=0。

-2-

当 b≠0 时呢? 假设 gcd(a,b)=d,则 gcd(b,a mod b)=d。若我们已经求出了 gcd(b,a mod b)的线性组合表示 bx'+(a mod b)y',则 gcd(a,b)=d =bx'+(a mod b)y' =bx'+(a-[a/b]b)y' =ay'+b(x'-[a/b]y') 那么,x=y',y=x'-[a/b]y'。这样就可以在 Euclid 的递归过程中求出 x 和 y。 程序: function gcd(a,b:longint):longint; var p,n:longint; begin if b=0 then begin x:=1; y:=0; exit(a); end else begin p:=gcd(b,a mod b); n:=x; x:=y; y:=n-a div b*y; exit(p); end; end; 我们现在还有一个问题: 是不是确定的?答案: x,y 不是。 如果 x,y 符合要求, 那么 x+bk,y-ak 也符合要求。不确定的原因在于这一句:“当 b=0 时,我们取 x=1,y=0。”实际上 y 可以取任 何正整数。 以 gcd(26,15)为例: (26,15) (15,11) (11,4) (4,3) (3,1) (1,0) X=-4 Y=3-1*(-4)=7 26*(-4)+15*7=1 X=3 Y=-1-1*3=-4 15*3+11*(-4)=1 X=-1 Y=1-2*(-1)=3 11*(-1)+4*3=1 X=1 Y=0-1*1=-1 4*1+3*(-1)=1 X=0 Y=1-3*0=1 3*0+1*1=1 X=1 Y=0 1*1+0*0=1



-3-

不定方程 ax+by=c
现在终于到了本文重点:解二元一次不定方程。看起来扩展 Euclid 算法是不定方程的一种 特殊情况,实际上呢,不定方程却是用 Euclid 算法解的。 对于不定方程 ax+by=c,设 gcd(a,b)=d,如果 ax+by=c 有解,则 d|c(这也是许多奥数题的切 入点)所以一旦 d 不是 c 的约数, 。 那么 ax+by=c 一定无解。 d|c 时, 当 先求出 ax’+by’=d=gcd(a,b) 的 x'和 y', 由于已经有 ax’+by’=d, 要求 ax’+by’=c, 将整个式子同乘 c/d 倍即可。 x=x'*c/d, 则 y=y'*c/d。由上一段可知, 只要 ax+by=c 有一个解,它就有无数个解。 Euclid 算法还可以求解同余方程 ax≡b(mod m)及其最小 x。这其实和不定方程 ax+my=b 没有 区别。(不定方程和同余方程一般都有范围限制,这其实也很容易解决,就不说了)

其他
初等数论中最基础的就是 GCD 以及其相关问题了。实际上,更深层次的初等数论还包括: ◆中国剩余定理 ◆Miller-Rabin 素性测试 ◆pollard rho 算法

Jollwish 原创,转载请说明出处

Htfy96@qq.com 修改于 2012/11/21

-4-


推荐相关:

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

C语言实现欧几里得算法和扩展欧几里得算法_数学_自然...具体流程图如下: 开始 对 a 和 b 进行赋值 b=...2014教师资格材料分析辅... 2014小学教师资格考试《...


欧几里德算法及其扩展

欧几里德与扩展欧几里德算法欧几里德算法 欧几里德算法又称辗转相除法,用于计算...(由于 d | a) 首先看一个简单的例子: 5x=4(mod3) 解得 x = 2,5,8...


扩展欧几里德算法求逆元

扩展欧几里德算法求逆元_计算机硬件及网络_IT/计算机_专业资料。 扩展欧几里德...举例:求 12 模 67 的逆元。 由于 gcd(12, 67) = 1,故其逆元存在且...


算法设计与分析课后习题解答

b.有a可知计算gcd(31415,14142)欧几里德算法做了11次除法。 连续整数检测算法...6.给出一个长度为 n 的文本和长度为 m 的模式构成的实例,它是蛮力字符串...


基于扩展欧几里得算法的多项式互素

完成多项式技术后,将其运 用到多项式的扩展欧几里得算法中,实现对两个多项式寻找到使 u(x)f(x)+v(x)g(x)=1 成立的 v(x),u(x); 以下是多项式程序。 ...


ACM数论基础之扩展欧几里德详细证明

ACM数论基础之扩展欧几里德详细证明_数学_自然科学_...扩展欧几里德算法扩展欧几里德算法是用来在已知 a,...“中国余数定理”相关知识举个例子比如 n 除以 5 ...


RSA扩展欧几里德算法

扩展欧几里得算法描述 5页 免费R​S​A​扩​展​欧​几​里​德​算​法 暂无评价|0人阅读|0次下载|举报文档 R​S​A​扩​展​...


扩展欧几里德算法计算乘法逆元

程序分析 本程序只是很简单描述了一般情况下的扩展欧几里德算法乘法逆元, 当给出的两个数如果最 大公因数不为一时, 则无乘法逆元, 将他们的逆元都设置为 0...


算法设计与分析基础课后习题答案(中文版)

(m,n)=gcd(n,r) 6.对于第一个数小于第二个数的一对数字,欧几里得算法...6.给出一个长度为 n 的文本和长度为 m 的模式构成的实例,它是蛮力字符串...


同余式的欧几里得算法

改进的扩展欧几里得算法描... 2页 免费如...qn Qn Qk ? 2 具体计算步骤如下: 1. 2. 3....一个例子例如:解同余式 1215x ? 560(%2755) 。...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com