gcd(a, b) = gcd(b, a % b)的证明

首先假设存在\(a,b,c\)这三个数，若其满足\(a = q*b + c\) ，证明：\((a, b) = (b, a \mod b)\)

证明：

\(\because\)首先可以由\((a, b)\)可知，\((a, b) | a\)，\((a, b) | b\) ；

\(\therefore\)由上式可知：

\[c=q1*(a, b)-q2*q*(a, b)=(a,b) *(q1 - q2 * q) \]

\(\therefore\)可知\((a,b) | c\)。

\(\therefore\) 可知\((a,b)|b,(a, b)|c\) ；故\(gcd(a,b)\) 是\(b\)，\(c\)的一个公因子；故有：

\[(a,b)\leqslant (b,c) \]

同理，可以知道\((a,b)\geqslant (b,c)\) ；那么可知\((a,b)=(b,c)\)；即\(gcd(a,b)=gcd(b,a \mod b)\) ;

此等式是欧几里得算法能够计算出\(gcd\)的保障。

代码实现如下:

通过上述等式来理解，当\(a \mod b = 0\)那么就不用递归，直接返回\(gcd(a,b)= b\)即可

func gcd(a, b int) int {
    if a % b == 0 {
        return b
    }
    return gcd(b, a % b)
}

还有一种写法，就是不断的递归下去，\(b\)会等于\(0\) ，那么当\(b\)等于\(0\)时，直接return a

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a % b)
}

Q&A

Q：\(gcd(a,b)=gcd(a,a\mod b)\)成立吗？

A：很显然无法证明。具体证明方法如上。