辗转相除法和扩展欧几里得算法

参考自https://www.cnblogs.com/bljfy/p/9316784.html

https://blog.csdn.net/weixin_44073496/article/details/85225355

辗转相除法

证明

q = a / b;

r = a % b;

1)若r == 0,则b为a的最大公因数

2)设a和b有公因数d,则d为r的因数

3)设b和r有公因数d,则d为a的因数

先证明2):设a = xd, b = yd,则r = a - bq = d(x - yq)

所以,a和b的公因数都为r的因数,也为b和r的公因数

在证明3):b = xd,r = yd,a = bq + r = d(xq+y)

所以,b和r的公因数都为a的因数,也为a和b的公因数

所以二者公因数集相等,那么gcd也相等

所以gcd(a, b) == gcd(a, a%b)

结合1,当a%b为0时,gcd(a, 0) ==…==gcd(a, b)

代码

1
2
3
4
5
int gcd(int a, int b)
{
if(b == 0) return a;
return gcd(b, a % b);
}

扩展欧几里得算法

证明

贝祖定理及其证明

贝祖定理:

ax + by = c, x ∈ Z*成立的充要条件是gcd(a, b) | c

证明:

s = gcd(a, b),显然s | a,并且s | b

又因为x, y ∈ Z*

所以s | ax, s | by

s | ax + by

ax + by = s * t(t为整数)

所以,c是s的倍数,即,c是a,b最大公因数的倍数

扩展欧几里得算法证明

利用数学归纳法

  1. 当b == 0时:在扩展欧几里得算法的最后一步,即b == 0 时候,显然存在一对整数x = 1, y = 0,使得a * 1 + 0 * 0 = gcd(a,0)成立

  2. 若b > 0, 则gcd(a,b) = gcd(b, a mod b)。假设存在一对整数x, y满足 b * x + (a mod b) * y = gcd(b, a mod b)成立

    因为 a mod b = a - [a / b] * b,所以式子可以变为
    bx + (a - [a / b] * b) y = ay + (x - [a / b] y) b. 这时候令 x ’ = y, y ’ = ( x - [a / b] y)
    就有ax’ + by’ = gcd(a, b).(这一步推出了下一步)

由1和2,归纳得出命题成立

代码

来自开头参考中的第二个链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y){
if(!b){ x = 1, y = 0; return a;}
ll d = exgcd(b,a % b, x, y);
ll z = x; x = y; y = z - (a / b) * y;
return d;
}
//定义变量d,x,y,调用d = exgcd(a,b,x,y) 注意x, y是引用传入。
//上述程序求出的是方程ax + by = gcd(a,b)的一组特解x,y.并返回了a,b的最大公约数
//对于更为一般的方程 ax + by = c,显然它有解的充分必要条件是d | c,d = gcd(a,b)
//所以我们可以先求出ax + by = d 的一组特解x0,y0,再同时乘上c / d, 就得到了ax + by = c 的一组特解 (c/d)x0, (c/d)y0;
/*
更进一步方程ax + by = c的通解可表示为:
x = c / d * x0 + k * (b / d) //1)
y = c / d * y0 - k * (a / d) //2)
其中k是任意整数,d = gcd(a,b),x0,y0是 ax + by = d的一组特解
简略证明是将1) 2)代入ax + by.发现 k * ab / d相互抵消
*/

扩展欧几里得算法的应用

以下有点超出我的知识范围orz,先copy下来,以后慢慢看,慢慢改

解线性同余方程:

描述

给定整数a,b,m,求一个整数x 使得 a * x ≡ b (mod m), 无解则给出无解。
a * x ≡ b (mod m) 等价于a * x - b 是 m的倍数,不妨设为 -y 倍,于是该方程可以变为
a * x + m * y = b.
由前面可知该线性同余方程有解当且仅当 gcd(a,m) | b.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ll exgcd(ll a, ll b,ll &x,ll &y){
if(!b){
return x = 1, y = 0, a;
}
ll d = exgcd(b , a % b, x, y);
ll t = x;
x = y, y = t - (a / b) * y;
return d;
}
//solve ax + by = c return x; // x > 0
ll solve(ll a,ll b,ll c){
ll x,y;
ll d = exgcd(a,b,x,y);
if(c % d) return -1; //无解 c 不能整除gcd(a,b)
x *= c / d ; // x = c / d * x0 + k * ( b / d)
ll tmp = b / d;
return (x % tmp + tmp) % tmp; //求解正整数解x
}

特殊的线性同余方程a * x ≡ 1 (mod m)(等价于求解乘法逆元)

代码

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

ll get_inv(ll a,ll mod){
ll x,y;
exgcd(a,mod,x,y);
return (x % mod + mod)%mod; //求解最小正逆元
}

扩展求解线性同余方程组

描述

先考虑两个方程组的情况t ≡ r1 ( mod a1)(1),t ≡ r2( mod a2)(2)
(a1,a2不一定互质) 要求t(t > 0)
则有 t = a1 * x1 + r1, t = a2*x2 + r2
变形为:a1 * x1 + a2 * (-x2) = ( r2 - r1)
方程组有解等价于: (r2 - r1) | gcd(a1, a2);
我们可用扩展欧几里得算法求出 特解x10, x20; 求出最小正整数解x10;
那么要求的 t0 = a1 * x10 + r1;
显然 t0 满足1) 式和2)式
由此推论:t0 + k * lcm(a1,a2) 是(1),(2)两个方程组的通解,lcm(a1,a2)都可消去。
在此通解基础上可以得到新的线性同余方程 t ≡ t0 (mod lcm(a1,a2)) (3)

两个以上的时候就等价于在先求出两个线性同余方程的通解t,在和第三个方程联立又求解一次t’,不断合并。

未完待续……

hexo的markdown渲染把*都当成斜体标志来处理,本地的typora都没有!!

害得我还得一个个加上引用来避免渲染……

0%