扩展欧几里德算法、证明及其应用

时间:2023-02-03 23:32:50

一、扩展欧几里德算法:

已知a, b求解一组x,y,使它们满足等式: ax+by = gcd(a, b) =d(解一定存在,根据数论中的相关定理)。

扩展欧几里德常用在求解模线性方程及方程组中。

 

证明:

ax+by=gcd(a,b);

1. (1) a = 0,ax+by = gcd(a,b) = gcd(0,b) = b,

此时x = 0(此时x的值是任意的),y = 1;

    (2)b = 0, ax + by = gcd(a,b) = gcd(a,0) = a,

此时x = 1,y = 0(此时y的值是任意的);

2.a和b都不为0时

ax1 + by1 = gcd(a, b)

由欧几里德定理:gcd(a,b) = gcd(b, a%b)得

ax1 + by1 = gcd(a,b) = gcd(b, a%b) 即:

bx2 + a%by2 = gcd(b, a%b) = ax1 + by1

a % b = a - a/b*b;

ax1 + by1 = bx2 + (a - a/b*b)y2;

                =bx2 + ay2 - a/b*b*y2;

                =ay2 + b(x2-a/b*y2);

所以:x1 = y2, y1 = x2 - a/b*y2

扩展欧几里德算法代码:

void gcd(int a, int b, int &x, int &y)
{
if(b == 0)
{
x
= 1;
y
= 0;
r
= a;//r为a、b的最大公约数
return ;
}
gcd(b, a
%b, x, y);
int t = x;
x
= y;
y
= t - a / b * y;
}

 二、欧几里德算法的应用

1.求方程ax + by = c的一种解

扩展欧几里德算法求得的x1,y1只是ax + by = gcd(a,b)中x和y的一个解

如果让求ax + by = c的一个解

ax1* z+ by1 * z = c * z;

使c * z = gcd(a,b),则z = c / gcd(a,b);

所以x = x1 * z = x1 * c / gcd(a,b), y = y1 * z = y1 * c / gcd(a,b);

x、y的解集为:

x = x1 + b / gcd(a,b) * t

y = y1 - a / gcd(a,b) * t;

(t 为任意值)

反证:

将x、y代入原式ax + by = gcd(a,b)中得:

a(x1 + b / gcd(a, b) * t) + b(y1 - a / gcd(a,b) * t) = gcd(a,b)

化简后得:

ax1 + by1 = gcd(a,b)

所以可得解集正确

 

2.ax≡b (mod n)的最小解,(ax % n ≡ b 相当与 ax + ny = b)

一般情况下,ax+by=1;得 x为a mod b 的逆元,y为 b mod a的逆元
若ax=1 mod f 则称a关于模f的乘法逆元为x。也可表示为ax≡1(mod f)。
当a与f互素时,a关于模f的乘法逆元有唯一解。如果不互素,则无解。如果f为素数,则从1到f-1的任意数都与f互素,即在1到f-1之间都恰好有一个关于模f的乘法逆元。

根据扩展欧几里德算法可求得ax + ny = b的一组解

x = b/gcd(a,n) * x1

要求其最小整数解,可根据同解x = x1 + n/gcd(a,n) * t;

s = n / gcd(a,n)

x%s得到最一个值x1,x1可能为负数,此时x%s还需要+s

加上s后可能就不是最小值了,所以还需要在对s取余

所以最小解最终为 x = (x % s + s) % s