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

欧几里德算法

欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。gcd函数就是用来求(a,b)的最大公约数的。

 

gcd函数的基本性质：

性质一：gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|)

证明略。

 

性质二：gcd(a,b)=gcd(b,a mod b)

证明：a可以表示成a = kb + r，则r = a mod b

假设d是a,b的一个公约数，则有 d|a, d|b，而r = a - kb，因此d|r ，d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数，则 d|b , d|r ，又a = kb +r ，因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。

 

//求GCD的递归方法

def gcb(a, b):
    if b==0:
        return a
    else:
        return gcb(b, a%b)

print gcb(12, 18)

//时间复杂度O(lgn)

 

扩展欧几里德算法
定理一：对于不完全为 0 的非负整数 a，b，gcd(a,b)表示 a，b 的最大公约数，必然存在整 数对 x，y ，

使得gcd(a,b)=ax+by。

解：设a、b不全为0，令a>b，

当b=0时，gcd(a,b)=a,解的情况为x=1，y=0

当ab！=0，令

a*x1+b*y1 = gcd（a,b)
b*x2+(a%b)*y2 = gcd(b,a-a/b*b)
又gcd(a,b) = gcd(b,a-a/b*b)
故有a*x1+b*y1 = b*x2+(a%b)*y2
a*x1+b*y1 = b*x2+(a-a/b*b)*y2
= b*x2+a*y2-a/b*by2
= a*y2+b*(x2-a/b*y2)
即有，x1=y2,  y1=x2-a/b*y2
由上推导可知，x1与y1的值可由x2、y2推知，拓展欧几里得算法就是不断地的将b放小，直至b等于0，最后反推求回x和y。

 

//算法,解方程ax+by=gcd(a,b),其中d=gcd(a,b)

求5mod7的逆元和最大公约数

def egcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        g, x, y = egcd(b, a % b)
        return g, y, x - a / b * y

print egcd(5, 7 )