我们之前主要研究过整数二元一次不定方程 $$ ax + by = val $$ 的解 $(x,y)$ 构成的解集。
现在研究这样的同余方程 $$ ax \equiv val \mod b $$ 的解集。不妨要求 $a,b$ 是正整数，$a$ 取 $1$ 到 $b-1$ 的值。
$$ ax \equiv val \mod b $$
对于一个多项式 $a_n x^{n} + a_{n-1} x^{n-1} + \cdots + a_0$， 如果它的最高次项系数 $a_n$ 为 $1$，则称它为首一多项式。
研究一个多项式方程 $a_n x^{n} + a_{n-1} x^{n-1} + \cdots + a_0 = 0$ 的解， 如果能把最高次项的系数转化成 $1$ 又不影响解集，则称这个过程为首一化。
$$ ax \equiv val \mod b $$ 它的解集，要么无解，等价于另一个首一的同余方程的解集。
当我们求解一组方程的时候，实际上是在找同时满足这些方程的解。
这个过程其实可以看成，求各个方程对应的解集，然后找它们的交集。
可以想象有两种情况会导致方程组无解。
在求解方程组时，局部无解的话，一般就可以不往下算了，判断全局无解。
本来我们应该要求解同余方程组 $$ \begin{cases} a_1\cdot x \equiv val_1 \mod b_1 \\ a_2\cdot x \equiv val_2 \mod b_2 \\ \cdots \\ a_n\cdot x \equiv val_n \mod b_n \\ \end{cases} $$ 如何首一化？
通过前面叙述的过程，要么前面局部发现无解直接判断全局无解。反之就是要求解同余方程组，形如 $$ \begin{cases} x \equiv val_1 \mod b_1 \\ x \equiv val_2 \mod b_2 \\ \cdots \\ x \equiv val_n \mod b_n \\ \end{cases} $$
实际上，结果要么是空集，要么是另一个可以由同余方程确定的解集。后面我们就是要仔细研究其中的细节。
把它们先打回不定方程的形式，也就是说，对于 $x$，它属于两个集合的交，当且仅当存在 $y_1,y_2$，使得 $$ \begin{cases} x+b_1\cdot y_1 = val_1 \\ x+b_2\cdot y_2 = val_2 \\ \end{cases} $$ 同时成立。
假设下面能同时成立 $$ \begin{cases} x+b_1\cdot y_1 = val_1 \\ x+b_2\cdot y_2 = val_2 \\ \end{cases} $$ 那么理应有 $$ b_1\cdot y_1 - b_2\cdot y_2 = val_1 - val_2 $$ 什么时候上面这条式子肯定不成立，从而导出假设必然是矛盾的（即交集必然为空）？
$$ val_1 - val_2 \equiv 0 \mod \gcd(b_1, b_2) $$ 记 $g = \gcd(b_1, b_2)$，$t = \frac{val_1 - val_2}{g}$，也可以写成 $$ g\cdot b_1' \cdot y_1 - g\cdot b_2' \cdot y_2 = g\cdot t $$ （注意，$g,t,b_1',b_2'$ 的生成不依赖于 $y_1,y_2$。它们是取 $y_1,y_2$ 之前就可以提前写好的两个东西。 它们在这里只是为了方便书写，以及便于洞察性质而辅助定义的。）
可以看出，$y_1,y_2$ 应当满足 $$ b_1' \cdot y_1 - b_2' \cdot y_2 = t $$ 这可以推出，$y_1$ 在模 $b_2'$ 意义是一个定值。从而如果 $x$ 存在，则 $$ x = val_1 - b_1\cdot y_1 $$ 必然在模 $b_2'\cdot b_1$ 意义下是一个定值。把辅助定义的 $b_2'$ 写回来，即 $b_2'\cdot b_1 = \frac{b_1\cdot b_2}{\gcd(b_1,b_2)}$。
把合并后的解集记作 $L$，那么目前只是说明 $L$ 里面的元素模意义下不会有两种值。
即有模 $\frac{b_1\cdot b_2}{\gcd(b_1,b_2)}$ 等于某个定值 $r$ 的集合记为 $R$，
使得 $L\subseteq R$。
至于 $L$ 具体等于什么，甚至说是不是空集，都还没讨论完全。但这时会有一个操作能使得 $L$ 被确定：
构造一个 $R = \{x : x\equiv r \mod \frac{b_1\cdot b_2}{\gcd(b_1,b_2)}\}$ 并发现 $$ L\supseteq R $$
实际上这里存在一种简洁并且更适合拿来设计算法的方法，来找到这个值。对于 $b_1,b_2,g=\gcd(b_1,b_2)$，存在 $u,v$ 使得 $$ b_1 u + b_2 v = g $$ 取 $$ r = val_1 + \frac{val_2 - val_1}{g}\cdot u \cdot b_1 $$ 即可。（怎么验证？怎么记忆？）