数论篇——欧几里得算法,扩展欧几里得算法,线性同余方程,

2020-07-24

欧几里得算法:

gcd(a,b)=gcd(b,a mod b)

证明:

a<b gcd(b,a mod b)=gcd(b,a)=gcd(a,b) 命题成立

a>=b 设a=q*b+r (0<=r<b) r=a mod b,对于a,b的任意公约数d 因为d|a , d|q *b ,所以d|(a-qb) 即d|r,因此d也是b,r的公约数,反之成立,估a,b的公约数集合和b a mod b的公约数集合相同,于是他们的最大公约数也相等

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

扩展欧几里得算法:

设 a和b不全为0,则存在整数x和y使得ax+by=gcd(a,b);

在b=0时gcd(a,b)=a,因为a*1+0 * 0=a所以此时的一组解为 x=1,y=0;

当b!=0时,递归求gcd(b,a%b),假设存在x,y满足

bx'+(a%b)y'=gcd(b,a%b)=gcd(a,b);

bx'+(a-a/b*b)y'=gcd(a,b)

ay'+b(x'-a/b*y')=gcd(a,b)

所以 x=y',y=x'-(a/b)y' 就得到了ax+by=gcd(a,b)

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

定理2:对于不定方程 ax+by=c当且仅当gcd(a,b)|c的时候,方程具有整数解。

线性同余方程:

给定整数a,b,m,求一个整数x满足a*x%m=b,或者给出无解,因其未知数的指数为1,所以我们称其为一次同余方程,也称线性同余方程,

相当于:a*x+m *y=b;当且仅当gcd(a,m)|b时方程恰好有gcd(a,m)模m个不同余的解,否则方程无解。

假设x0为方程ax%m=b的任意一解,则该方程对模m恰有d个不同的解,分别为xi=x0+i*(m/d)

(0<=i<=d-1)

定理:若gcd(a,m)=1,则称x的一个解为a模m的逆。


标题:数论篇——欧几里得算法,扩展欧几里得算法,线性同余方程,
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2020/07/24/1595597910928.html