『数论』扩展欧几里得算法

『数论』扩展欧几里得算法

欧几里得算法

辗转相除计算两个数的最大公约数，求gcd(a,b)。

证明

设 a=b∗p+q ，则 gcd(b,q)|b ， gcd(b,q)|a ，故 gcd(b,q)|gcd(a,b)

同样 q=a−b∗p ，则 gcd(a,b)|q ，故 gcd(a,b)|gcd(b,q)

可得 gcd(a,b)=gcd(b,a) ，最终得到 gcd(a,b)=gcd(c,0)=c

代码

int gcd(int a, int b){ return

扩展欧几里得算法

存在整数对 (x,y) 使得 ax+by=gcd(a,b)

证明

设 a>b

当 b=0 时， a∗1+b∗0=a=gcd(a,b) ，此时 x=1 ， y=0

当 b!=0

a∗x1+b∗y1=gcd(a,b)

b∗x2+a%b∗y2=gcd(b,a%b)

由于 gcd(a,b)=gcd(b,a%b) ，所以有 a∗x1+b∗y1=b∗x2+a%b∗y2

将 a%b=a−(a/b)∗b

得到 a∗x1+b∗y1=a∗y2+b∗x2−(a/b)∗b∗y2

即 x1=y2,y1=x2−(a/b)∗y2

因此可以递归的定义 exgcd ，同样 b=0

代码

int extgcd(int a, int b, int &x, int &y){ int d = a; if(b != 0) { d = extgcd(b, a % b, y, x); y -= (a/b) * x; }else { x = 1, y = 0; } return

应用

求解不定方程

若 c%gcd(a,b)=0 ，则存在整数对 (x,y) ，使得 a∗x+b∗y=c

通过上面的方法可得到一组特解 x0 ， y0 使得 a∗x0+b∗y0=gcd(a,b) ，那么如何在无穷多个解中求出 x ， y

证明

首先 a∗x0+a∗k∗b/gcd(a,b)+b∗y0−a∗k∗b/gcd(a,b)=gcd(a,b)

即 a∗(x0+k∗b/gcd(a,b))+b∗(y0−k∗a/gcd(a,b))=gcd(a,b)

通解为 x=x0+k∗b/gcd(a,b) ， y=y0−k∗a/gcd(a,b) ，其中 k=...−2,−1,0,1,2...

在所有解中最小的正整数为 (x0+b/gcd(a,b))%(b/gcd(a,b))

所以对于方程 a∗x+b∗y=c ，最小正整数解（以x为例）为 (x0∗c/gcd(a,b)+b/gcd(a,b))%(b/gcd(a,b))

注意：若 b 为负数，需将 b

代码

int cal(int a, int b, int c){ int x, y; int gcd = extgcd(a, b, x, y); if(c % gcd != 0) return -1; x *= c/gcd; b /= gcd; if(b < 0) b = -b; int ans = x % b; if(ans <= 0) ans += b; return

同余方程

根据上面的内容，我们可以得到：

a∗x≡b(mod n) ，转化为 a∗x+n∗y=b ，当 b%gcd(a,n)=0 时，方程有 gcd(a,n)a∗x≡1(mod n) ，如果 gcd(a,n)=1

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。