当前位置:首页 > 经验

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

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

  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) 式③

  可以在评论区切磋切磋。

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

请赐教!

声明:此文信息来源于网络,登载此文只为提供信息参考,并不用于任何商业目的。如有侵权,请及时联系我们:fendou3451@163.com
标签:

  • 关注微信

相关文章