定义
形如ax≡c (mod b)的方程被称为线性同余方程
前置知识
辗转相除法
为了求解线性同余方程,先要介绍欧几里得求解最大公约数的算法,又称为辗转相除法:
gcd(a,b)=gcd(b,a mod b) (a > b)它的简要证明如下:
假设:a=bk+c,k∈Z
那么显然有:c=a mod b=a−bk
令:d∣a,d∣b
观察等式:cd=ad−bdk
因为:ad,bd,k∈Z
所以:cd∈Z
即:d∣c
上面的证明说明了:凡是a、b的公约数,同时也是b、a mod b的公约数
同理可证:凡是b、a mod b的公约数,同时也是a、b的公约数
既然它们的公约数都相同,那么最大公约数也相同,证毕
由于规定gcd(a,0)=a,所以辗转相除法可以递归进行,当发现a mod b=0时就退出即可
最大公约数与质因数分解
最大公约数也可以从质因数分解的角度来考虑:
a=n∏i=0paii, b=m∏i=0pbii∀i, pi is primegcd(a,b)=max(n,m)∏i=0pmin(ai,bi)i证明如下:
令:d∣a
那么对于d的质因数分解形式:
O∏i=0pdii显然有:di<=ai
同理有:di<=bi
即:di<=min(ai,bi)
假设:d=gcd(a,b),则:d必须尽量大
所以:di=min(ai,bi)
此外最大公约数还有一个性质:
gcd(ac,bc)=c∗gcd(a,b) (c>1)利用最大公约数的质因数分解形式即可完成这个性质的证明:
考虑a、b、c的质因数分解形式:
a=n∏i=0paii, b=m∏i=0pbii, c=O∏i=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)i∗pcii= c∗max(n,m,O)∏i=0pmin(ai,bi)i= c∗gcd(a,b)
用上面这个性质可以获得下面这个推论:
d=gcd(a,b), a=k1d, b=k2dgcd(k1,k2)=1裴蜀定理
裴蜀定理的内容是:
∀a,b∈Z, gcd(a,b)=dexist x,y∈Z,ax+by=c⟺d∣c证明如下:
因为:d=gcd(a,b)
所以:d∣a,d∣b
所以:∀x,y∈Z,d∣ax+by
假设:s是ax+by的最小正值,令:q=⌊as⌋
则:r=a%s=a−q(ax+by)=a(1−qx)+b(−qy)
说明:r也满足ax+by的形式
由于:r∈[0,s),并且:s是ax+by的最小正值
所以:r=0
所以:s∣a,同理:s∣b
而由于:d=gcd(a,b),所以:d≥s
又因为:d∣ax+by,即:d∣s
由于:s>0,所以:d≤s
由此得出结论:d=s
既然d是ax+by的最小正值,而又显然有:d∣ax+by,所以:当d∤c时,方程无解
裴蜀定理还有一个重要的推论:
∀a,b∈Z,(a=0&&b=0)=falseexist x,y∈Z,ax+by=gcd(a,b)证明如下:
- 如果a=0或者b=0:
此时原方程转化为ax=a或者by=b,定理显然成立
- 否则:
由于gcd(a,b)=gcd(a,−b),不妨假设:a≥b,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])...rn−3=qn−1rn−2+rn−1rn−2=qnrn−1+rnrn−1=qn+1rn+0即:
gcd(a1,b1)=gcd(b1,r1)=...=gcd(rn−1,rn)=1利用辗转相除法的性质:
gcd(rn−1,rn)=1gcd(qn+1rn,rn)=1rn∗gcd(qn+1,1)=1rn=1得到了rn=1之后,我们考虑把这个结果回代,消去rn:
rn−2=qnrn−1+1也即:
1=rn−2−qnrn−1继续回代,消去rn−1:
1=rn−2−qn(rn−3−qn−1rn−2)=(1+qnqn−1)rn−2−qnrn−3重复上述过程,逐步消去rn−2…r1,最终可以获得形如: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+(a−kb)y1=bx1+ay1−kby1=ay1+b(x1−ky1)(k=⌊ab⌋)这样可以考虑在函数向下递归之后回溯时更新x和y,用来求解一组满足方程: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;
}
这里注意一点,没有必要考虑a和b的大小关系
假设a<b,在第一次扩展欧几里得中,函数会如下运行:
gcd(a,b)=gcd(b,a%b)=gcd(b,a) (a<b)函数就这样自动完成了a和b的交换
解法
定理一
方程ax+by=c与方程ax≡c(mod b)等价,有整数解的充要条件是gcd(a,b)∣c
方程的等价性显然,有整数解的充要条件参考裴蜀定理
定理二
若x0,y0是方程:ax+by=c的一组特解,那么:方程的通解可以表示为x0+bt,y0−at (t∈Z)
为了满足x0+bt,y0−at∈Z,显然: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;
}
来做第一个留言的人吧!