最大公约数是指两个或多个整数的约数中最大的一个。这个概念在小学时代，我们就已经知道了。但是今天依然把这个问题拿出来，是因为由最大公约数引发的一系列问题，成为了公钥密码学的基础，所以有必要对此类问题的来龙去脉再做一个了解。

欧几里得算法

步骤与实现

求解两个自然数的最大公约数时，我们最常用的一种方法就是辗转相除法，也叫欧几里得算法。 先简单回顾一下算法的步骤：求解两个自然数a,b的最大公约数gcd(a,b)，可以通过求解gcd(b,a mod b)的最大公约数实现，以此迭代，循环向前，直到函数成为gcd(x,0)时（x为正整数）返回x. 代码如下： def euclid(a, b): while b != 0: temp = a a = b b = temp % b return a

原理解析

这个算法本身非常简单，大家也非常熟悉。但是为什么可以这样做呢？首先，我们需要理解GCD递归定理。 GCD递归定理：对任意非负整数a,b，等式gcd(a,b)=gcd(b,a mod b)成立。 证明： 先证gcd(a,b)能整除gcd(b,a mod b)

• 设d=gcd(a,b)，那么有d|a和d|b成立。
• 再假设a mod b=x，也就是说，a=nb+x，从而x=a−nb
• 由以上两点可知，d|b且d|x，则说明d是b和a mod b的约数
• 所以，d|gcd(b,a mod b)，也就是gcd(a,b)|gcd(b,a mod b)

上面最后一点的原因是：两个整数的公约数可以整除这两个整数的最大公约数。证明略。 再证gcd(a,b)能被gcd(b,a mod b)整除。和上面的证明几乎是一模一样的道理

• 设d=gcd(b,a mod b)，那么有d|a和d|b成立。因为a mod b可以写成a与b的线性关系式。
• 也就是说d是a与b的公约数，显然，有d|gcd(a,b)成立

好了，到此，由以上两点的证明可知，gcd(a,b)|gcd(b,a mod b) 且 gcd(b,a mod b)|gcd(a,b)。也就是说gcd(a,b)=gcd