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

斐蜀定理

内容

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

若$a,bin N$,那么对于任意x，y，方程$ax+by=gcd(a,b)*k(kin 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=adiv s$(此处为整除),$r=amod 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)$

因为$0leq 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)$

证明完毕

拓展欧几里得算法

内容

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

方法

下面直接给出代码

1
2
3
4
5
6
7
8
9
大专栏  数论入门——斐蜀定理与拓展欧几里得算法"line">10
11
12
13
14
15
16
17
18


///解整数方程: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+(amod b)y_x=gcd(b,amod b)$

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

$ax_1+by_1=bx_2+(amod b)y_2$.

其中$amod b=a-adiv btimes b$(此处为整除)，带入原式得到:

$ax_1+by_1=bx_2+ay_2-adiv btimes y_2times b$

通过移项得到:

$ax_1+by_1=ay_2+b(x_2-adiv btimes y_2)$

则可以得到:

$x_1=y_2,y_1=(x_2-adiv btimes y_2)$

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

参考链接

Ⅰ.EXGCD证明