【数学】贝祖定理和扩展欧几里得算法

2021-06-28 约 1171 字预计阅读 3 分钟

贝祖定理（裴蜀定理）

在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理，裴蜀定理得名于法国数学家艾蒂安·裴蜀。裴蜀定理说明了对任何整数$a$、$b$和它们的最大公约数 $d$ ，关于未知数 $x$以及$ y$ 的线性的丢番图方程（称为裴蜀等式）。

裴蜀定理（或贝祖定理） 说明了对任何整数$a$、$b$和它们的最大公约数$d$，关于未知数$x$和$y$的线性不定方程（称为裴蜀等式）：若$a$,$b$是整数,且$gcd(a,b)=d$，那么对于任意的整数$x,y,ax+by$都一定是$d$的倍数，特别地，一定存在整数$x,y$，使$ax+by=d$成立。

它的一个重要推论是：$a,b$互质的充分必要条件是存在整数$x,y$，使$ax+by=1$。

扩展欧几里得算法

扩展欧几里得算法（英语：Extended Euclidean algorithm） 是欧几里得算法（又叫辗转相除法）的扩展。已知整数$a$、$b$，扩展欧几里得算法可以在求得$a$、$b$的最大公约数的同时，能找到整数$x$、$y$（其中一个很可能是负数） ，使它们满足贝祖等式 $$ ax+by=gcd(a,b) $$ 如果$a$是负数，可以把问题转化成 $$ |a|(-x)+bx=gcd(|a|,b) $$ 然后令$x'=(-x)$。

扩展欧几里得算法的实现可以通过收集辗转相除法中每一步等式的解，反推原等式的解。

扩展欧几里得算法可以用来计算数字的乘法逆元(也叫模反元素或模逆元)，而模反元素在RSA加密算法中有举足轻重的地位。

扩展欧几里得算法的推导流程和实现

扩展欧几里得算法的推导流程

在辗转相除法求解两个数字$a,b\ (a>b)$ 的最大公约数$gcd(a,b)$时，我们用到的是如下的递推关系： $$ gcd(a,b) \equiv gcd(b,a\bmod b) $$ 现在我们需要求解$ax+by\equiv gcd(a,b)$的整数特解，同样可以利用这个递推关系。

设$ax+by\equiv gcd(a,b)$方程的整数解为$(x_0,y_0)$；等式右侧对应的方程$bx+(a\bmod b)y\equiv gcd(a,a\bmod b)$的整数解为$(x_1,y_1)$： $$ ax_0+by_0=bx_1+(a\bmod b)y_1 $$ 其中 $$ a\bmod b = a-\lfloor \frac{a}{b}\rfloor \cdot b $$ 将其代入原等式 $$ ax_0+by_0 \equiv bx_1+(a-\lfloor \frac{a}{b}\rfloor \cdot b)y_1 $$ $$ ax_0+by_0 \equiv ay_1+b(x_1-\lfloor \frac{a}{b}\rfloor \cdot y_1) $$ 由此可得整数解$(x_0,y_0)$和整数解$(x_1,y_1)$的关系为： $$ x_0 = y_1 $$ $$ y_0 = x_1-\lfloor \frac{a}{b}\rfloor \cdot y_1 $$ 而且，我们知道在辗转相除法的终止条件处，除数大小等于$gcd(a,b)$，我们一定会得到一个整数特解$(0,1)$。

因此，由递推公式和终止条件处的整数特解，可以反推得到原方程$ax+by\equiv gcd(a,b)$的整数特解。

补充：方程通解

上述求出来的是原方程的一个整数特解。原方程整数通解的形式为： $$ x = x_0+\frac{b}{gcd(a,b)}\cdot t $$ $$ y = y_0-\frac{a}{gcd(a,b)}\cdot t $$ 其中$t$为整数。

扩展欧几里得算法的代码实现

from typing import Tuple
# 递归实现扩展欧几里得算法
def exEuclid(a, b) -> Tuple:
    '''
    return (x0,y0,gcd) contain a solution of ax + by == gcd(a,b) and gcd(a,b)
    Notice:a should greater than b,otherwise will return a solution of bx + ay == gcd(a,b)
    '''
    (a, b) = (a, b) if a >= b else (b, a)
    if b == 0 or a % b == 0:
        return (0, 1, b)
    (x1, y1, gcd) = exEuclid(b, a % b)
    x0, y0 = y1, x1-(a//b)*y1
    return (x0, y0, gcd)

目录