《算法导论学习笔记》-裴蜀定理及其扩展的证明

裴蜀等式及其扩展

裴蜀等式是

$exgcd$的骨髓,是建立在$gcd$,它保证了$exgcd$的有解性。
裴蜀等式
存在让$ax+by=gcd(a,b)$的$x,y$;
扩展
$gcd(a,b)$是${ax+by:x,y∈Z}$的最小正元素。

证明

先设$s$是这个集合中最小正元素
设$q=\lfloor \frac as\rfloor$。
带余除法我们可以知道会有$a\mod s=a-qs$
因为$s$是那个集合中的元素,所以一定可以表示成$ax+by$的形式,
$\therefore原式=a-q(ax+by)=a(1-qx)+b(-qy)$
显而易见,我们发现$a\mod s$被我们表示成$ax+by$的形式,其中$x=(1-qx)$,$y=-qy$。都是整数,符合要求。
因此$a\mod s$也是这个集合中的一个元素。

因为任意数对一个数取模,结果肯定小于那个模数,也就是$0\leq a\mod s<s$,而前面我们又令$s$是最小正元素,所以$a\mod s$就一定是0了。所以$s$能够被$a$整除。

同样的,我们可以证明$s$能够被$b$整除。

$\therefore$我们可以知道$s$是$a$和$b$的公约数。
$\therefore gcd(a,b)\ge s$,而且$gcd(a,b)$能整除$s$。

又因为,$gcd(a,b)$能同时被$a$和$b$整除,所以$gcd(a,b)$能被$ax+by$整除,也就是能被$s$整除。由于$s>0,\therefore gcd(a,b)\le s$
所以$gcd(a,b)=s$
$\therefore 得证$

文章目录
  1. 1. 裴蜀等式及其扩展
  2. 2. 证明