[数学基础] 4 欧几里得算法&扩展欧几里得算法

2022/5/10 11:02:32

本文主要是介绍[数学基础] 4 欧几里得算法&扩展欧几里得算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

欧几里得算法

欧几里得算法基于的性质:

  1. 若\(d|a, a|b\),则\(d|(ax+by)\)

  2. \((a,b)=(b,a~mod~b)\)

第二条性质证明:

\(\because a~mod~b=a-\lfloor \frac{a}{b} \rfloor\times b\),令\(c=\lfloor \frac{a}{b} \rfloor\)

则问题等价于证明\((a,b)=(b,a-c\times b)\)

这个证明方法就和裴蜀定理的证明差不多。

证明:令\(d=gcd(a,b)\),则\(d|a,d|b\),易得\(d|(a-c\times b)\)。则\(d\)为\(b,(a-c\times b)\)的公因数。

那么令\(D=(b,a-c\times b)\),\(d\leq D\)。

\(D|b,D|(a-c\times b)\),易得\(D|a\),则\(D\leq (a,b)=d\)。

因此\(d=D\),即\(d=gcd(b,a-c\times b)\)

欧几里得算法模板

int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}

扩展欧几里得算法

1. 前置知识-裴蜀定理

裴蜀定理:\(\forall a,b\in \Z\),令\(d=(a,b)\),那么对于任意的整数\(x,y\in \Z\),\(ax+by=kd\)。特别的,一定\(\exist x,y\),使得\(ax+by=d\)成立。

丢番图方程\(ax+by=m\)有解,当且仅当\(m\)是\(d\)的倍数。丢番图方程有解时必然有无穷多个解,每组解\(x,y\)都称为裴蜀数,可用辗转相除法求得。

证明:

(前半句)\(\because d|a,d|b\),\(\therefore \forall x,y\in Z, d|(ax+by)\)

(特别的...)设\(s\)为\(ax+by\)的最小正值,令\(q=\lfloor \frac{a}{s} \rfloor\),\(r=a ~mod ~s\)。

则\(r=a-\lfloor \frac{a}{s} \rfloor\times s=a-q\times(ax+by)=a(1-qx)+b(-qy)\),即\(r\)也为\(a,b\)的线性组合

\(\because r=a~mod~s\) ,\(\therefore 0\leq r <s\)

又\(s\)为\(ax+by\)的最小正值,可得\(r=0\),即\(a ~mod~s=0\)。

\(\therefore s|a\),再设\(r_2=b~mod~s\),同理可得\(s|b\)。因此\(s\)为\(a,b\)的公因子,\(d\geq s\)。

\(\because d|a,d|b,s=ax+by\),\(\therefore d|s\),\(d\leq s\)。

因此\(d=s\),命题得证。

推论1:\((a,b)=1\)的充分必要条件是\(\exist x,y\in Z, s.t.~~ax+by=1\)。

推论2:裴蜀等式也可以用来给最大公约数定义:\(d\)其实就是最小的可以写成\(ax + by\)形式的正整数。

推论2:设\(a_1,a_2,...,a_n\)为\(n\)个整数,\(d\)是它们的最大公约数,那么\(\exist x_1,x_2,...,x_n\),使得\(a_1x_1+a_2x_2+...+a_nx_n=d\)成立。特别的,若\(a_1,a_2,...,a_n\)是互质的(不是两两互质),那么\(\exist x_1,x_2,...,x_n\),使得\(a_1x_1+a_2x_2+...+a_nx_n=1\)成立。

2. 扩展欧几里得算法

如何用扩展欧几里得算法求裴蜀数?

假如要求解的不定方程(又名丢番图方程)为\(ax+by=m\)

我们现在先求解不定方程\(ax+by=d\),其中\(d=(a,b)\),\(d|m\)。

由欧几里得算法性质1,2可知\((a,b)=(b,a~mod~b)=(b, a-\lfloor \frac{a}{b} \rfloor\times b)\)

若\(ax_1+by_1=d\)有解,则\(by_2+(a~mod~b)x_2=d\)一定有解,即\(by_2+(a-\lfloor \frac{a}{b} \rfloor\times b)x_2=d\)有解。

化简得\(ax_2+b(y_2-\lfloor \frac{a}{b} \rfloor\times x_2)=d\),那么\(x_1=x_2,y_1=y_2-\lfloor \frac{a}{b} \rfloor\times x_2\)。

于是可以递归进行操作,当\(b'=0\)时,\((a',0)=d\),也就是\(a'=d\),此时\(x=1,y=0\)为一组平凡解,再不断带回,即可得到不定方程的一组特解,设此特解为\(\{x_1,y_1\}\)。则通解即为\(\{x_1+k\times\frac{b}{d}, y_1-k\times\frac{a}{d}, k\in \Z\}\)

证明通解是方程的解:

\(ax+by=a\times(x_1+k\times\frac{b}{d})+b\times(y_1-k\times\frac{a}{d})\\=ax_1+by_1+k\times (\frac{ab}{d}-\frac{ab}{d})=d\)

因此,通解是可以使等式成立的。

那么同理,\(ax+by=m\),通解也是\(\{x_0+k\times \frac{b}{d}, y_0-k\times \frac{a}{d}\}\)。

  • 代码
int exgcd(int a, int b, int &x, int &y){
    if (!b){
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a%b, y, x);
    y -= a / b * x;
    return d;
}


这篇关于[数学基础] 4 欧几里得算法&扩展欧几里得算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程