用中国剩余定理如何解一次同余式组 x≡3(mod5) x≡1(mod7) x≡4(mod9)
来源:学生作业帮助网 编辑:六六作业网 时间:2024/09/02 04:12:29
用中国剩余定理如何解一次同余式组 x≡3(mod5) x≡1(mod7) x≡4(mod9)
用中国剩余定理如何解一次同余式组 x≡3(mod5) x≡1(mod7) x≡4(mod9)
用中国剩余定理如何解一次同余式组 x≡3(mod5) x≡1(mod7) x≡4(mod9)
题:用中国剩余定理如何解一次同余式组 x≡3(mod5) x≡1(mod7) x≡4(mod9)
题目转化:x==(3;1;4) mod (5;7;9)
为打字方便,我常用双等号==代替三线等号≡表示同余.
敬告:请略花时间稍加琢磨,体谅我一片热心:
下面的解题过程,综合了我自2005年开始使用模积计数(表示)法与洪伯阳表示来解同余式组及后来作的一些进一步的阐述,
相信对同余式的解法是很好的简化,形式很为简洁.掌握了我的套路,很是省力.
解法形式上比较简明,只怕与传统方式变化太多,因此多加注解.其实,正是由于简明,所以稍加用心,十分容易理解.
如果不妥之处,疑问之处,敬请指教、交流,谢谢.
引子:
并量:为了叙述方便、形式的简明和思考之便捷,我引用一个新概念,称之为并量.
说起来很简单,也很容易转化.原同余式组各个式子是并列的,顺序无谓先后,可以交换;那么我们将其中同等地位的量并列在一起,用分号隔开;在不产生歧义对相同的量进行合并,称 为“并量”.并量概念由此延伸,可以不限于同余运算.矩阵可以看作是一种井字型(十字型,交午型)的并量,用并量来解释矩阵的运算,有些时候更加方便.
并量的性质:一、在同一个式子中,对所有的并量进行同样的顺序变换,不影响命题的条件与结果.二、在运算时,各个同等地位的分量可以形成一组进行独立计算.
缘起一:我以前曾多次使用类似方式,并且说明这种量具有类似向量的性质,比如可以线性叠加.
优点发微:前面写了这么多,其实很简单,首先是为了方便,为了叙述方便,形式方便,
由于思考是眼手脑多者并用,形式简明使眼、手、脑减轻了包袱,加强了协作,
结果竟然使得理解问题更加直接,快捷,即思考之便捷,理解之方便.
附注1:并量与普通向量也有显然的不同之处:
用分号对各个分量作间隔就是为了强调“并量”与“向量”概念不同.例如中间的运算符 mod,是由前一并量的分量作用于后一并量的对应分量.这个和向量的点积或矩阵的积有些类似.
我个人认为使用“并量”这种提议简明与直接,省去了用矩阵理论(相当于向量组理论)、算子理论来解释,不方便,有一点麻烦.
附注2:缘起详说,即说此概念的由来:
曾经使用普通向量的形式,后来改用分号间隔其各个分量,强调其与普通向量的不同.
此次专门定名为并量.
于是一组同余式,或者说一个同余方程(式)组,在形式上写成并量的同余式,或称并量的模余关系式.(外一则:还有并量的模积关系式.)
题目转化:x==(3;1;4) mod (5;7;9)
解一:中国剩余定理+原理略简化+并量表示
x== [mod (5;7;9)] [$以下用中括号括起或用$开头表示注解或公共说明]
(3;0;0)+
(0;1;0)+
(0;0;4)
== [以下==表示同余,在计算过程中允许表达式,表达式的返回值由箭头指定]
(63a<==3 mod 5) +
(45b<==1 mod 7)+
(35c<==4 mod 9)
== [心算a==1mod5, b==-2==5mod7,c==-4==5mod9,取其任意特值参予计算]
63-45*2-35*4
==-27-140 mod 315
==288-140
==148
解二:中国剩余定理+原理略简化+并量表示+洪伯阳同余表示+分数化速算法
x== [mod (5;7;9)] [$以下用中括号括起或用$开头表示注解或公共说明]
(3;0;0)+
(0;1;0)+
(0;0;4)
==
63 * (3/63 mod 5) +
45 * (1/45 mod 7)+
35* (4/35 mod 9)
== [以下//后面的项为分母,直到第一个结束符(如括号)为止]
5*7*9 *
(
(3/63 mod 5 // 5)+
(1/45 mod 7 //7)+
(4/35 mod 9 //9)
)
== [以下用|...|表示在分数计算时,不进行约分,并取分子值作为计算结果]
|
(3/63 mod 5 // 5)+
(1/45 mod 7 //7)+
(4/35 mod 9 //9)
|
==
|
1//5)+-2//7)+-4//9) mod 1==-3/35-4/9==32/35-4/9
|
==288-140==148
解二之过程提炼:
x== [mod (5;7;9)] [$以下用中括号括起或用$开头表示注解或公共说明]
(3;0;0)+
(0;1;0)+
(0;0;4)
==
|
(3/63 mod 5 // 5)+
(1/45 mod 7 //7)+
(4/35 mod 9 //9)
|
==
|
1//5)+-2//7)+-4//9) mod 1==-3/35-4/9==32/35-4/9
|
==288-140==148
解二过程之进一步精炼--模积计数法,模积表示法.定义
|
(3/63 mod 5 // 5)+
(1/45 mod 7 // 7)+
(4/35 mod 9 // 9)
|
== [用||表示模积表示.为简便,改用@或其它符号表示 mod,在不致混淆时可用很简单的符号,如<都行.当然在草稿纸上写,还可以省去很多规范符号,直接指向心髓.
另外注意: mod 的本质是 0类剩余类.即 a mod m= a + 0 mod m= a + [0] = a+ m**, [0]表示m的余数为0的剩余类,简称0类剩余类,**表示任意可变的整数值.]
||
3/63 @ 5;
1/45 @ 7;
4/35 @ 9
||
于是解二过程进一步变成:
x== [mod (5;7;9)] [$以下用中括号括起或用$开头表示注解或公共说明]
(3;0;0)+
(0;1;0)+
(0;0;4)
==
||
3/63 @ 5;
1/45 @ 7;
4/35 @ 9
||
==
||
1 @ 5
-2 @ 7
-4 @ 9
||
==
||
-3 @ 35==32
-4 @ 9
||
==32*9-4*35==148
解三:中国剩余定理.过程是是这样的:
先求得
A==(1;0;0) mod (5;7;9)
B==(0;1;0) mod (5;7;9)
C==(0;0;1) mod (5;7;9)
于是
X==3*A+1*B+4*C 就是所求的解了.在线性代数里面,就是先找到单位向量,再进行线性叠加.道理是一样的.
A,B,C是很好求的,例如求A:
A==1 mod 5, 同时A==0 mod (7;9),即A= 63a
如果习惯了并量这种形式,并直接理解它,就可以直接写成:
A=63a==1 mod 5, 解得a==2 mod 5,即是a=2+5k,取其任一个具体数值均不影响最终计算结果.
想想看,类似地,如何求B? (此处思考几分钟再看下面的最好)
同理写成:B=45b==1==3b mod 7, 解得b==-2 mod 7, 即b=-2+7j,可任取其特值.
同量,C==35c==1 mod 9, c==-1 mod 9, 即c=-1 + 9*t, 可任取其特值.
现在该来求X了.
X
==3*A+1*B+4*C mod (5;7;9)
==3*7*9a+1*5*9b+4*5*7c
==5*7*9*F
==5*7*9* (F mod 1)
F=(3a/5+1b/7+4c/9)
下面来计算()内的分数F.
F=6/5-2/7-4/9=32/35-4/9=(288-140)/(35*9)=148/(5*7*9)
故X==148 mod 315
因为 5*7≡ -1 (mod 9) ,7*9≡3 (mod 5) ,5*9≡3 (mod 7) ,
所以 -4*5*7≡4 (mod 9) ,1*7*9≡3 (mod 5) ,-2*5*9≡-6≡1 (mod 7) ,
因此 x≡-4*5*7+1*7*9-2*5*9(mod 5*7*9) ,
也即 x≡ -167≡148 (mod 315) 。
(5×7)×9=280=1(mod9)
(5×9)×5=225=1(mod7)
(7×9)×2=126=1(mod5)
所以3×280+1×225+4×126=1569
5×7×9=315
1569=309(mod315)
所以x=309+315n