互素是什么意思（互素但不两两互素的四个整数）

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