‘壹’ 中国剩余定理 —— 霸气的名字让我对这个算法产生了好感
当初探索算法，纯粹是因为它的名字——中国剩余定理，也被称为孙子定理。对这个算法感兴趣的朋友可以自行查阅它的原始名称。接下来，让我们深入探讨这个算法的精髓。
一、物不知数
【例题1】有一个未知数量的物品，当被三除时余二，被五除时余三，被七除时余二。请问这个物品的数量是多少？
这个问题是中国南北朝时期《孙子算经》中的经典问题，被称为“物不知数”问题。翻译成现代语言，即寻找一个整数，它除以3余2，除以5余3，除以7余2。用数学表达式表示为：[公式]，其中[公式]是公共的未知数。这种形式的方程组称为同余方程组，而[公式]就是这个同余方程组。
二、同余方程组
我们将同余方程组表示为更一般的形式：[公式]。我们知道，同余方程可以表示为等式的形式，因此同余方程组也可以表示为：[公式]。在这种情况下，有[公式]个方程和[公式]个未知数。在存在解的情况下，可能存在无穷多解。
1、不存在解
当存在[公式]和[公式]，同时满足[公式]且[公式]时，解必然是不存在的。因为任何数模另一个数的结果是确定的，不可能有两种结果。
2、存在无穷多解
一旦存在解，对于任意两个[公式]和[公式]，只要[公式]，必然满足[公式]。出现这种情况时，变量数和方程数同时减少，未知数永远比方程数多1，从而一定有无穷多解。
三、朴素算法
朴素算法采用穷举的方法，以“物不知数”问题为例，我们可以从零开始枚举[公式]的值，不断试除，直到找到满足三个同余方程同时成立的整数。对于这个特定问题，它形成了一个等差数列，并且公差是105，即所有模数的乘积。因此，我们猜测同余方程组的通解为：[公式]，其中最小的非负整数解为[公式]。
四、中国剩余定理
根据上述猜测，模数不互素的情况包含模数互素的情况。因此，我将直接介绍模数不互素情况下同余方程组通解的求解方式，即所谓的扩展中国剩余定理。虽然它没有“中国剩余定理”这个名字霸气，但重要的是理解算法原理。我们给同余方程组编号，并尝试合并第[公式]个方程和第[公式]个方程，得到新的同余方程。通过扩展欧几里德定理，我们可以求出最小的正整数解，并得到最终的通解。
五、算法实现
首先，设计一个类来表示方程，包含模数和余数。然后实现求解过程，包括标准化方程组、合并方程、利用扩展欧几里得定理求解等步骤。最终，算法将给出同余方程组的最小非负整数解。