求模的逆元

• 辗转相处法
  　求a b的最大公约数c,则c是min(a,b)的最大公约数且是|a-b|的最大公约数(都是整倍数嘛)。
  例如: 252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）； 因为252 − 105 = 21 × (12 − 5) = 147，所以147和105的最大公约数也是21。 当两个数的最大公约数是1时，这是两个数互为素数。==>以后可用该算法判断两个数是否是素数。
• 扩展欧几里得算法
  ax+by=gcd(a,b)，要求a,b互素即gcd(a,b)=1
  通过辗转相处可求出ax+by=gcd(a,b)方程的解。
• 模的逆元(ab%n=1)
  对ax+by=1求b的模:
  (ax+by)%b=1%b
  ax%b+0=1
  即求出a模b的逆元为x。
• wiki上的例子 用类似辗转相除法，求二元一次不定方程 47x+30y=1 47x+30y=1的整数解。 47 = 30 * 1 + 17 30 = 17 * 1 + 13 17 = 13 * 1 + 4 13 = 4 * 3 + 1 然后把它们改写成“余数等于”的形式 17 = 47 * 1 + 30 * (-1) //式1 13 = 30 * 1 + 17 * (-1) //式2 4 = 17 * 1 + 13 * (-1) //式3 1 = 13 * 1 + 4 * (-3) 然后把它们“倒回去” 1 = 13 * 1 + 4 * (-3) 1 = 13 * 1 + [17 * 1 + 13 * (-1)] * (-3) //应用式3 1 = 17 * (-3) + 13 * 4 1 = 17 * (-3) + [30 * 1 + 17 * (-1)] * 4 //应用式2 1 = 30 * 4 + 17 * (-7) 1 = 30 * 4 + [47 * 1 + 30 * (-1)] * (-7) //应用式1 1 = 47 * (-7) + 30 * 11 得解x=-7, y=11。 47的逆元为-7
• 代码(from wiki)
  • python
  def ext_euclid ( a , b ): if (b == 0): return 1, 0, a else: x , y , q = ext_euclid( b , a % b ) x , y = y, ( x - (a // b) * y ) return x, y, q
  • c
    int gcdEx(int a, int b, int *x, int *y) { if(b==0) { *x = 1,*y = 0; return a; } else { int r = gcdEx(b, a%b, x, y); int t = *x; *x = *y; *y = t - a/b * *y; return r; } }
• 参考
  
  • 辗转相处法(欧几里得算法)
  • 模逆元
  • 扩展欧几里得算法
  • 算法导论第三版31章