最大的公约数的程序求法

最大公约数简称gcd

下为使用python的基于辗转相除法的gcd函数实现

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

辗转相除法，又叫欧几里得算法，他的计算过程如上代码，不再赘述，下附其原理与证明。

原理与证明

其计算原理依赖于下面的定理。

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。

gcd(a,b) = gcd(b,a mod b) (不妨设a＞b 且r=a mod b ,r不为0)

证法一

a可以表示成a = kb + r（a，b，k，r皆为正整数，且b不为0），其中kb项是关联gcd(a,b)、gcd(b,r)的桥梁。

①假设d是a、b的一个公约数，即a和b都可以被d整除，记a=ud，b=vd，则r = a - kb=(u-kv)d，显然d也是r的因子，那么d也是b、r的一个公约数。

②同理，设e是b、r的一个公约数，记b=xe，r=ye，则a = kb+r=(kx+y)e，显然e也是a的因子，那么e也是a、b的一个公约数。

取d=gcd(a,b)，e=gcd(b,r)，根据①：d是e的一个因子，设e=pd；同理根据②：e是d的一个因子，设d=qe。结合两点可知d=qpd，则qp=1，由于p、q均为正整数，所以p=q=1。进而可得d=e。

综上论证，a、b和b、r具有相同的公约数，并且gcd(a,b)=gcd(b,r)。

证法二

假设c = gcd(a,b),则存在m,n，使a = mc, b = nc;

令r = a mod b，即存在k，使r = a-kb = mc - knc = (m-kn)c;

故gcd(b,a mod b) = gcd(b,r) = gcd(nc,(m-kn)c) = gcd(n,m-kn)c;

则c为b与a mod b的公约数;

假设d = gcd(n,m-kn), 则存在x,y, 使n = xd, m-kn = yd; 故m = yd+kn = yd+kxd = (y+kx)d;

故有a = mc = (y+kx)dc, b = nc = xdc; 可得 gcd(a,b) = gcd((y+kx)dc,xdc) = dc;

由于gcd(a,b) = c, 故d = 1;

即gcd(n,m-kn) = 1, 故可得gcd(b,a mod b) = c;

故得证gcd(a,b) = gcd(b,a mod b).

注意:两种方法是有区别的。

更相减损术的python实现

def gcd(a, b):
    # a>b
    if a < b:
        temp = a
        a = b
        b = temp
    if(b==0):
        return a
    if a == b << 1:
        return b
    return gcd(a - b, b)
#要证明该算法的正确性也并不困难 只要证明gcd(a,b)=gcd(a,b-a)和当x-y=y时gcd(x,y)=y

如何求gcd(x,y,z)

直接说结论，总有gcd(x,y,z)=gcd(x,gcd(y,z)) 读者自证不难。