欧几里得算法

文中用 表示求模运算, 表示整除, 比如 ,
欧几里德算法(称辗转相除法)，用于计算两个整数a, b的最大公约数gcd(a, b).
基本原理

1. 与第3条结合, 可以写更相减损术
2. 与第3条结合, 欧几里得算法(辗转相除法)
3. 
4. 是点集 中最小的正整数.
   c/c++ 实现的欧几里得算法

int gcd(a, b)
{
    int temp;
    while(b)
    {
          temp = b;
          b = a % b;
          a = temp;
    }
  return a;
}

扩展欧几里得算法

求的整数解
因为我不是学数学的, 严谨的证明就不写了. 只写一点简单的推导

递推公式

设





根据上式的 c++ 实现

void exgcd(int a, int b, int& g, int& x, int& y)
{  // 纯c好像不支持引用, 可以用指针代替.
    if(!b)
    {
        g = a;
        x = 1;
        y = 0;
    }
    else exgcd(b, a % b, g, x, y);
    int t;
    t = x;
    x = y;
    y = t -(a / b) * y;
}

非递归算法

这个稍有些难, 仍然是
step1 .
step2.
step3. if(r==0) 结束, else继续
step4. 去step2

初始时由上step1的定义有
第一次到step3, 如果,就是的解
step4
(1)式变为 , (3)式变为

void exgcd(int a, int b, int& g, int& x, int& y)
{ // 可以用来求逆元
    if(!b)
    {
        x = 0;
        y = 1;
        g = a;
    }
    else
    {
          int x1, y1, q, r, t;
          x1 = y = 1; y1 = x = 0; 
          r = a % b; q = a / b;
          while(r) 
          {
              a = b;
              b = r;
              t = x1;
              x1 = x;
              x = t - q * x;
              t = y1;
              y1 = y;
              y = t - q * y;
              r = a % b;
              q = a / b;
          } 
          g = b;
    }
}