欧几里得算法

又名：辗转相除法

1. 目的：

求两个数的最大公约数。

2. 定理

:::info 设是任意三个不全为0的整数，且，其中是整数，则. ::: 图解最大公约数.pdf

3. 证明：

已知两个数 a 和 b ，假设他们的最大公约数是 d
有 d | a, d | b

证1. gcd(a, b) --> gcd(b, a % b)
即证 d | a, d | b ---> d | a % b
因为 a % b = a - a // b * b 令 c = - a // b c一定是个整数
根据除法的性质 d | a, d | b ---> d | xa + yb 可得 d | a + cb
所以 d | a % b

证2. gcd(a, a % b) ---> gcd(a, b)
即证 d | a % b, d | b ----> d | a
因为 d | a % b <==> d | a + cb
又有 d | b ，可得 d | a + cb - cb
即 d | a
得证！！！

4. 模板

public int gcd(int x, int y) {
    return y > 0 ? gcd(y, x%y) : x;
}

//优化，使用绝对最小剩余
public int gcd(int a, int b) {
    if (b == 0) return a;
    int mod = a % b;
    if (mod > b / 2) mod = b - mod;
    return gcd(b, mod);
}