第3节　对于给定模求与给定剩余同余的数的方法

32

从上面的结论，解决问题“对于给定的模，求与给定剩余所同余的数的方法”是很容易的，在下面的讨论中也会很有用。指定模A，B，我们求数z，对于模A，B分别与数a，b同余。所有z的值都形如Ax＋a，x是未知数，而且要满足Ax＋a≡b（mod B）。现在如果数A，B的最大公约数是δ，同余方程的完整解的形式为x≡v（mod B/δ）或者用等价的等式表达，x＝v＋kB/δ，k为任意整数。因此，公式Av＋a＋kAB/δ包括了z的所有值，即z≡Av＋a（mod AB/δ）是这个问题的完整解。如果我们在模A，B的基础上再加一个模C，并且对于模C，z≡c，我们可以按照同样的方式开展，因为先前两个条件已经合并为一个。因此，如果AB/δ和C的最大公约数为e，并且假设同余方程（AB/δ）x＋Av＋a≡c（mod C）的解为x≡w（mod C/e），那么问题的解完全可以通过同余方程z≡ABw/δ＋Av＋a（mod ABC/δe）解得。我们观察到AB/δ是A和B的最小公倍数，ABC/δ是数A，B和C的最小公倍数，那么容易推出不论有多少个模A，B，C，…，如果它们的最小公倍数是M，全部的解都可以用z≡r（mod M）来表示。但是当并非所有的辅助同余方程都可解时，我们断定这个问题存在不可解的情况。但是显然，当所有的数A，B，C，…互质时，这种情况是不可能发生的。

例如，令数A，B，C，a，b，c分别为504，35，16，17，-4，33。这里的两个条件z≡17（mod 504）和z≡-4（mod 35）等价于一个条件z≡521（mod 2520），加上条件z≡33（mod 16），我们最终得到z≡3041（mod 5040）。

33

当所有数A，B，C，…都互质，可知它们的乘积是它们的最小公倍数。在这种情况下，多个同余式z≡a（mod A），z≡b（mod B），z≡c（mod C）…合起来就与单个同余式z≡r（mod R）等价，式中R是数A，B，C，…的乘积。反过来，单个条件z≡r（mod R）也可以分解为多个条件，即如果R以任意方式分解为互质的因数A，B，C，…，那么条件z≡a（mod A），z≡b（mod B），z≡c（mod C），…就把原始条件全部涵盖。这条结论不仅提供了一个发现方程无解的快捷的方法，也是一种令人满意的、优雅的运算方式。

34

如上，令z≡a（mod A），z≡b（mod B），z≡c（mod C）。将所有模都分解为互质的因数：A分解为A′A″A‴，…；B分解为B′B″B‴，…；使得数A′，A″，…，B′，B″，…要么都是质数，要么都是质数幂。如果数A，B，C，…中的任何一个数已经是质数或质数幂，则不用分解。可知，上述条件可以用下面的条件来代替：z≡a（mod A′），z≡a（mod A″），z≡a（mod A‴），…；z≡b（mod B′），z≡b（mod B″），…；…。现在如果不是所有的数A，B，C，…都互质（例如A和B非互质），显然A，B的所有质除数并非都各不相同。在因数A，A″，A‴，…中必定有一个因数在B′，B″，B‴，…能够找到等于它，或是它的倍数，或是它的除数的因数。假设第一个可能性是A′＝B′。那么条件z≡a（mod A′）和条件z≡b（mod B′）必定相同，即a≡b（mod A′或B′），因此其中一个可以忽略。但是如果z≡a（mod A′）不成立，这个问题就无解。其次，假设B′是A′倍数，那么条件z≡a（mod A′）就一定包含在条件z≡b（mod B′）中，即从后者推出的z≡b（mod A′）必须与前者相同。由此可以推出条件z≡a（mod A′）可以忽略，除非它与其他条件矛盾（如果这样问题便无解）。当所有多余的条件都忽略以后，因数A′，A″，A‴，…；B′，B″，B‴，…；…中剩下的模就都是互质的。然后我们就能确定问题是否可解，并按照上文描述的方法求解。

35

例如，如果按照上文（参考条目32），z≡17（mod 504），z≡-4（mod 35）和z≡33（mod 16），那么这些条件可以分解为下面的条件：z≡17（mod 8），z≡17（mod 9），z≡17（mod 7），z≡-4（mod 5），z≡-4（mod 7），z≡33（mod 16）。在这些条件中，z≡17（mod 8）和z≡17（mod 7）可以忽略，因为前者已经包含在条件z≡33（mod 16）中，后者同于条件z≡-4（mod 7）。还剩条件

并且从这些条件我们有z≡3041（mod 5040）。显然，通常这样做会比较方便：把从同一个条件推导出的剩下的条件分别重新组合：例如，当条件z≡a（mod A′），z≡a（mod A″），…中的一些被去掉之后，剩下的全部条件可以用z≡a取代，它的模是A′，A″，A‴，…中所有剩下的模的乘积。因此，在我们的例子中，条件z≡-4（mod 5），z≡-4（mod 7）都被条件z≡-4（mod 35）所取代。进一步可知，就简化计算来说，去掉多余的条件并不是无关紧要的。但是，讨论这些内容或其他具体的技巧并不是我们的目的，这些方法的学习通过自己实践比听他人讲述更加容易。

36

当所有的模A，B，C，D，…都彼此互质，通常采用下面的方法更好。确定一个数α，它对于模A同余于1，而对于剩余所有模的乘积同余为0，即α是BCD…乘以表达式1/BCD…（mod A）的一个值（优先选取最小值）（参考条目32）。类似地，令β≡1（mod B）及β≡0（mod ACD…），γ≡1（mod C）及γ≡0（mod ABD…），…。因此，如果我们求z使得它对于模A，B，C，D，…分别同余于a，b，c，d，…，我们可以取

z≡αa＋βbγc＋δd＋…（mod ABCD…）

因为，显然αa≡a（mod A）且剩下所有的数βb，γc，δd，…都对于模A同余为0，所以z≡a（mod A）。对于其他的模可以做类似证明。当我们解几个同样类型的问题，它们中的所有的模A，B，C，…的值保持不变，那么这种解法要优于前一种解法，因为α，β，γ，…取同样的值。在年代学中有这样的问题：给定某年的小纪，黄金数以及太阳活动周，确定它的儒略年份。在这里可以取A＝15，B＝19，C＝28；因为表达式1/（19×28）（mod 15）或1/532（mod 15）的值是13，所以α＝6916，按照同样的方法可得β＝4200和γ＝4845。因此，我们要求的数是6916a＋4200b＋4845c的最小剩余，其中a是小纪，b是黄金数，c是太阳活动周。