扩展欧几里得算法

定义

扩展欧几里得算法用于已知\(a,b\),求解一组\(x,y\),使得他们满足\(ax+by=\gcd(a,b)=d\)

有关概念

  1. \(a,b\)是整数,则一定存在\(x,y\),使得方程\(ax+by=m\)有解,其中\(m\)满足\(\gcd(a,b)|m\)。称之为裴蜀定理(贝祖定理)。

求解算法

思路与简单证明

首先设\(ax_1+by_1=\gcd(a,b)\),\(bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)\)

根据欧几里得算法,

\(\gcd(a,b)=\gcd(b,a\bmod b)\)

\(ax_1+by_1=bx_2+(a\bmod b)y_2\)

\(ax_1+by_1=bx_2+(a-\lfloor \frac ab\rfloor\times b)y_2\)

\(ax_1+by_1=ay_2+b(x_2-\lfloor \frac ab\rfloor y_2)\)

根据多项式恒等定理,得:

\(x_1=y_2,y_1=x_2-\lfloor \frac ab\rfloor y_2\)

于是我们发现,可以按照类似欧几里得算法的形式递归求解,边界条件:

\(b=0\)时,\(\gcd(a,b)=a\),此时方程的解为\(x=1,y=0\)

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int d=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return d;
}

应用

  1. 求解线性同余方程\(ax+by=c\)

    首先该方程需满足\(\gcd(a,b)|c\),否则无解。

    先用扩展欧几里得算法求出方程\(ax+by=\gcd(a,b)\)的一组解\(x_0,y_0\),该方程的任意一组解可以表示为\(x=x_0+\frac b{\gcd(a,b)}t,y=y_0-\frac a{\gcd(a,b)}t,\ t\in Z\)。将等号两边同时同时乘以\(\frac c {\gcd (a,b)}\),就求得了原方程的一个解。

    方程通解的证明:

    若有\(ax+by=d\)\(a_0x+b_0y=d\)

    那么便有\(a(x-x_0)+b(y-y_0)=0\)

    两边同时除以\(\gcd(a,b)\)可得:

    \(\frac{a}{\gcd(a,b)}(x-x_0)=-\frac{b}{\gcd(a,b)}(y-y_0)\)

    而因为\(\gcd(\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)})=1\)

    所以可得\(\frac{b}{\gcd(a,b)}|(x-x_0)\)

    所以很显然有\(\frac{b}{\gcd(a,b)}t=(x-x_0),t \in Z\)

作者

xqmmcqs

发布于

2017-11-07

更新于

2021-03-13

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×