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

斐蜀定理

内容

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

若 $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%i0)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=(resi)%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 d1?(x%mod+mod)%mod:-1;70}71//计算C(n,m)%mod:C(n,m)%mod=(n!/[m!(n-m)!])%mod=n!%modinv(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证明