线性同余方程

written by oneman233
2021-05-25

定义

形如axc (mod b)的方程被称为线性同余方程

前置知识

辗转相除法

为了求解线性同余方程,先要介绍欧几里得求解最大公约数的算法,又称为辗转相除法:

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

它的简要证明如下:

假设:a=bk+c,kZ

那么显然有:c=a mod b=abk

令:da,db

观察等式:cd=adbdk

因为:ad,bd,kZ

所以:cdZ

即:dc

上面的证明说明了:凡是ab的公约数,同时也是ba mod b的公约数

同理可证:凡是ba mod b的公约数,同时也是ab的公约数

既然它们的公约数都相同,那么最大公约数也相同,证毕

由于规定gcd(a,0)=a,所以辗转相除法可以递归进行,当发现a mod b=0时就退出即可

最大公约数与质因数分解

最大公约数也可以从质因数分解的角度来考虑:

a=ni=0paii, b=mi=0pbiii, pi  is  primegcd(a,b)=max(n,m)i=0pmin(ai,bi)i

证明如下:

令:da

那么对于d的质因数分解形式:

Oi=0pdii

显然有:di<=ai

同理有:di<=bi

即:di<=min(ai,bi)

假设:d=gcd(a,b),则:d必须尽量大

所以:di=min(ai,bi)

此外最大公约数还有一个性质:

gcd(ac,bc)=cgcd(a,b) (c>1)

利用最大公约数的质因数分解形式即可完成这个性质的证明:

考虑abc的质因数分解形式:

a=ni=0paii, b=mi=0pbii, c=Oi=0pcii

那么有:

gcd(ac,bc)= max(n,m,O)i=0pmin(ai+ci,bi+ci)i= max(n,m,O)i=0pmin(ai,bi)+cii= max(n,m,O)i=0pmin(ai,bi)ipcii= cmax(n,m,O)i=0pmin(ai,bi)i= cgcd(a,b)

用上面这个性质可以获得下面这个推论:

d=gcd(a,b), a=k1d, b=k2dgcd(k1,k2)=1

裴蜀定理

裴蜀定理的内容是:

a,bZ, gcd(a,b)=dexist x,yZ,ax+by=cdc

证明如下:

因为:d=gcd(a,b)

所以:da,db

所以:x,yZ,dax+by

假设:sax+by的最小正值,令:q=as

则:r=a%s=aq(ax+by)=a(1qx)+b(qy)

说明:r也满足ax+by的形式

由于:r[0,s),并且:sax+by的最小正值

所以:r=0

所以:sa,同理:sb

而由于:d=gcd(a,b),所以:ds

又因为:dax+by,即:ds

由于:s>0,所以:ds

由此得出结论:d=s

既然dax+by的最小正值,而又显然有:dax+by,所以:dc时,方程无解

裴蜀定理还有一个重要的推论:

a,bZ,(a=0&&b=0)=falseexist x,yZ,ax+by=gcd(a,b)

证明如下:

  1. 如果a=0或者b=0

此时原方程转化为ax=a或者by=b,定理显然成立

  1. 否则:

由于gcd(a,b)=gcd(a,b),不妨假设:ab,a>0,b>0

令:d=gcd(a,b)

对于ax+by=d,两边同时除以d可得:a1x+b1y=1

由gcd性质的推论,此时有:gcd(a1,b1)=1,下面试图证明这个式子

把辗转相除法的过程展开:

a1=q1b1+r1 (r1[0,b1))b1=q2r1+r2 (r2[0,r1])...rn3=qn1rn2+rn1rn2=qnrn1+rnrn1=qn+1rn+0

即:

gcd(a1,b1)=gcd(b1,r1)=...=gcd(rn1,rn)=1

利用辗转相除法的性质:

gcd(rn1,rn)=1gcd(qn+1rn,rn)=1rngcd(qn+1,1)=1rn=1

得到了rn=1之后,我们考虑把这个结果回代,消去rn

rn2=qnrn1+1

也即:

1=rn2qnrn1

继续回代,消去rn1

1=rn2qn(rn3qn1rn2)=(1+qnqn1)rn2qnrn3

重复上述过程,逐步消去rn2r1,最终可以获得形如:1=a1x+b1y的等式

这说明:方程1=a1x+b1y有解,也就证明了:gcd(a1,b1)=1

扩展欧几里得

实际上裴蜀定理的证明过程就是扩展欧几里得算法的思路,考虑以下两个等式:

ax+by=gcd(a,b)bx1+(a%b)y1=gcd(b,a%b)=gcd(a,b)

则有:

ax+by=bx1+(a%b)y1=bx1+(akb)y1=bx1+ay1kby1=ay1+b(x1ky1)(k=ab)

这样可以考虑在函数向下递归之后回溯时更新xy,用来求解一组满足方程:ax+by=gcd(a,b)的解

c实现代码如下:

/*
    返回值是最大公约数
*/
ll exgcd(ll a,ll b,ll *x,ll *y) {
	if(!b) {
		*x=1ll;
		*y=0ll;
		return a;
	}
	ll ret=exgcd(b,a%b,x,y);
	ll tmp=*x-a/b*(*y);
	*x=*y;
	*y=tmp;
	return ret;
}

这里注意一点,没有必要考虑ab的大小关系

假设a<b,在第一次扩展欧几里得中,函数会如下运行:

gcd(a,b)=gcd(b,a%b)=gcd(b,a) (a<b)

函数就这样自动完成了ab的交换

解法

定理一

方程ax+by=c与方程axc(mod b)等价,有整数解的充要条件是gcd(a,b)c

方程的等价性显然,有整数解的充要条件参考裴蜀定理

定理二

x0,y0是方程:ax+by=c的一组特解,那么:方程的通解可以表示为x0+bt,y0at (tZ)

为了满足x0+bt,y0atZ,显然:t的最小值为:1gcd(a,b)

这也就意味着:x的最小正整数解为x0+bgcd(a,b)

注意一点:特解x是正整数时就不需要加上bgcd(a,b)

完整c代码如下:

#include <stdio.h>
typedef long long ll;

ll exgcd(ll a,ll b,ll *x,ll *y) {
	if(!b) {
		*x=1ll;
		*y=0ll;
		return a;
	}
	ll ret=exgcd(b,a%b,x,y);
	ll tmp=*x-a/b*(*y);
	*x=*y;
	*y=tmp;
	return ret;
}

int lieq(ll a,ll b,ll c,ll *x,ll *y) {
	ll d=exgcd(a,b,x,y);
	if(c%d) return 0;
	(*x)*=c/d;
	(*y)*=c/d;
	if(*x<=0) (*x)+=b/d;
	return 1;
}

ll a,b;

int main() {
	scanf("%lld%lld",&a,&b);
	ll x=0,y=0;
	lieq(a,b,1,&x,&y);
	printf("%lld",x);
	return 0;
}

测试题目:#2605. 「NOIP2012」同余方程

参考

  1. 最大公约数
  2. GCD from Prime Decomposition
  3. 裴蜀定理
  4. 线性同余方程
0 条评论
未登录用户
支持 Markdown 语法

来做第一个留言的人吧!