众所周知，gcd(x, y) = gcd(y, x%y)
但怎么证明其正确性，既保证我们这么做得到的答案一定是最大公约数
今天，我就来证明一下。
首先，我们要知道两条推论：
- 若 a|b，则 ka|b;
- 若 a|b，c|b ，则 (a±b)|c;
当我们知道这两条推论后，我们还需要知道一件事情，如果 a≤b， b≤a，则 a=b;
下面开始证明：
设 a = x|y, b = x%y, c = gcd(x, y), d = gcd(y, b);
解释：a为x除以y的商数。
∵c 为 x, y的最大公约数
∴x|c y|c
∴ya|c
∴x-ya|c 即 b|c
∴ c 为y和b的公约数
∴c≤d
同理可证 d≤c
∵d 为 y 和 b 的最大公约数
∴y|d b|d
∴ya|d
∴ya+b|d
∴d 为 x, y的公约数
∵c 为 x 和 y 的最大公约数
∴d≤c
∴c = d
等证。
所以 gcd(x, y) = gcd(y, x%y)