“物不知数问题”的一般化
2019年8月29日星期四
本文接前文：
——《用现代数学方法解古题“物不知数”》
——《用“辗转相除法”将两数的最大公因数表成两数的线性组合》
——《完整例解增强版“物不知数”》
——《除数不满足“两两互素”条件的“物不知数问题”初探》
关于“物不知数问题”的一般化推广，本文打算分两步：
一、形如：ax≡b（mod m）或ax－b≡0（mod m）的一元一次同余方程组；
二、形如：f（x）≡b（mod m）或f（x）－b≡0（mod m）的一元同余方程组。
且以第一步为主介绍，第二步推广据说连数学家都没有找到好的求通解的方法。
文中图片均来自网络
一、f（x）＝a1x＋a0
数学符号总让人抓狂，且看古题改编：
“
今有物，不知其数。
二倍之，十五、十五数之，剩十四；
三倍之，十二、十二数之，剩三；
四倍之，十四、十四数之，剩八；
五倍之，九九数之，剩五。
问：物几何？
”
数学化：
方程组A：
2x≡14（mod 15） 式①
3x≡3（mod 12） 式②
4x≡8（mod 14） 式③
5x≡5（mod 9） 式④
或者：
2x－14≡0（mod 15）
3x－3≡0（mod 12）
4x－8≡0（mod 14）
5x－5≡0（mod 9）
这道题也是我精心设计的，因为它一定有解。胡乱构造一道这样的题，无解的可能性是很大的。
怎么解？似乎又有了新变化、新挑战，的确如此。
步骤1：
运用定理：
若：x≡b(mod m)， 则：kx≡kb(mod km)。 其中：x、b、m、k∈Z。
由于：［2，3，4，5］＝60
原方程组变为：
60x≡420（mod 450），取k＝30；
60x≡60（mod 240），取k＝20；
60x≡120（mod 210），取k＝15；
60x≡60（mod 108），取k＝12。
步骤2：
令：y＝60x
则有：
方程组B：
y≡420（mod 450） 式①
y≡60（mod 240） 式②
y≡120（mod 210） 式③
y≡60（mod 108） 式④
步骤3：
判断方程组B是否有解。
先对模进行标准素因子分解：
m1＝450＝2×3^2×5^2
m2＝240＝2^4×3×5
m3＝210＝2×3×5×7
m4＝108＝2^2×3^3
判断：
（m1，m2）｜（b2－b1）＝（450，240）｜（60－420）＝30｜（－360）
（m1，m3）｜（b3－b1）＝（450，210）｜（120－420）＝30｜（－300）
（m1，m4）｜（b4－b1）＝（450，108）｜（60－420）＝18｜（－360）
（m2，m3）｜（b3－b2）＝（240，210）｜（120－60）＝30｜60
（m2，m4）｜（b4－b2）＝（240，108）｜（60－60）＝12｜0
（m3，m4）｜（b4－b3）＝（210，108）｜（60－120）＝6｜（－60）
结论：方程组B有解。
步骤4：
拆解方程组B的合数模。
y≡420（mod 2）
y≡420（mod 9）
y≡420（mod 25）
——————
y≡60（mod 16）
y≡60（mod 3）
y≡60（mod 5）
——————
y≡120（mod 2）
y≡120（mod 3）
y≡120（mod 5）
y≡120（mod 7）
——————
y≡60（mod 4）
y≡60（mod 27）
将常数项继续模相应m运算得：
y≡0（mod 2）
y≡6（mod 9）
y≡20（mod 25）
——————
y≡12（mod 16）
y≡0（mod 3）
y≡0（mod 5）
——————
y≡0（mod 2）
y≡0（mod 3）
y≡0（mod 5）
y≡1（mod 7）
——————
y≡0（mod 4）
y≡6（mod 27）
去重：
y≡0（mod 2）
y≡6（mod 9）
y≡20（mod 25）
——————
y≡12（mod 16）
y≡0（mod 3）
y≡0（mod 5）
——————
y≡1（mod 7）
——————
y≡0（mod 4）
y≡6（mod 27）
整理：
y≡0（mod 2）
y≡0（mod 4）
y≡12（mod 16）
——————
y≡0（mod 3）
y≡6（mod 9）
y≡6（mod 27）
——————
y≡0（mod 5）
y≡20（mod 25）
——————
y≡1（mod 7）
保留高次幂模：
y≡12（mod 16） 式①
y≡6（mod 27） 式②
y≡20（mod 25） 式③
y≡1（mod 7） 式④
此时，模｛16，27，25，7｝满足“两两互素”的条件，是为方程组C。
从方程组A到B再到C，一路变形，皆恪守“等价变形”，否则就误入歧途了。
步骤5：
求方程组C的特解参数：v1、v2、v3、v4。
v1：｛m1，m2m3m4｝＝｛16，27×25×7｝＝｛16，4725｝
1＝886×16－3×4725（辗转相除过程略）
v1＝－3
——————
v2：｛m2，m1m3m4｝＝｛27，16×25×7｝＝｛27，2800｝
1＝－1037×27＋10×2800（辗转相除过程略）
v2＝10
——————
v3：｛m3，m1m2m4｝＝｛25，16×27×7｝＝｛25，3024｝
1＝121×25－1×3024（辗转相除过程略）
v3＝－1
——————
v4：｛m4，m1m2m3｝＝｛7，16×27×25｝＝｛7，10800｝
1＝1543×7－1×10800（辗转相除过程略）
v4＝－1
步骤6：
代入特解模型求出特解。
c＝v1（m2m3m4）b1＋v2（m1m3m4）b2＋v3（m1m2m4）b3＋v4（m1m2m3）b4
＝－3×4725×12＋10×2800×6＋（－1）×3024×20＋（－1）×10800×1
＝－170100＋168000－60480－10800
＝－73380
求通解。
y＝c＋k［m1，m2，m3，m4］
＝－73380＋k×［16，27，25，7］
＝－73380＋75600k
x＝y/60＝（－73380＋75600k）÷60＝－1223＋1260k
当k＝1时，得最小正数解：x＝37。
步骤7：
验证。
2×37÷15＝4……14
3×37÷12＝9……3
4×37÷14＝10……8
5×37÷9＝20……5
结论：
形如：f（x）≡b（mod m）的一元同余方程组中，当f（x）＝a1x＋a0时，可以完整解决。
二、f（x）＝anx^n＋……＋a3x^3＋a2x^2＋a1x＋a0
此时的一元同余方程组主要是指一元高次同余方程组，形如：
f（x）≡b1（mod m1）
g（x）≡b2（mod m2）
h（x）≡b3（mod m3）
……
其中：f（x）、g（x）、h（x）……全是关于不定量（或变量、未知数）x的多项式，且彼此间次数不见得一致。此时的求解一元同余方程组并不容易，甚至据说连一元二次同余方程组的通解都没能找到……要是再推广的话，可以有二元同余方程组、三元同余方程组、甚至更多……
f（x，y，z）≡b1（mod m1）
g（x，y，z）≡b2（mod m2）
h（x，y，z）≡b3（mod m3）
……
实非寻常人可为啊。
不过，对于一元同余方程组，哪怕是高次的，却是有一种“*力暴**”求解方法的，容后文介绍。