欧几里得与扩展欧几里得

补博客ing……

最大公约数

先说最大公约数的概念。

关于约数的概念已经在素数中提及过,就不再讨论。

公约数集合,是指一组数中共同的约数的集合。

那么最大公约数,顾名思义,就是这个集合中最大的数,用gcdgcd表示。

如果两个数 aabb 满足 gcd(a,b)=1\gcd(a, b) = 1 ,我们称 aabb 互质。

怎么求最大公约数呢?

欧几里得算法

如果我们有两个已知的数a,ba,b,怎么去求它的最大公约数呢?

首先,我们不妨a>ba>b,那么很容易的得知,如果bbaa的约数,那么gcd(a,b)=bgcd(a,b)=b

再讨论不能整除的情况,我们可以把aa看作a=b×q+r    (r<b)a=b \times q +r \;\; (r<b),通过证明,可以得知gcd(a,b)=gcd(b,amodb)gcd(a,b)=gcd(b,a \bmod b)

下面是证明

证明

1
2
反之亦然同理,推论自然成立,略去过程QED,由上可知证毕  
即得易见平凡,仿照上例显然,留作习题答案略,读者自证不难

咳咳……

code

所以我们得到了这个代码

1
2
3
4
int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}

扩展欧几里得定理

用于求ax+by=gcd(a,b)ax+by=gcd(a,b)的一组可行解。

证明:

ax1+by1=gcd(a,b)ax_1+by_1=\gcd(a,b)

bx2+(amodb)y2=gcd(b,amodb)bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)

由欧几里得定理可知: gcd(a,b)=gcd(b,amodb)\gcd(a,b)=\gcd(b,a\bmod b)

所以 ax1+by1=bx2+(amodb)y2ax_1+by_1=bx_2+(a\bmod b)y_2

又因为 amodb=a(ab×b)a\bmod b=a-(\lfloor\frac{a}{b}\rfloor\times b)

所以 ax1+by1=bx2+(a(ab×b))y2ax_1+by_1=bx_2+(a-(\lfloor\frac{a}{b}\rfloor\times b))y_2

ax1+by1=ay2+bx2ab×by2=ay2+b(x2aby2)ax_1+by_1=ay_2+bx_2-\lfloor\frac{a}{b}\rfloor\times by_2=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)

因为 a=a,b=ba=a,b=b ,所以 x1=y2,y1=x2aby2x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2

code

x2,y2x_2,y_2 不断代入递归求解直至 GCD(最大公约数,下同)为 0 递归 x=1,y=0 回去求解。

1
2
3
4
5
6
7
8
9
10
11
12
int Exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int d = Exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - (a / b) * y;
return d;
}

函数返回的值为 GCD,在这个过程中计算 x,yx,y 即可。

文章作者: Langlangago
文章链接: https://langlangago.xyz/2019/08/17/欧几里得与扩展欧几里得/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Langlangago's blog

评论