下面简单记录如何用“扩展欧几里德算法”解线性方程组Ax + By = C
（1）先判断是够存在解
首先，Ax + By = C 式子存在解的条件是：C为A和B最大公约数gcd(A,B)的整数倍。否则式子左边除以gcd(A,B)仍为整数，右边除以gcd(A,B)就不是整数了。所以有解的条件是C = n*gcd(A,B)。
如何快速算出gcd(A,B)，大一教C的时候很熟悉了，就是欧几里德提出的辗转相除法，核心定理为gcd(A, B) = gcd(B, A mod B)。
证明：
设r = A mod B，则A = kB + r。不妨设d为A和B的任意一个公约数，则A = pd，B = qd。那么r = pd - qkd = (p - qk)d。d也是r的约数，因此d是B和A mod B的公约数。因此gcd(A, B) = gcd(B, A mod B)。
递归代码为：
gcd(A,B) {
if (A mod B == 0) {
return B
}
return gcd(B, A mod B)
}
（2）求解
Ax + By = C，由于A，B，C均为gcd(A, B)的整数倍，因此首先将它们都缩小gcd(A,B)倍，得到A’x + B’y = C’，A’ = A / gcd(A, B)等。（PS：这一步很重要，后面再解释。）
现在，问题转换为求A’x + B’y = C’的解。我们可以先求A’x + B’y = 1的解(x’, y’)，然后扩大C’倍，得到最后解(x, y) = (C’x’, C’y’)。
所以问题紧接着转换成如何求A’x + B’y = 1的解(x’, y’)。
再求(x’, y’)之前，我们需要了解一个基本定理：
对于不完全为0的非负整数A, B, gcd(A,B)，必然存在整数对x, y（和上面的x, y表示不一样）使得Ax + By = gcd(A,B)
利用上述定理，我们假设
A * x[1] + B * y[1] = gcd(A, B)
B * x[2] + (A mod B) * y[2] = gcd(B, A mod B)
由于gcd(A, B) = gcd(B, A mod B)，因此：
A * x[1] + B * y[1] = B * x[2] + (A mod B) * y[2]
=> A * x[1] + B * y[1] = B * x[2] + (A - kB) * y[2] // A = kB + r
=> A * x[1] + B * y[1] = A * y[2] + B * x[2] - kB * y[2]
=> A * x[1] + B * y[1] = A * y[2] + B * (x[2] - ky[2])
=> x[1] = y[2], y[1] = (x[2] - ky[2])
显然，利用x[1] = y[2], y[1] = (x[2] - ky[2])，其中k = A/B，我们可以递归求解得到(x1, y1)。递归终止条件为B = 0，此时对应的方程A * x[1] = gcd(A,B)，那么(x, y) = (1, 0)，这个算法可以称作“扩展辗转相除法”。
此时的解(x1, y1)是方程A * x[1] + B * y[1] = gcd(A, B)的解，其和A’x + B’y = 1的解(x’, y’)是等价的，因为A’ = A / gcd(A, B)，所以第一步缩小gcd(A,B)倍在这一步就起作用了。然后别忘了把解(x’, y’)乘以C’得到A’x + B’y = C’的解，此解也和原问题Ax + By = C解等价，也就是最终我们要求的解。
PS: 另外，往往在许多题目中要求求出的解x为所有解系(x, y)中最小的非负整数，如何保证？
上一步，我们能顺利地求出一组合法可行解，但不能保证x是最小的非负整数。此时，我们需要将方程A’x + B’y = 1的解(A’,B’,x’,y’)扩充为一个解系：
A'x' + B'y' + (u + (-u))A'B' = 1
=> (x' + uB')*A' + (y' - uA')*B' = 1
=> X = x' + uB', Y = y' - uA'
可以求得最小的 X = (x’ + uB’) mod B’，(x’ + uB’ > 0)。同时我们需要将X扩大C’倍，因此最后的解为x = (x’*C’) mod B’。 在实际做题过程中，防止x’ * c’溢出，可以这么做x = ((x’ % B) * (c’ % B)) % B，这对%操作是等价的。
算出来的x有可能为0，则不断累加B’，直到x > 0为止。