扩展欧几里得算法

同余方程

\(ax\equiv b(\mod m)\)

二元一次方程

\(ax+by=c\)，其中\(a,b,c\)为已知的正整数

这两者可以相互转化，显然对于这个二元一次方程，有:
\(ax\mod b=c \mod b\),可以转化为\(ax\equiv c(mod b)\)

裴蜀定理

当我们考虑一个二元一次方程解的情况，我们发现：

• 1.可能无解
• 2.有解即有无数个解

所以问题转化为判断是否有解，所以出现了裴蜀定理：

设\(a,b\)为正整数，则\(ax+by=c\)有正整数解，当且仅当\(c\)是\(gcd(a,b)\)的倍数，注意 \(c\) 不需要是正整数。

辗转相除法

求 \(gcd(a,b)\) 的方法：
\(gcd(a,b)=gcd(b,a \mod b)\)。

扩展欧几里得算法：

扩展欧几里得算法致力于进一步找到解

• 1. 裴蜀定理判无解；
• 2. 若有解，先求方程 \(ax + by = \gcd (a, b)\) 的解，则原方程的一个解为 \(x = x \times \frac{c}{\gcd (a, b)}\)；
• 3. 递归求最大公约数，并利用，\(x = y_1, y = x_1 - \lfloor \frac{a}{b} \rfloor y_1\)。

如何求解：

1. \(ax + by = c\)。
2. \(bx_1 + (a - b \times \lfloor \frac{a}{b} \rfloor )y_1\)。
3. \(ay_1 + b(x_1 - \lfloor \frac{a}{b} \rfloor y_1)\)。

这样 \(x, y\) 与 \(x_1, y_1\) 就有关联了。