欧几里德算法(扩展:求模线性方程)

欧几里德算法(扩展:求模线性方程)

一、欧几里德算法(辗转相除法)

求两个正整数的最大公约数gcd(m,n),算法基于的方法是重复应用等式gcd(m,n) = gcd(n,m mod n),直到m mod n等于0。

证明gcd(m,n) = gcd(n,m mod n):m可以表示成 m = kn + r,则 r = m mod n;假设d是m和n的一个公约数,则有 d|m 和 d|n,而 r = m - kn,因此d|r,因此d是(n,m mod n)的公约数;假设d 是(n,m mod n)的公约数,则 d|n,d|r,但是 m = kn + r,因此d也是(a,b)的公约数;因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证。

具体步骤描述如下:

1:如果n=0,返回m的值作为结果,同时过程结束;否则,进入第二步。 2:用n去除m,将余数赋给r。

3:将n的值赋给m,将r的值赋给n,返回第一步。

模板(没有判断0的情况)

int gcd( int a, int b ){ int r; while( b > 0 ){ r = a % b; a = b; b = r; }

return a;

}

二、扩展欧几里德算法:

对于不完全为0的非负整数a,b,必然存在整数对 x,y,使得 gcd(a,b)= ax + by。

基于以下事实:gcd(a, b) = gcd(b, a%b). 可以得出:存在x,y,x',y'使得: ax + by = d (1) bx'+ (a%b)y' = d 即 bx' + [a-(a/b)*b]y' = d 整理得: ay'+ b(x'-(a/b)y')=d (2) 由(1)(2)得:x = y' y = x'-(a/b)y' 当b = 0时,ax = gcd(a,0) = a, 得x = 1. 模板(求x 和 y): EXTEND-EUCLID int Extend_Euclid(int a, int b, int &x, int &y){ if(b == 0){ x = 1;

} else{ } y = 0; return a; int gcd,t; gcd = Extend_Euclid(b, a%b, x, y); t = x; x = y; y = t - (a / b) * y; return gcd;

}

三、扩展欧几里德算法的应用:

1.求二元一次方程 ax + by = c 的整数解

定理:对于整数方程ax + by = c,若c mod Gcd(a, b) == 0,则该方程存在整数解,否则不存在整数解。

设d = gcd(a,b), a' = a/d, b' = b/d, 则方程变形为 d(a'x + b'y) = c 若方程有整数解,则 d|c, 否则无解. 设c' = c/d, 则方程 ax + by = c等价于 a'x + b'y = c' 因为gcd(a',b') = 1, 则我们可以求得 a'x + b'y = gcd(a',b') = 1 的解, 即 ax + by = gcd(a,b) = d的解 x,y。

则c'x, c'y就是 ax + by = c 的一组解。

xx = c'x + b't, yy = c'y - a't t∈Z就是所有满足条件的解。

2.对于求解模线性方程 ax ≡ b(modn)

定理:假设对整数x', y',有gcd(a,b) = ax' + ny', 则方程ax ≡ b(modn)有一个解的值为 x0。

满足x0 = x' * (b/d) modn. ax0 ≡ ax'(b/d) (mod n) ≡ d(b/d) (mod n) ≡ b (mod n)

模板:

Modular_Linear

int Modular_Linear(int a, int b, int n){ // ax = b (mod n) int d, x, y, x0, i; d = Extend_Euclid(a, n, x, y); if(b%d == 0){ x0 = x * (b/d) % n + n; for(i = 0;i < d;i ++) cout << (x0 + i*n/d) % n <<endl;

}

return 0; }



联系客服:cand57il.com