一次同余方程组的简捷解法

第22卷第3期2006年9月

焦作师范高等专科学校学报

JOURNA L OF J IAOZ UO TE ACHERS CO LLEGE V ol 1221N o 13Sep 12006

一次同余方程组的简捷解法

常瑞连, 叶留青

(焦作师范高等专科学校数学系, 河南焦作454001)

　　摘要:应用孙子定理解一次同余方程组, 一是有局限性(模两两互质) , 二是在解题过程中求得n 个乘率αi (I =1, 2, …,

n ) 需要解n 个同余方程, 计算复杂, 解题过程思路单一, 突破传统思维模式, 把已知定理的条件加强得到新的解法%%“同余取倍法”。

关键词:一次同余方程组; 孙子定理; 同余取倍法

中图分类号:O156. 1　　文献标识码:A　　文章编号:1672-3465(2006) 03-0073-02

1　引言及引理

应用孙子定理解关于一次同余方程组的各类问题, 是现行初等数论教材中介绍的主要方法, 已成为我们解决此类问题时的重要思维模式. 在一次同余方程组这节教材中, 一般:

x ≡c 1(m od m 1)

引理1　　①有解的充分必

x ≡c 2(m od m 2)

要条件是(m 1, m 2) |(c 1-c 2) 。, 模[m 1, m 2]有唯一解n (n 。

x ≡a 1(m od m 1)

(即任一适合①式的整数适合②式; 反之, 任一适合②式的整

数也适合①式) .

β, 则同余方程组引理4　若α≥

αx ≡c 1(m od P x m β

α

) 的x ≡c 1(m od P

:先用定理1或, 再机械地套定理的重要条件是模m 1, m 2, …, m n 两两互质, 当模不是两两互质时, 但再应用引理3或引理4把两两不互质的模转化为两两互质的模.

孙子定理是我国古代数学家对数学的杰出贡献, 在数学史上颇负盛名, 被誉为中国剩余定理, 应用孙子定理解一次同余方程组, 一是有局限性(只有模两两互质时才能应用) ,

二是在解题过程中需要求得n 个乘率αi (i =1, 2, …, n ) , 这就需要解n 个同余方程, 解题过程思路单一, 死套模式, 计算复杂.

如何突破传统的思维模式, 去寻求一次同余方程组的简便解法. 本文把引理3的条件加强得到定理(3) , 灵活应用引理(或定理(3) ) , 引理4可以很简便地解一次同余方程组.

2　主要结论

x ≡a (m od m ) x ≡a (m od n ) c ≡a (m od m )

一般地, x ≡a 2(m od m 2)

……

x ≡a n (m od m n )

　有解的充要条

件是

(m i , m j ) |(a i -a j ) (i , j =1, 2, …, n ) 　(i ≠j ) .

如果这个条件成立, 那么它对于[m 1, m 2, …, m n ]只有唯一解.

引理2　(孙子定理) 设n ≥2, m 1, m 2, …, m n 是两两互质的正整数, 令m 1m 2…m n =M =m 1M 1=m 2M 2=…=m n M n .

x ≡c 1(m od m 1) x ≡c 2(m od m 2)

……

x ≡c n (m od m n )

α有且只有解x ≡M 1αod M ) . 1c 1+M 2α2c 2+…+M n n c n (m

α其中M

K 1(m od m K ) , K =1, 2, …, n. K ≡引理3　设m =…P 是模m 的素因子标准分解

式, 则同余方程x ≡a (m od m ) ①与同余方程组

α

x ≡a (m od P 11)

n n

定理(3) 若[m , n ]=p , 与同余方程x ≡(m od p ) ②等价.

①

αα

P 11P 22

α

.

c ≡a (m od n )

∴m |(c -a ) , n |(c -a ) , 即c -a 是m , n 的公倍数, ∵[m , n ]=p , ∴P |(c -a ) , ∴c ≡(m od P ) , 即c 也适合同余方

证明　设c 是适合①式的一个整数, x ≡a (m od

α

P 22)

……

x ≡a (m od P n n )

α

　②等价

程②.

反之, 如果c 是适合②式的一个整数, ∴c ≡a (m od P ) , P

|(c -a ) ,

　　收稿日期:2006-01-10

基金项目:河南省自然科学基金(0611056100) , 河南省教育厅教改项目(C2803) 资助。作者简介:常瑞连(1956-) , 男, 河南博爱人, 焦作师范高等专科学校数学系高级讲师。

・73・

焦作师范高等专科学校学报

∵[m , n ]=p ∴m |(c -a ) , n |

(n -a ) , c ≡a (m od m ) c ≡a (m od n )

.

∴c 也适合同余方程组①.

把余数化成相等, 是应用引理3(或定理(3) ) 解一次同余方程组的关键. 当数目比较小时, 可以直接观察应用同余变形得到. 当数目比较大时, 可以根据a ≡b (m od m ) Ζa =b mq (q ∈Z ) , 通过解二元一次不定方程来实现. 设x ≡c 1(m od m )

, 则x =c 1+ma , x =c 2+nb , c 1+ma =c 2+

x ≡c 2(m od n )

nb , ma -nb =c 2-c 1①. 只要求解关于a , b 的二元一次不定

方程①就可以把余数化为相等(求解二元一次不定方程时, 只需要求出一个未知数的特解) .

应用新方法解一次同余方程组的步骤是:1. 根据定理1或其推广形式判断形方程组是否有解; 2. 若方程组中有相同的余数或模之间有倍数关系, 直接应用引理3(或定理(3) ) , 引理4把方程组中的子方程组化为方程; 3. 将方程组中的方程两两组合, 通过同余变形或解二元一次不定方程把余数化成相等, 使之能应用引理3(或定理(3) ) . 3　实例

例1(韩信点兵) :有兵3万多, 若均分成5营, 则余

1人; 均分成6营, 则余5人; 均分成7营, 则余4人; 均分成11营, 则余10人; 均分成13营, 则余5人. 求兵数.

解　设兵数为x , 30000

≡5(m od13)

因为5, 6, 7, 11, 13两两互质, 所以①有解.

x ≡1(m od5) x ≡5(m od78)

解题过程为:①]　②]

x ≡4(m od7) x ≡10(m od11)

x ≡11(m od5)

x ≡11(m od35)

x ≡5(m od78)

　③]x ≡5(m od78) 　④]

x ≡11(m od7)

x ≡10(m od7)

x ≡10(m od11) x ≡186(m od35)

x ≡186(m od385)

　

⑤]　⑥]x ≡5(m od78)

x ≡5(m od78)

x ≡186(m od11) x ≡3275381(m od385)

　⑦]x ≡3275381≡2111(m od30030) 　

x ≡3275381(m od78) ⑧

说明:根据引理3由①得②, 观察后同余变形得③, 根据引理3得④, 这时直接观察同余变形比较困难, 设11+35a =10+11b , 解不定方程11b -35a =1, 得b =16, 16×11+10=186, 由此得到⑤, 由定理3得⑥, 设186+395a 1=5+78b 1, 解不定方程78b 1-385a 1=181得b 1=41992

41992×78=3275376, 327576+5=3275381, 由此得到⑦[78, 385]=30030, 由引理3得到⑧.

) 一般解是X =2111+30030t , (t =0, 1, 2, …

根据题意有30000

∴x =2111+30030×1=32141. 答:兵数为32141人. 当方程组中的模不是两两互质时用新方法解更简单.

x ≡2(m od35)

例2　x ≡9(m od14) ①

x ≡7(m od20)

解　由引理1的推广式判定①有解. 解答过程为:

x ≡2(m od35)

x ≡2(m od35)

①]x ≡　③]x 107(m od14) 　②]

x ≡107(m od140)

x ≡107(m od20)

≡107(m od140) .

说明:由①设9+14a =7+20b , 即10b -7a =1, 观察得b =5, 由此得到②, 由定理(3) 得到③, 再由引理4得同余方程组①的解为x ≡107(m od140) .

传统解法立足于应用孙子定理, 忙于求各个模的乘积M 、衍数M i 、乘率αi 等, 不再对原方程组中的各个方程进行观察, 以至许多简便方法被埋没.

下面两例用新方法解就很简捷.

(物不知数”例3　“问题) 设物的个数为x , 则

x ≡2(m od3) x m od5) . 3, , . 由引x ≡2)

2(m od21)

x () , 观察后同余变形易

x ≡3(m od5)

x ≡23(m od21) , 再由引理3得x ≡23(m od105) , 所以物的

x ≡23(m od5)

x =23+105k , k ∈N.

例4　十一数余三, 十二数余二, 十三数余一, 问本数. 解:(注:若应用孙子定理比较复杂) 设本数为x , 则x ≡3(m od11) x ≡2(m od12) . 因为11, 12, 13两两互质, 所以方程组有解. x ≡1(m od13)

x ≡14(m od11)

x ≡14(m od12) , 由引理3得, 所以本数是

x ≡14(m od13)

14+1716k , k ∈N. 4　结束语

新的解法简称为“同余取倍法”, 即当余数相同时取模的最小公倍数作模, 将方程组的子方程组化为方程, 逐步减少方程组中方程的个数. 只要方程组有解, 都可以用这种方法直接解. 这可以看作引理3和引理4的角色转换, 在传统的解法中, 当模不是两两互质时, 只是应用这两个定理进行转化, 新解法是以这两个定理作主要理论根据, 思维的导向是寻求相同的余数. 把同余变形与解二元一次不定方程有机地结合起来, 通过不断观察、转化, 既促进了学生思维能力的发展, 又简化了一次同余方程组的解法.

[参考文献]

[1]闵嗣鹤, 严士健. 初等数论[M].北京:高等教育出版社,2003. [2]教材编写委员会. 初等数论[M].北京:开明出版社,1996. [3]潘承洞, 潘承彪. 初等数论[M].北京:北京大学出版社,2001.

　

・74・