《算法导论学习笔记》-扩展欧几里得原理

扩展欧几里得算法的原理

扩展欧几里得算法即欧几里得算法的一个变形。

我们先来看《算法导论》上的一段伪代码。

1
2
3
4
5
6
EXTENDED-EUCLID
if b==0
return(a,1,0)
else(d_,x_,y_)=EXTENDED-EUCLID(b,a mod b)
(d,x,y)=(d_,y_,x_-round(a/b)*y_)
return (d,x,y)

我们可以发现递归到最后是求出了这样一个:使得$a=ax+by$满足的x和y。也就是1,0.
最后通过$d’=bx’+(a \mod b)y’$推出$d=ax+by$。
至于这个推论过程为什么成立,我们可以发现:
当$x=y’$和$y=x’-round(a/b)y’$时显然成立。

文章目录
  1. 1. 扩展欧几里得算法的原理