扩展欧几里得定理求ax + by = c 的通解

前置条件：

ax + by = c , gcd(a, b) = d

计算：

$\frac{a}{d}$x + $\frac{b}{d}$y = $\frac{c}{d}$ ；

设$\frac{a}{d}$ = a1 , $\frac{b}{d}$ = b1 ;

原式变为 a1x + b1y = $\frac{c}{d}$ ；

易知 gcd(a1, b1) = 1 ；

设 a1m +b1n = 1 ;

由扩展欧几里得算法可得 m0 为一个特解 ;

m = m0 + b1t , t 为任意整数 ;

则 a1x + b1y = $\frac{c}{d}$ 的通解为 ：

x = m * $\frac{c}{d}$ ；

一个特解为 x0 = m0 * $\frac{c}{d}$ ；

得到 x = x0 + $\frac{c b t}{d * d}$ ；（这里把b1换成了$\frac{b}{d}$）

所以 x = x0 + $\frac{bt}{d}$ ， t为任意整数 (因为 t 不一定是 d 的倍数， 所以不能约分)

在学CRT的时候自己琢磨的，如有错误，敬请斧正。