扩展欧几里得算法及贝祖定理的证明

作者: M_lear | 来源:发表于2019-01-25 16:59 被阅读0次

扩展欧几里得算法及贝祖定理的证明
组合数求解
学习列表
扩展欧几里得算法
扩展欧几里得算法
算法学习(2)----丢番图方程
扩展欧几里德算法
扩展欧几里得算法
365.水壶问题
无标题文章

欧几里得算法

公式表述： $gcd(a,b)=gcd(b,a\%b)$
证明：
a 可以表示为 a = kb + r，r = a%b
假设 d 是 (a,b) 的一个公约数，则有
d|a，d|b，而 r = a – kb，因此 d|r
所以 d 也是 (b,a%b) 的公约数.

除了上面这个经典算法，还有 stein 算法用来求解最大公约数，只有整数的移位和加减法，比欧几里得算法在大整数上更有优势，可以去了解一下。

扩展欧几里得算法求解贝祖等式

贝祖定理（一般形式）

对于不全为 0 的自然数 a，b，则必然存在整数 x ， y （不唯一）满足等式 $ax+by=gcd(a,b)$

上面的等式就称做贝祖等式。

扩展欧几里得算法能够求解贝祖等式的正确性证明

设 a > b

当 b = 0 时，gcd(a,b) = a
贝祖等式即 ax = a，解得 x = 1，y 可以取 y = 0
当 b > 0 时，
假设 a，b 的贝祖等式的解为 $x_1，y_1$ ，即 $a\cdot x_1+b\cdot y_1=gcd(a,b)\cdots\cdots1$
b，a%b 的贝祖等式的解为 $x_2，y_2$ ，即 $b\cdot x_2+a\%b\cdot y_2=gcd(b,a\%b)\cdots\cdots2$
由欧几里得算法可知 $gcd(a,b)=gcd(b,a\%b)$
故 $a\cdot x_1+b\cdot y_1=b\cdot x_2+a\%b\cdot y_2$
即 $a\cdot x_1+b\cdot y_1=b\cdot x_2+(a-\lfloor a/b\rfloor\cdot b)\cdot y_2=a\cdot y_2+b\cdot(x_2-\lfloor a/b\rfloor \cdot y_2)$
由恒等关系可得 $x_1=y_2;y_1=x_2-\lfloor a/b\rfloor\cdot y_2$ 即贝祖等式 1 的解可以由贝祖等式 2 的解得到，这是一个递归求解的过程，并且随着对 a，b 进行辗转相除，贝祖等式的系数会越来越小，直至变为情况1，而情况1贝祖等式的解是有具体的值的，即 x = 1，y = 0。然后进行回溯计算，最终可以得到 $x_1，y_1$ 。
C++代码如下：

\\exGcd函数返回a，b最大公约数。贝祖等式的整数解为引用参数x，y
int exGcd(int a, int b, int& x, int& y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    int r = exGcd(b,a%b,x,y);
    int t = x;
    x = y;
    y = t - a/b*y;
    return r;
}

贝祖定理（更原始形式）的证明

若整数 a，b 互质，则存在整数解 x，y 满足 ax + by = 1

证明：
设 $X，Y$ 分别是使得 $aX+bY > 0$ 的整数集合，
令 $s = min\{aX + bY\} > 0$ ，假设此时 $X=x_1，Y=y_1$
则有 $ax_1+by_1=s$
假设 $a$ 除以 $s$ 的商为 $k$ ，余数为 $r(0\le r < s)$
则有 $r=a-ks=a-k(ax_1+by_1)=a(1-kx_1)+b(-ky_1)$
但是因为其中 $1-kx_1,-ky_1\in Z$ ，所以必须有 $r=0$
否则 $r<s$ 与假设 $s = min\{aX + bY\} > 0$ 矛盾
故 $s|a$ ，同理可得 $s|b$
即 $s$ 为 $a，b$ 的公约数，又 $a，b$ 互质
所以有 $s = 1$
即存在整数 $x，y$ 使得 $a\cdot x+b\cdot y=1$ 成立。