数论-同余与扩展欧几里得详解(附例题及代码)

说明了对任何整数a、b和它们的最大公约数d

关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数

特别地，一定存在整数x,y，使ax+by=d成立

它的一个重要推论是：a,b互质的充分必要条件是存在整数x,y使ax+by=1.

由此，我们便可对式子进行化简

将同余式ax≡c(mod b)转化为ax+by=c(很重要，做题列方程化简几乎必定会用到，牢记)

充分必要条件也即充要条件，意思是说，如果能从命题p推出命题q，而且也能从命题q推出命题p ，则称p是q的充分必要条件，且q也是p的充分必要条件。

样例：

1 A=“三角形的三条边都相等”；B=“三角形的三个角都相等”。

A是B的充分必要条件；

2 A=“某人触犯了法律”；B=“应当依照刑法对他处以刑罚”。

A是B的必要不充分条件；（A触犯法律包含各种法，有刑法有民法；B已经确定是刑法。B属于A所以A是B的必要不充分条件）

3 A=“付了足够的钱”；B=“买到商店里的东西”。

A是B的必要不充分条件；（ A付够了钱 可以买的是车、房子等；但是B能买到商店里的东西一定是要付够钱）

ax1+by1=gcd(a,b)　　　ax2+by2=gcd(a,b)

可由此推出

ax1+by1=ax2+by2

a(x1-x2)=b(y2-y1)

因为gcd(a,b)为a,b的最大公因数，所以将 A=a/gcd(a,b)，B=b/gcd(a,b)，向下推出

A(x1-x2)=B(y2-y1)

此时A，B互质，继续向下推出

A(nB)=B(nA)

(x1-x2)=n*B

(y2-y1)=n*A

重点部分

这里从x入手，得

(x1-x2)=n*B

x1=x2+n*B

由此，我们推出了x解的通解公式 x=x0+n*B

同理，我们推出了y解的通解公式 y=y0-m*A

如果要求x的最小整数解,即x0,就为x0=x%B

如果我们要求的是 ax+by=c，还得先转化 x=x*c/gcd(a,b).

然后套入公式

B=b/gcd(a,b)

x0=x%(b/gcd(a,b))

证毕(博主已累成狗，点个推荐呗) 若还不清楚，可移步Ta的博客(讲的蛮详细的)

int exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=1;return a;}int gcd=exgcd(b,a%b,y,x);//没错，这玩意能求gcd    //不过c++是有系统函数求GCD的->__gcd(a,b);y-=a/b*x;return gcd;  }

(1).求解不定方程

(2).求解线性不定方程(线性同余方程)

(3).求解模的逆元

int exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=1;return a;}int gcd=exgcd(b,a%b,y,x);y-=a/b*x;return gcd;  }  int getinv(int a,int p){int x,y,gcd;gcd=exgcd(a,p,x,y);if(gcd==1){x=(x%p+p)%p;return x;}else{cout<<"a,p不互质"<

#include  #define int long long  using namespace std;  int x=0,y=0;  int exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;return a;}int g=exgcd(b,a%b,y,x);y-=a/b*x;return g;  }  signed main(){int a,b;cin>>a>>b;exgcd(a,b,x,y);cout<<(x%b+b)%b;return 0;  }