除数不满足“两两互素”条件的“物不知数问题”初探

　　2019年8月25日星期日

　　本文接前文：

　　——《用现代数学方法解古题“物不知数”》

　　——《用“辗转相除法”将两数的最大公因数表成两数的线性组合》

　　——《完整例解增强版“物不知数”》

　　先来看我“设计”的一个例子：

　　一元一次同余方程组A：

　　x≡17（mod　28） 式①

　　x≡3（mod　21） 式②

　　x≡39（mod　45） 式③

　　x≡9（mod　30） 式④

　　还原为古题是：

　　“

　　今有物，不知其数。

　　二十八、二十八数之，剩十七；

　　二十一、二十一数之，剩三；

　　四十五、四十五数之，剩三十九；

　　三十、三十数之，剩九。

　　问：物几何？

　　”

　　在这个例子中：

　　m1＝28、m2＝21、m3＝45、m4＝30；

　　b1＝17、b2＝3、b3＝39、b4＝9；

　　（m1，m2）＝（28，21）＝7

　　（m1，m4）＝（28，30）＝2

　　（m2，m3）＝（21，45）＝3

　　（m2，m4）＝（21，30）＝3

　　（m3，m4）＝（45，30）＝15

　　即：除数（或“模”）不满足“两两互素”的条件。

疯狂（文中图片均来自网络）

　　下面将通过该例初步探究除数不满足“两两互素”条件的“物不知数问题”的特点和解法。“物不知数问题”的数学实质是如何解“一元一次同余方程组”。本文中所有变量均在整数范围内讨论，为了便于理解，倾向于举非负例子。

一、任意给定的一元一次同余方程组是否有解（或解集是否为空）的判断

　　随便给出的一元一次同余方程组不一定有解，比如：

　　一元一次同余方程组B：

　　x≡1（mod　2） 式①

　　x≡2（mod　4） 式②

　　由B①可得：x＝2k＋1，即x为奇数；但由B②可得：x＝4k＋2，显然x是偶数；二者矛盾，同余方程组B无解。

　　这是一个极其简单的例子，目的在于说明：对于任给的一元一次同余方程组，第一位的目标并不是解方程，而是判断方程是否有解。

　　设有一般的一元一次同余方程组如下：

　　x≡b1（mod　m1） 式①

　　x≡b2（mod　m2） 式②

　　且（m1，m2）＝d。

　　我们给出一些小推理：

　　令：m1＝dk1、m2＝dk2

　　由于：

　　x≡b1（mod　m1）→x－b1＝m1q1→x＝m1q1＋b1

　　x≡b2（mod　m2）→x－b2＝m2q2→x＝m2q2＋b2

　　（说明：同余两数的差必为模的倍数）

　　所以：

　　m1q1＋b1＝m2q2＋b2

　→dk1q1＋b1＝dk2q2＋b2

　→d（k1q1－k2q2）＝b2－b1

　→d｜（b2－b1）

　　这个结论用直白的话说就是：只有当两个除数（或模）的最大公因数整除两个余数（或指方程中的常数项）的差时，该一元一次同余方程组才有解。这也是文首方程组A所以说是“设计”的原因，在方程组A中有：

　　（m1，m2）｜（b2－b1）＝（28，21）｜（3－17）＝7｜（－14）

　　（m1，m4）｜（b4－b1）＝（28，30）｜（9－17）＝2｜（－8）

　　（m2，m3）｜（b3－b2）＝（21，45）｜（39－3）＝3｜36

　　（m2，m4）｜（b4－b2）＝（21，30）｜（9－3）＝3｜6

　　（m3，m4）｜（b4－b3）＝（45，30）｜（9－39）＝15｜（－30）

　　所以，一元一次同余方程组A一定有解。

别急

二、模不满足“两两互素”且解集不为空的一元一次同余方程组的求解办法

　　核心思路是：将模不满足“两两互素”条件的一元一次同余方程组转化为等价的模满足“两两互素”条件的方程组。其关键是：实现等价转化。何为“等价”？具指方程形式变了，但是解集不能变！

　　举例说明：

　　x≡1（mod　15）的解集是：X1＝｛1，16，31，46，61，76，91……｝

　　x≡1（mod　3）的解集是：X2＝｛1，4，7，10，13，16，19……｝

　　x≡1（mod　5）的解集是：X3＝｛1，6，11，16，21，26，31……｝

　　观察思考可得：X1＝X2∩X3，即：解集X1是解集X2、X3的交集，而模的关系是：15＝3×5。

　　一般地，若：

　　x≡b（mod　m），且m＝m1m2，m1≠m2

　　则：

　　同余方程x≡b（mod　m）等价于以下同余方程组：

　　x≡b（mod　m1）

　　x≡b（mod　m2）

　　因为：

　　m｜（x－b）、m1｜m、m2｜m→m1｜（x－b）、m2｜（x－b）

　　其中，限制条件m1≠m2极端重要，来看下面的反例：

　　x≡0（mod　8）的解集是：X1＝｛0，8，16，24，32，40，48……｝

　　x≡0（mod　4）的解集是：X2＝｛0，4，8，12，16，20，24……｝

　　x≡0（mod　2）的解集是：X3＝｛0，2，4，6，8，10，12……｝

　　则：X1⊂X2⊂X3。可见，模是素因子2的3次幂（2^3＝8）的解集最小，2次幂（2^2＝4）的解集稍大，1次幂（2^1＝2）的解集最大。故而，拆解合数模的原则是：以不同的素因子为基本单位，当素因子的幂有大有小时，保留高次幂，舍去低次幂。

　　（重要程度）

耐心

　　下面开始等价转化：

　　（1）原方程组A

　　x≡17（mod　28） 式①

　　x≡3（mod　21） 式②

　　x≡39（mod　45） 式③

　　x≡9（mod　30） 式④

　　（2）拆解合数模

　　28＝2^2×7，式①等价于：

　　x≡17（mod　4），即：x≡1（mod　4）

　　x≡17（mod　7），即：x≡3（mod　7）

　　（17除以4余1，17模4同余1，x模4同余17，也就是x模4同余1；

　　17除以7余3，17模7同余3，x模7同余17，也就是x模7同余3）

　　21＝3×7，式②等价于：

　　x≡3（mod　3），即：x≡0（mod　3）

　　x≡3（mod　7），即：x≡3（mod　7）

　　45＝3^2×5，式③等价于：

　　x≡39（mod　9），即：x≡3（mod　9）

　　x≡39（mod　5），即：x≡4（mod　5）

　　30＝2×3×5，式①等价于：

　　x≡9（mod　2），即：x≡1（mod　2）

　　x≡9（mod　3），即：x≡0（mod　3）

　　x≡9（mod　5），即：x≡4（mod　5）

　　（3）合并

　　x≡1（mod　4）　式1

　　x≡3（mod　7）　式2

　　x≡0（mod　3）　式3

　　x≡3（mod　7）　式4

　　x≡3（mod　9）　式5

　　x≡4（mod　5）　式6

　　x≡1（mod　2）　式7

　　x≡0（mod　3）　式8

　　x≡4（mod　5）　式9

　　（4）去重

　　式2与式4相同，留一；式3与式8相同，留一；式6与式9相同，留一；式1与式7同余，对比保留高次幂模式1，舍去低次幂模式7。

　　x≡1（mod　4）　式1

　　x≡3（mod　7）　式2

　　x≡0（mod　3）　式3

　　x≡3（mod　9）　式5

　　x≡4（mod　5）　式6

　　式5与式3的模依然不互素，需要再次调整。由于式5拆解后可得式3，说明只要满足式5成立的解，必然满足式3，因此保留解集较小的式5，舍去式3。尽管式3与式5不同余，但依然满足“保留高次幂，舍去低次幂”的拆解原则。

　　（5）排序得模满足“两两互素”条件的同解方程组B

　　x≡1（mod　4）　式1

　　x≡4（mod　5）　式6

　　x≡3（mod　7）　式2

　　x≡3（mod　9）　式5

　　（6）解同解方程组B

　　详细过程略（有兴趣的读者可自行补充）。

　　特解：

　　c＝v1（m2m3m4）b1＋v2（m1m3m4）b2＋v3（m1m2m4）b3＋v4（m1m2m3）b4

　　＝－1×315×1＋（－2）×252×4＋3×180×3＋2×140×3

　　＝－315－2016＋1620＋840

　　＝129

　　通解：

　　x＝c＋k［m1，m2，m3，m4］

　　＝129＋k×［28，21，45，30］

　　＝129＋1260k

　　注意：通解中的m1、m2、m3、m4是指原方程组A中的模，且要取它们的最小公倍数，而不再是其乘积。

好神奇呀……

三、留个尾巴，大家练练手

　　x≡29（mod　36） 式①

　　x≡13（mod　20） 式②

　　x≡43（mod　70） 式③

　　可以在评论区切磋切磋。

请赐教！