数论入门:斐蜀定理与拓展欧几里得算法

斐蜀定理

内容

斐蜀定理又叫贝祖定理，它的内容是这样的：

若$a,b\in N$,那么对于任意x，y，方程$ax+by=gcd(a,b)*k(k\in N)$一定有解，且一定有一组解使$ax+by=gcd(a,b)$

推论

a，b互素的充要条件是方程$ax+by=1$有整数解。

证明

令$d=gcd(a,b)$，则$d|a,d|b$

那么就能得到$d|(ax+by)$

于是我们设s为$ax+by$能得到的最小正整数值，则$d|s$。

令$q=a\div s$(此处为整除),$r=a\mod s$，则$a=qs+r$。

->$r=a-qs$

->$r=a-q(ax+by)$

->$r=(1-qx)a+b(-qy)$

则通过观察可以发现r也是一个关于a,b的线性组合，其中$x=(1-qx),y=(-qy)$

因为$0\leq r < s$,又因为s是a,b线性组合所能得到的最小自然数，那么r既然比s小，r只能等于0.

所以既然余数为0就说明$s|a$,同理可证明$s|b$，所以能得到$s|(ax+by)$。

于是就有$s|d$,又因为上文提到了$d|s$，所以得到$s==d$

由于s是$ax+by$所得到任意值的集合中的最小者，又因为s=d，d=gcd(a,b)所以得到

$ax+by=gcd(a,b)$

证明完毕

拓展欧几里得算法

内容

所谓拓展欧几里得算法，那一定是跟欧几里得算法有一定关系的，拓展欧几里得算法所研究的问题是，讨论如何求满足斐蜀定理的一组方程的解。

方法

下面直接给出代码

///inv,x,y应在外部定义,d为gcd(a,b)
///解整数方程:ax+by=gcd(a,b);
void exgcd(ll a,ll b,ll& inv,ll& x,ll& y)
{
    if(b)
    {
        exgcd(b,a%b,inv,x,y);
        ll temp=x;
        x=y;
        y=temp-a/b*y;
    }
    else
    {
		inv=a;
        x=1;
        y=0;
    }
}

证明

假设a>b:

Ⅰ.当b=0时，gcd(a,b)=a，于是方程就变成了$ax=gcd(a,b)=a$，易知x=1,那么当x=1,y=0，时就得到了方程的一组解。

Ⅱ.设两方程:

$ax_1+by_1=gcd(a,b)$

$bx_2+(a\mod b)y_x=gcd(b,a\mod b)$

有欧几里得算法得$gcd(a,b)=gcd(b,a\mod b)$ 于是得到:

$ax_1+by_1=bx_2+(a\mod b)y_2$.

其中$a\mod b=a-a\div b\times b$(此处为整除)，带入原式得到:

$ax_1+by_1=bx_2+ay_2-a\div b\times y_2\times b$

通过移项得到:

$ax_1+by_1=ay_2+b(x_2-a\div b\times y_2)$

则可以得到:

xxxxxxxxxx108 1#include 2#include 3#include 4#include 5#include 6#include 7using namespace std;8typedef long long ll;9#define MAXN 1510ll t;11ll n,m;12ll k;13ll a[MAXN];14ll r[MAXN];1516//唯一分解定理将mod分解为素数17ll fj(ll n)18{19 int c=0;20 for(int i=2;i<=n;i++)21 {22 while(n%i==0)23 {24 a[c++]=i;25 n/=i;26 }27 }28 return c;29}3031//快速乘取模32ll mul(ll a,ll b,ll mod)33{34 ll res=0;35 while(b)36 {37 if(b&1)res=(res+a)%mod;38 a=(a+a)%mod;39 b>>=1;40 }41 return res;42}43//计算n！%mod44ll fact(ll n,ll mod)45{46 ll res=1;47 for (int i = 1; i <= n; ++i) {48 res=(res*i)%mod;49 }50 return res;51}52void exgcd(ll a,ll b,ll &x,ll &y,ll &d)53{54 if(!b)55 {56 d=a;57 x=1;58 y=0;59 } else{60 exgcd(b,a%b,y,x,d);61 y-=x*(a/b);62 }63}64//用exgcd计算t模mod的逆元65ll inv(ll t,ll mod)66{67 ll d,x,y;68 exgcd(t,mod,x,y,d);69 return d==1?(x%mod+mod)%mod:-1;70}71//计算C(n,m)%mod:C(n,m)%mod=(n!/[m!*(n-m)!])%mod=n!%mod*inv(m!,mod)%mod*inv((n-m)!,mod)%mod72ll comb(ll n,ll m,ll mod)73{74 if(m<0||m>n)return 0;75 return fact(n,mod)inv(fact(m,mod),mod)%modinv(fact(n-m,mod),mod)%mod;76}77//lucas定理:C(n,m)%mod=C(n/mod,m/mod)C(n%mod,m%mod)%mod78ll lucas(ll n,ll m,ll mod)79{80 return m?lucas(n/mod,m/mod,mod)comb(n%mod,m%mod,mod)%mod:1;81}8283//中国剩余定理求解C(n,m)%mod=C(n,m)%(a1a2a3…)(ai为素数)84ll china(ll n,ll *d,ll *m)85{86 ll M = 1, ret = 0;87 for(int i = 0; i < n; i ++) M *= m[i];88 for(int i = 0; i < n; i ++)89 {90 ll w = M / m[i];91 ret = (ret + mul(w * inv(w, m[i]), d[i], M)) % M;92 }93 return (ret + M) % M;94}95int main()96{97 cin>>t;98 while(t–)99 {100 cin>>n>>m>>k;101 ll num=fj(k);//分解模k102 for (int i = 0; i <num; ++i) {103 r[i]=lucas(n,m,a[i]);104 }105 cout<<china(num,r,a)<<endl;106 }107 return 0;108}C++

于是就得到了x，y的递推关系，求接的过程是递归的，从最后一个解$x=1,y=0$，就能推导到第一个式子的一个解。证毕。

参考链接

Ⅰ.EXGCD证明