同余方程

下文中 \(a/b\) 指整数除法，即 \(a=kb+r\) 那么 \(a/b=k\)。
常见转化（有启示意义）会用 \(\mathbf{mathbf}\) 加重显示。

1.Exgcd (扩展欧几里得算法)(求解二元一次不定方程/单个线性同余方程)

引理 1：\(gcd(a,b)=gcd(b,a \bmod b)\)

证明：

令 \(gcd(a, b) = g\)，设 \(a=g \times k_1, b = g \times k_2\)。
那么 \(\mathbf{a \% b = (k1 \% k2) \times g}\)。

因为都有公因子 \(g\)，所以 \(b\) 和 \(a \bmod b\) 之间一定有公因子 \(g\)。
要证最大公因数是 \(g\) 只需证 \(k1 \% k2\) 和 \(k2\) 互质。

反证法：假设它们之间有公因数 \(t>1\)，设 \(k1 \% k2 = t \times q, k2 = t \times p\)。
那么 \(a = g \times (ktp+tq)\) 有因子 \(t\)，同时 \(b = g \times tq\) 也有因子 \(t\)，与假设矛盾。

故原命题成立。

现在我们要做的事情是解同余方程 \(ax \equiv k \pmod b\)，其等价于二元一次不定方程 \(ax + by = k\)。

引理 2（即 exgcd 原理）：上述方程对于 \(k | gcd(a, b)\) 总有整数解，否则总没有整数解。

证明：

第二句话显然成立，不论 \(x,y\) 取得什么值，\(ax+by\) 一定会有因子 \(g\)。

为了证明第一句话，并求出这个方程的解，我们考虑 \(k = gcd(a, b)\)。

我们已经证明出引理 \(1\)，那么可以将 \(ax + by = gcd(a, b)\) 规约成另一个方程 \(bx' + (a\%b)y' = gcd(b, a \% b)\)，方便递归计算：
我们现在假设求出了第二个方程的解，那么 \(bx' + (a - (a/b) \times b)y' = g\)
也即 \(ay' + b(x' - (a/b)y') = g\)
因此第一个方程的解为：
\(x = y'\)
\(y = x' - (a/b)y'\)

当 \(b=0\) 时，\(x=1,y=0\) 即函数出口，因此可以得出解。

当 \(k = k' \times gcd(a, b)\) 时，只需要将 \(x,y\) 的值都对应乘上 \(k\) 即可。