# 最大公约数

若自然数 d ，同时是自然数 a 和 b 的约数，我们称 d 为 a 和 b 的公约数。而所有公约数中最大的，我们称为 a 和 b 的最大公约数，记为 gcd(a,b) 。

求最大公约数的算法有很多，比如：分解质因数、九章算术里的更相减损术、短除法等等。但是应用最广泛的还是今天的主角 -- 辗转相除法。

# 辗转相除法

古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法，所以又被命名为欧几里得算法。

辗转相除法依赖除法的一个基本性质（下面称为除法性质）：

假设 d|a ，同时 d|b ，那么一定有 d|(ax+by) 。

其中 | 表示整除的意思， d|a ，表示 d 可以整除 a 。既， a 是 d 的倍数，比如 3 可以整除 9 ，表示为 3|9 。

所以，这个性质的意思是，如果 d 能同时整除 a 和 b，那么 d 也能整除 a 的倍数加上 b 的倍数。

例如： 4 能整除 8 ，也能整除 12 ，那么 4 也能整除 8*3+12*5 （其中 3 和 5 可以取任意整数）。

通过这个性质，我们就能得到辗转相除法的最终公式： gcd(a, b)=gcd(b, a mod b) 。

当 a<b 的时候，有 a%b==a ，那么最终公式自然成立。
当 a>=b 的时候。首先看模数部分，先把模运算改成普通的四则运算： $a \bmod b = a - \frac{a}{b} * b$ (其中 $\frac{a}{b}$ 用来表示 a 除以 b 并向下取整)。
举例： $7 \bmod 3 = 7 - \frac{7}{3} * 3 = 7 - 2 * 3 = 1$ 。
在上面的公式中，因为 $\frac{a}{b}$ 一定是一个整数，我们用 x 来表示这个整数，那么，公式变成 $a \bmod b = a - x * b$ 。
把这个公式带入到最终结果中得到： $gcd(a, b)=gcd(b, a-x*b)$ 。
如何证明两面是相等的呢？
1. 先看左面，假设 d 为 a 和 b 的任意公约数，那么显然 d 可以整除 a 和 b ，再根据上面的除法性质，我们知道 d 也能整除 a-x*b (其中 a 的整数倍是 1 ， b 的整数倍是 -x )。又因为 d 是任意公约数，那么 d 也可以是最大公约数，所以 gcd(a,b)=d，gcd(b,a-x*b)=d ，推出 gcd(a,b)==>gcd(b, a-x*b) 。
2. 再看右面，假设 d 为 b 和 a-x*b 的任意公约数，那么显然 d 可以整除 b ，那么根据上面的除法性质，我们知道 d 也能整除 a-x*b+x*b (其中 a-x*b 的整数倍是 1 ， b 的整数倍是 x )，也就是 d 能整除 a 。同步骤 1 的推论，可以得出 gcd(b, a-x*b)==>gcd(a,b) 。
3. 综合步骤 1 和步骤 2，得出最终结论 gcd(a, b)=gcd(b, a mod b) 。

执行到最后的最终形态一定是 gcd (a, 0)。既，b=0 导致无法再进行除法运算，此时，最大公约数就是 a，同时这个 a 也是最后一个值不为 0 的 b。

裴蜀定理：关于任意的正整数 a,b，一定有非零数对 x,y ，可以让 ax+ay=gcd(a, b) 。

扩展欧几里得算法的作用就是求出其中的系数 x,y 。

在上一节，我们已经知道了欧几里得算法的最终形态： gcd(a, b)=gcd(b, a mod b) 。
根据裴蜀定理，现在有公式 ax+by=gcd(a, b) 。联立两个公式可以推出： ax+by=gcd(b, a mod b) 。
根据裴蜀定理，从 gcd(b, a mod b) 又可以推出 $gcd(b, a \bmod b)=by^\prime + (a \bmod b)x^\prime$ 。
代入 $a \bmod b=a - \frac{a}{b} * b$ 到上面的公式，并且联合最初的 $ax+by$ ，从而得到 $ax+by=by^\prime + (a - \frac{a}{b} * b)x^\prime$ 。
我们看一下其中 $x, y$ 与 $x^\prime,y^\prime$ 的关系。将上一步的公式展开：
$\begin{array}{c} ax+by = by^\prime + (a - \frac{a}{b} * b)x^\prime \\ = by^\prime+ax^\prime- \frac{a}{b} * b * x^\prime \\ = ax^\prime + b(y^\prime - \frac{a}{b} * x^\prime) \end{array}$
由此，我们得到了 $x, y$ 与 $x^\prime,y^\prime$ 的关系：其中 $x$ 原封不动的变成了 $x^\prime$ ，而 $y$ 变成了 $y^\prime - \frac{a}{b} * x^\prime$ 。该规则说明最终的 $x,y$ ，一定能通过子问题 $x^\prime, y^\prime$ 构造出来。
那么最初的 $x^\prime, y^\prime$ 是什么呢？我们注意到在欧几里得算法中，辗转相除到最后的子问题一定是 gcd(a, 0) ，那么对于等式 $gcd(a, 0)=ax^\prime+0*y^\prime$ ，如果让 $x\prime=1$ 一定成立。且由于 b 此时是 0，所以 $y^\prime$ 可以是任意整数，为了方便我们就让它也是 0。

输入示例：
2
4 6
8 18
输出示例：
-1 1
-2 1

在代码实现上，在辗转相除计算最大公约数的基础上，同时把系数 x,y 也求出来。其中有两点需要注意一下：

x,y 必须传递引用，否则在递归的过程中， x,y 都不相同的。如 exgcd(6,4) 中的 x,y 与 exgcd(4,2) 中的 x,y 与 exgcd(2,0) 中初始化出来的 x=1,y=0 都是不相同的，而我们最后要得到初始化的那个 x=1,y=0 中的 x,y ，所以在传参的时候要传引用。
因为求公约数是自顶向上的递归，而求系数 x,y 的时候是从 1,0 求到 x,y ，因此必须使用自底向上的递归，也就是把求 y 的部分放到求公约数之后。

对于没办法直接传递引用的语言 (“对，说的就是你，python”)，我们需要手动翻转 x 和 y 的值。