（普通、扩展、二进制扩展） 欧几里得算法

欧几里得算法。

一个常见误区：有人以为 gcd(a,b)=1 是 a/bmodp 可计算的必要条件。其实不然，只要 gcd(b,p)=1 就足够了，gcd(a,b) 是否为 1 不影响模逆的存在性。

普通欧几里得算法

求最大公约数gcd

普通欧几里得定义：gcd(a,b)=gcd(b,a mod b)直到余数为 0，最后一个非零余数就是最大公约数。 gcd(48,18) 48%18=12 gcd(18,12) 18%12=6 gcd(12,6) 12%6=0 故：gcd(48,18) = gcd(12,6) = 6 int gcd(int a, int b) { int temp; while (b != 0) { temp = a % b; a = b; b = temp; } return a; } 递归版本 int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); }

扩展欧几里得算法

• 扩展欧几里得算法通过不断用“较大数减去较小数的倍数”来简化问题，并在每一步保持 ax+by的值不变，最终把这个值收缩到 gcd(a,b)，同时得到对应的系数。

• 其核心思想是维护不变式：在每一步中，当前余数都能表示为输入整数 a和 b的线性组合，且系数随余数同步更新。

• 作用：
  不仅能算出最大公约数，还能直接构造出贝祖等式 ax+by=gcd(a,b)的整数解。

  • 求逆元
  • 解线性不定方程
    

算法文字描述

已知a，b， 求得到最大公约数 gcd(a,b)以及满足 a·x1 + b·y1 = gcd(a,b)的整数 x1、y1。 定义中间辅助变量 x2、y2 非递归版本，本质上就是在从底向上模拟递归的回推过程，只是没有用函数栈。 数学上等价于： 新系数=上一轮系数−q×当前系数 初始化： a = 48, b = 18 x1 = 1, y1 = 0（对应 a的系数） x2 = 0, y2 = 1（对应 b的系数） 循环条件：b ≠ 0，每次迭代： 计算商 q = a // b 更新 (a , b ) = (b , a - q·b ) 更新 (x1, x2) = (x2, x1 - q·x2) 更新 (y1, y2) = (y2, y1 - q·y2) 循环结束时，a即为 gcd，此时 x1、y1即为所求系数。 初始化： x1=1,y1=0 x2=0,y2=1 gcd(48,18) q=48//18=2 b=48%18=48-2*18=12; a=18 (x1,x2) = (x2,x1-2*x2)= (0,1-2*0)=(0,1) (y1,y2) = (y2,y1-q·y2)=(1,0-2*1)=(1,-2) gcd(18,12) q=18//12=1 b=18%12=18-1*12=6; a=12 (x1,x2) = (x2,x1-2*x2)= (1,0-1*1)=(1,-1) (y1,y2) = (y2,y1-q·y2)=(-2,1-1*(-2))=(-2,3) gcd(12,6) q=12//6=2 b=12%6=12-2*6=0; a=12 (x1,x2) = (x2,x1-2*x2)= (-1,1-2*(-1))=(-1,3) (y1,y2) = (y2,y1-q·y2)=(-3,-2-2*3)=(3,-8) gcd(48,18) = 6 = 48 * (-1) + 18 * 3

迭代计算过程

算法c语言

一边做辗转相除，一边同步构造贝祖系数。 // 非递归版扩展欧几里得算法 // 返回 gcd(a, b)，并得到 ax + by = gcd 的一组解 int extended_gcd(int a, int b, int *x, int *y) { int x0 = 1, y0 = 0; // 初始：a*1 + b*0 = a int x1 = 0, y1 = 1; // a*0 + b*1 = b int r0 = a, r1 = b; int q, tmp; while (r1 != 0) { q = r0 / r1; // 余数迭代 tmp = r1; r1 = r0 % r1; r0 = tmp; // 系数迭代 tmp = x1; x1 = x0 - q * x1; x0 = tmp; tmp = y1; y1 = y0 - q * y1; y0 = tmp; } *x = x0; *y = y0; return r0; } 递归 // 返回 gcd(a, b)，并通过指针 x, y 得到方程 ax + by = gcd 的一组解 int extended_gcd(int a, int b, int *x, int *y) { if (b == 0) { *x = 1; *y = 0; return a; } int x1, y1; int gcd = extended_gcd(b, a % b, &x1, &y1); *x = y1; *y = x1 - (a / b) * y1; return gcd; }

二进制扩展欧几里得算法

二进制扩展欧几里得算法求" a/b mod p "

二进制扩展欧几里得算法求" 1/b mod p "

求1/b mod p与gcd（b,p）有什么关系？

性质

“边求 gcd 边求逆” 的精髓是：二进制 GCD 的每一步归约操作（去 2、凑偶、大减小），都被精心设计成不改变线性组合不变式的变换。当 gcd 被归约为 1 的那一刻，不变式本身就变成了逆元的定义式 b⋅x≡1(modp)。gcd 与逆元不是先后两步，而是同一个过程的同一个输出——这正是二进制扩展欧几里得算法最漂亮的地方。

// 二进制扩展欧几里得（非递归） // 返回 gcd(a,b)，并满足 a*x + b*y = gcd(a,b) int binary_exgcd(int a, int b, int *x, int *y) { int g = 1, u = a, v = b; int x1 = 1, y1 = 0, x2 = 0, y2 = 1; while ((u & 1) == 0 && (v & 1) == 0)//两个偶数 u >>= 1, v >>= 1, g <<= 1; *x = x1, *y = y1; while (u) { while ((u & 1) == 0) { u >>= 1; if ((*x & 1) || (*y & 1)) *x = (*x + v) >> 1, *y = (*y - u) >> 1; else *x >>= 1, *y >>= 1; } while ((v & 1) == 0) { v >>= 1; if ((x2 & 1) || (y2 & 1)) x2 = (x2 + u) >> 1, y2 = (y2 - v) >> 1; else x2 >>= 1, y2 >>= 1; } if (u >= v) u -= v, *x -= x2, *y -= y2; else v -= u, x2 -= *x, y2 -= *y; } *x = x2 * g; *y = y2 * g; if (a < 0) *x = -*x; if (b < 0) *y = -*y; return v * g; }