扩展欧几里得

欧几里得算法

1. 别名：求最大公约数算法，辗转相除法
2. 证明：gcd(a, b) = gcd(b, a%b)
   • 设 a = kb + r, r = a % b;
   • 设 g 是 a, b 的公约数, g|a, g|b;
   • 因 r = a - kb, g|r;
   • =—————————–=
   • 设 g|b, g|r;
   • 因 a = kb + r, g|a;
   • 得证;
3. cpp
   • 递归

     int gcd(int a, int b){
         return b == 0 ? a : gcd(b, a%b);
     }

   • 非递归

     long long gcd(long long a, long long b){
         while(b != 0){
             int t = a;
             a = b;
             b = t%b;
         }
         return a;
     } 

扩展欧几里得算法

1. 证明：对于不完全为 0 的非负整数 a, b, 必然存在整数对 x, y, 使得：gcd(a, b) = ax + by;
   • 当 b = 0, gcd(a, b) = a, x = 1, y = 0;
   • 当 b != 0 :
     • 设 ax1 + by1 = gcd(a, b);
     • 设 bx2 + (a%b)y2 = gcd(b, a%b);
     • 因 gcd(a, b) = gcd(b, a%b), ax1 + by1 = bx2 + (a%b)y2;
     • ax1 + by1 = bx2 + (a - a/b * b)y2;
     • ax1 + by1 = ay2 + b(x2-a/b)y2;
     • 则 x1 = y2, y1 = (x2-a/b)y2;
2. cpp
   • 递归

     int exgcd(int a, int b, int &x, int &y){
         if(b == 0){
             x = 1;
             y = 0;
             return a;
         }
         int cc = exgcd(b, a%b, x, y);
         int t = x;
         x = y;
         y = t - a/b*y;
         return cc;
     }

   • 非递归

     // ...

3. 求乘法逆元
   • a*x ≡ 1(mod n);
   • a*x%n ≡ 1%n;
   • 将其写成 ax + by = 1 (b = n);
   • 判断逆元是否存在 => gcd(a, b) == 1;
   • 存在求解 x 就是 a 关于 n 的逆元了;
   • 费马小定理 qpow(a, n-2, n) 求逆元需要满足 n 是个素数，而扩展欧几里得只需要满足 gcd(a, n) = 1;