除数不满足“两两互素”条件的“物不知数问题”初探
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） 式③
可以在评论区切磋切磋。
请赐教！
关注微信