数学问题——拓展欧几里得算法

一、拓展欧几里得算法

该算法用来解决这样一个问题：给定两个非零整数 a和 b，求一组整数解 (x,y) ，使得 ax + by = gcd(a,b)成立，其中 gcd(a,b)表示 a和 b的最大公约数。

• • 递归边界：当 b为 0时，此时的 a就等于 gcd，显然有 a*1+b*0=gcd成立，此时 x=1,y=0；
  • 递推公式：设当计算 gcd(a,b)时，有 ax₁ + by₁ = gcd成立；而在下一步计算gcd(b,a%b)时，又有bx₂+ (a%b)y₂= gcd成立。有以下递推式：

$\left\{\begin{matrix}x_{1} = y_{2}\\ y_{1} = x_{2} - (a/b)y_{2}\end{matrix}\right. $

代码如下：

1 /*    
 2     拓展欧几里得算法 
 3 */
 4 
 5 #include <stdio.h>
 6 #include <string.h>
 7 #include <math.h>
 8 #include <stdlib.h>
 9 #include <time.h>
10 #include <stdbool.h>
11 
12 int x=0, y=0;
13 // 给定两个非零整数 a 和 b，求一组整数解 (x,y) ，使得 ax + by = gcd(a,b) 成立
14 int exGcd(int a, int b) {
15     if(b == 0) {    // 递归边界 
16         x = 1;
17         y = 0;
18         return a;    // 返回最大公约数 
19     }
20     int g = exGcd(b, a%b);
21     int temp = x;    // 存放 x 的值
22     x = y;            // 递推式 
23     y = temp - a/b*y; 
24     return g;        // g 是最大公约数 
25 }
26 
27 int main() {
28     int gcd = exGcd(4,3);
29     printf("4*%d + 3*%d = %d\n", x, y, gcd); 
30 
31     return 0;
32 }

当exGcd函数结束时 x和 y就是所求的解。显然，在得到这样一组解之后，就可以通过下面的式子得到全部解：

$\left\{\begin{matrix} x^{'} = x + \frac{b}{gcd}*K \\ y^{'} = y - \frac{a}{gcd}*K \end{matrix}\right.$ （K为任意整数）

也就是说， x和 y的所有解分别以 b/gcd与 a/gcd为周期。那么其中 x的最小非负整数解是什么呢？从直观上来看就是x%(b/gcd) 。但是当 x为负数时，x%(b/gcd)也会得到一个负数，例如 (-15)%4=-3。考虑到即便 x是负数，x%(b/gcd)的范围也是在 （-b/gcd，0) ，因此对任意整数来说，$\left ( x\%\frac{b}{gcd} + \frac{b}{gcd} \right ) \% \frac{b}{gcd}$才是对应的最小非负整数解。

二、方程 ax + by = c的求解

ax + by = c存在解的充要条件是c%gcd == 0，且一组解 (x,y)等于 $\left ( \frac{cx_{0}}{gcd},\frac{cy_{0}}{gcd} \right )$。

在得到这样一组解之后，就可以通过下面的式子得到全部解：

$\left\{\begin{matrix} x^{'} = \frac{cx_{0}}{gcd} + \frac{b}{gcd}*K \\ y^{'} = \frac{cy_{0}}{gcd} - \frac{a}{gcd}*K \end{matrix}\right.$（K为任意整数）

除此之外，可以得到和上面一样的结论，对任意整数来说，$\left ( x\%\frac{b}{gcd} + \frac{b}{gcd} \right ) \% \frac{b}{gcd}$是ax+by=c中 x的最小非负整数解，一般来说可以让 x取 $\frac{cx_{0}}{gcd}$，其中 x₀是ax+by=gcd的一个解。

三、同余式 ax≡ c(mod m)的求解

先解释什么是同余式。对整数 a、b、m来说，入门 m整除 a-b（即 (a-b)%m=0），那么就说 a与 b模 m同余，对应的同余式为 a≡ b(mod m)，m称为同余式的模。显然，每一个整数都各自与 [0,m)中唯一的整数同余。

此处要解决的就是同余式 ax≡ c(mod m)的求解。根据同余式的定义，有 (ax-c)%m=0成立，因此存在整数 y，使得 ax-c=my成立。移项并令 y=-y后即得 ax+my=c 。

由上面的结论，$\left ( x,y \right ) = \left ( \frac{cx_{0}}{gcd\left ( a,m \right )},\frac{cy_{0}}{gcd\left ( a,m \right )} \right )$。

至于全部解，有以下结论：

设 a,c,m是整数，其中 m≥1，则

• • 若c%gcd(a,m) ≠ 0，则同余式方程 ax≡ c(mod m)无解。
  • 若c%gcd(a,m) = 0，则同余式方程 ax≡ c(mod m)恰好有 gcd(a,m)个模 m意义下不同的解，且解的形式为

$x^{'}=x+\frac{m}{gcd\left ( a,m \right )}*K$

其中 K = 0,1，... ,gcd(a,m)-1。

四、逆元的求解以及 (b/a)%m的计算

先解释什么是逆元（此处特指乘法逆元）。假设 a、b、m是整数，m>1。且有 ab≡ 1(mod m)成立，那么就说 a和 b互为模 m的逆元。通俗的说，如果两个数的乘积模 m后等于 1，就称它们互为 m的逆元。

那么逆元有什么用处呢？当要计算(b/a)%m时，通过找到 a模 m的逆元 x，就有(b/a)%m = (b*x)%m = ((b%m)*(x%m))%m 成立。这对于解决被除数 b非常大的问题来说是非常实用的。

由定义知，求a模 m的逆元，就是求解同余式 ax≡ 1(mod m)，并且在实际使用中，一般把 x的最小正整数解称为a模 m的逆元。

• • 如果gcd(a,m) ≠ 1，那么同余式 ax≡ 1(mod m)无解，a不存在模 m的逆元。
  • 如果gcd(a,m) ≠ 1，那么同余式 ax≡ 1(mod m)在 (0,m)上有唯一解，直接使用拓展欧几里得算法解出 x之后就可以用 (x%m + m)%m得到 (0,m)范围内的解，也就是所需要的逆元。

另外，如果 m是素数，且 a不是 m的倍数，则还可以直接使用费马小定理来得到逆元。

费马小定理：设 m是素数，a是任意整数且 a $\not\equiv$ 0(mod m)，则 a^m-1≡ 1(mod m)。