欧几里得算法与扩展欧几里得算法

资料来源:维基百科的欧几里得算法以及扩展欧几里得算法


欧几里得算法(辗转相除法)

辗转相除法为求最大公约数的算法。算法步骤为

  1. 将已知的两个数a,b相除(a/b),得到商q以及余数r
  2. 将上一步得到的余数r作为除数,除数b作为被除数,继续相除,即b/r。
  3. 反复进行上一步,直到得到的余数r为0时,除数即为最大公约数

python代码为:

def gcd(a, b):
	while b != 0:
		r = a % b
		a = b
		b = r
	return a

示例: 辗转相除法


扩展欧几里得算法

根据裴蜀定理,给定的两个整数a,b。必定存在整数x,y使得xa+yb = gcd(a,b)。在欧几里得算法的基础上,增加两个数列s,t——其初始值为[1,0],[0,1]。每次计算si +1 = si-1 - qsi与ti +1 = ti-1 - qti。其中,q为每一步所得的商

python代码为:

def ext_euclid(a, b):
    old_s, s = 1, 0
    old_t, t = 0, 1
    old_r, r = a, b
    if b == 0:
        return 1, 0, a
    else:
        while r != 0:
            q = old_r // r
            old_r, r = r, old_r - q * r
            old_s, s = s, old_s - q * s
            old_t, t = t, old_t - q * t
    return old_r, old_s, old_t      # 最小公约数  s为a的系数  t为b的系数

示例: 扩展欧几里得算法