星空22222仰望
范文一：同余方程的解法（可编辑）
同余方程的解法
包头师范学院
本 科 毕 业 论 文
题 目: 同余方程的解法 学生姓名:
学 号: 专 业: 数学与应用数学
班 级: 指导教师:
二 ?一年 四 月
摘要:
本文论述了同余方程的基本概念及同余方程的一些基本性质与解法,主
要对一次同余方程的解法进行了探讨,特别是对一次同余方程的欧拉定理算法,
欧几里德算法等七种解法进行了比较与分析,并介绍了同余方程组、孙子定理、
素数模的同余方程,模 的同余方程的解法。
关键词: 同余 同余方程 孙子定理Abstract:
This paper mainly discusses the basic concepts of congruence equations and congruence equation some of the basic nature of solution,and highlights the Remainder Theorem,solution of the congruence equation,mod congruence equation solution,congruence equation of primes mode solution,etc.
Key words: CongruenceCongruence equation Remainder Theorem
目录
引言 1
1.同余与同余方程的基本性质 2
1.1 同余的概念与基本性质 2
1.2同余方程的概念与性质 3
2.一次同余方程的解法 4
2.1 的情况 4
2.2 的情况 7
3.同余方程组的解法 8
3.1简单同余方程组的解法 8
3.2 孙子定理 9
4.高次同余方程的的解法 11
4.1素数模的同余方程 11
4.2模p的同余方程 12
总结: 17
参考文献 18
致谢: 19
引言
对于同余方程的解法国内外的数学家们均对其做出了非常全面与细致的研究。在我国古代的数学名著《孙子算经》中就较早的给出了同余方程的算法即著名的“孙子定理”。我国宋代的大数学家秦九?,也在他的杰作《数书九章》中也对同余方程的解法进行了系统的研究。教材中对于同余方程的解法虽然给出了一些方法,但对其研究还不够全面不彻底。所以对于同余方程的解法进行归纳总结,从而作进一步的研究就显得特别重要。
1.同余与同余方程的基本性质
1.1 同余的概念与基本性质
定义1 给定一个正整数,如果用去除两个整数所得的余数相同,那么称对模同余,记作;否则,称同余.记作
定理1 设是一个正整数,是两个整数,则的充要条件是存在一个整数使得
定理2 模同余是等价关系,即 (i)(自反性)对任意整数,; (ii)(对称性)若, 则; (iii)(传递性)若,
定理 3 整数同余的充分必要条件是除的余数相同.
定理4 设一个整数, 是四个整数.如果
, 从而,
,定理 5 若, 则定理6设一个正整数,.如果则定理7 设一个正整数,, 则 定理 8 设一个正整数,,如果整数则
定理9 设是一个正整数,, 如果.
定理10 设是一个正整数, , , 则
定理11 设是一个正整数,1.2同余方程的概念与性质
定义2 设是整系数多项式,称 1
是关于未知数的模的同余方程,简称为模的同余方程。
若,则称为次同余方程。
定义3 设是整数,当时式1成立,则称是同余方程的解。凡对于模同余的解,
被视为同一个解。同余方程1的解数是指它的关于模互不同余的所有解的个数,
也即在模的一个完全剩余系中的解的个数。
由定义3,同余方程1的解数不超过
定理12 下面的结论成立:
? 设是整系数多项式,则同余方程1与
等价;
? 设是整数,,则同余方程1与
等价;
? 设是素数,都是整系数多项式,又设是同余方程1的解,则必是同余方程 的解。
2.一次同余方程的解法
定理13 同余方程
? 若有唯一解
? 若,没有解
? 若, 有个解
2.1 的情况
2.1.1观察法
在模的完全剩余系中考虑同余式的解,此方法适用在当模较小时或方程具有
特殊形式的一次同余方程里
例1:的解为
2.1.2欧拉定理算法
由欧拉定理有,而可得
既得:为所求的解。此解法适合较小或较易求解
例2:解
解,
2.1.3化为不定方程的解法
有解存在整数使得。即不定方程有解。此解法对模的要求较低。 例3:解
解:原方程对应的不定方程为
其通解为(对任意的整数)
,
所以
2.1.4减小模数的解法
对于 此时,然后去掉中的倍数不断将模变小此时若有解,则为的解。 经过几次转换后一般可以用观察法求解,在递推出原方程的解。此方法适合
模数较大的同余方程。
例4:解同余式
解:原同余式即是:,解同余式:
得:,所以原同余式的解是:
2.1.5欧几里得算法
可借用辗转相除法求整数的最大公因数的方法,结合同余式的性质,可转化
为一个形如的同解方程。当利用恒等变形将变小,直至将的系数化为1. 若, 且模数较大时, 可用取余的办法, 将变小, 然后求出解。 例5: 解同余式.
解: ?, ?原同余式有1 个解。
?,
而 ,
,
。
?,
而
?,
,
即为原同余式的解。
若, 且中至少有一个数大于m , 可根据同余知识, 将化小, 再用方法去解。
例6: 解
解: ?,
?原同余式化为:
?,
而,
?。
又 ,
?。
?为原同余式的解。
2.1.6分式法
先把写成的形式(这里是一种形式的写法)然后用与互素的数陆续的乘又端
的分子和分母,目的在于把分母的绝对值变小,直到变成1为止。此方法使用模不
太大如三位数或三位数以内的。
例7:解同余是
解
2.1.7威尔逊定理解法
为素数,由威尔逊定理有:此方法适用模为素数且模不能太大。
例8:解
解
2.2 的情况
, 有个解
2.2.1化为法
对于先用去除同余式,在按的情况去解。 例9:求的解
解原方程有4个解。用4去除同余式得: 而
,原同余式的解为
2.2.2消去的系数解同余式
逐次消去的系数
例10: 解同余式。
解:因为,同余式有个解。
原同余式可化简为,,
与的公因数与互质,可消去公因数,同余式进一步化简为:
。与的公因数与互质,可消去公因数,同余式可化简为:,是的倍数故:。原同
余式的个解为:。
利用辗转相除法消去 的系数
对于系数较大、较复杂的同余式, 可以采取辗转相除法消去 的系数。
例11:解同余式
解:因为同余式有个解。
化简:,用辗转相除法
,将上述过程反演得到:
所以:
因为
同余式的5个解为:
3.同余方程组的解法
3.1简单同余方程组的解法
对于同余方程组(1)
当时的简单解法。
例12解同余方程组
。2
解 : 将2的前一式乘以2后一式乘以3再相减得到
再代入2的前一式得到
即同余方程组2的解是。
3.2 孙子定理
定理14孙子定理 设是正整数, 记
, ,,
则存在整数,使得
,
并且(3)
是同余方程组1对模的唯一解,即若有使方程组1成立,则
。
定理15 同余方程组1有解的充要条件是定理16 设,其中是两两互素的正
整数,是整系数多项式,以与分别表示同余方程 与
的解的个数,则
例13求整数,它被除的余数分别是 解:是同余方程组
的解。根据孙子定理,取
则
因此所求的整数
例14解同余方程
。 4
解: 因为,所以,由定理16可知,同余方程4等价于
同余方程组 5 67
分别解同余方程5,6,7得到解
,
,
,
同余方程4的解可转化为下面的方程: ,
其中或,或。
利用孙子定理,取
则
。
将所有可能的取值代入上式,得到方程4的全部解是
,
,
,
。
4.高次同余方程的的解法
4.1素数模的同余方程
设是整系数多项式,是素数, 。
定理17 设若同余方程 1
有个不同的解则对于任意的整数有
,
其中是一个次数为的整系数多项式,并且它的项的系数是 定理18 同余方程1的解数
定理19 同余方程1与一个次数不超过的质数模同余式等价。
定理20 设,则同余方程
有个解的充要条件是存在整数多项式和,的次数使得 定理21 定理若是素数,则
例15判定同余方程是否有三个解。
解: 因为,所以,原方程与
即等价。由于
所以,由定理20和定理18可知,原方程的解数小于。 例16解同余方程
。
解: 由定理,,
又因为
因此,由定理19原同余方程等价于:
即 。 (2)
将分别代入方程(2)进行验证,可知这个同余方程解是 4.2模p的同余方程
求解模的同余方程可以转化为对模的同余方程的求解。 若是同余方程 1
的解,则它必是方程 2
的解,因此,必有与相应的方程2的某个解,使 ,
此处,是某个适当的整数。
定理22设是素数,是整数,是整系数多项式,又设是同余方程2的一个解。以
表示的导函数。
? 若,则存在整数,使得3
是同余方程1的解。
? 若并且,则对于,式3中的是方程1的解。 由定理,可以把解同余方程1,转化为解同余方程 。4
由方程4的解,利用定理,可以求出方程的解,再利用定理,又可以求出方程
的解,,直到求出方程1的解。
推论1 使用定理的记号,
? 若是同余方程4的解,并且,则存在,使得是同余方程1的解。
? 若与同余方程4没有公共解,则对于任意的整数,同余方程1与4的解数
相同。
例17解同余方程
。
解: 根据定理16 原同余方程等价于同余方程组 , 5
。 6
先解同余方程5。同余方程的解是。
令并代入方程5,得到
, 7
由定理22?这是一个对于任何整数t都成立的同余式,所以,方程7的解是,
于是方程5的解是
。 8
再解同余方程6。用去验证,得到6的解是 。
因此,原同余方程的解是下面六个同余方程组的解:
利用孙子定理解这六个方程组,记
,
则
。
将
,
,
,
,
,
。
例18解同余方程 。9
解: 同余方程10 有两个解。
令
, 11
代入同余方程
, 12
得到
,
,
。 13
于是,将式11与式13联合,得到方程12的解
。 14
将式14中的代入同余方程9,得到
,
,
,
。
将上式与14联合,得到同余方程9的一个解
。
从同余方程10的另一个解出发利用上述方法,可以求出同余方程9的另一个
解为。
例19解同余方程
。 15
解: 若,则方程15的解是。 若,则方程15的解是。 若,则同余方程15,即
,
的解必是奇数,设,则同余方程1成为
,
。 16
同余方程16的解是,即 ,
所以,方程15的解是
,
即
。
总结:
本文应用前人的研究成果,对同余方程的常用解法进行了系统的归纳总结,并对其解法进行了进一步的研究优化。其主要对一次同余方程的解法进行了详细的介绍,其次对用孙子定理来解同余方程组做了初步的总结,最后叙述了素数模及模的同余方程的解法,但本文只是讲了一些同余方程的常见解法,希望读者在这方面有更好更多的见解。
参考文献
柯召,孙琦.数论讲义上册[M]. 高等教育出版社,北京,2001年 闵嗣鹤,严士健.初等数论第三版[M].高等教育出版社,北京,2003年 潘乘洞、潘乘彪.初等数论[M].北京大学出版社第二版,北京,2003年 杜德利.基础数论[M].周仲良,译.上海科技出版社,上海1982年 刘合义.谈数论中的同余及其应用[J].衡水师专学报,2002年
原新生.一次同余方程的几种解法[J].牡丹江教育学院学报,2009年
致谢:时光匆匆,如白驹过隙。在毕业论文定稿之际,四年的大学本科生活也即将画上句号。遥想初入大学之时,还历历在目,恍如隔日,不免感叹光阴易逝、韶华难追。然而,艰辛而快乐的求学之路,也给我留下了很多难以忘怀的欣慰和幸福。在此,向四年来陪伴我一起走过,给予我帮助和关心的良师益友以及亲人们,致以最为真挚的谢意! 我衷心的感谢我的导师李晓冬老师,她在我毕业设计的题目选择上给与了非常大的帮助,并且在整个毕业设计过程中一直指导、鼓励着我,使我能够顺利完成毕业设计的工作。
范文二：同余方程的解法 毕业论文
题 目: 同余方程的解法 学生姓名: 学 号: 专 业: 数学与应用数学 班 级: 指导教师:
二 〇一 年 四 月
摘要:
本文论述了同余方程的基本概念及同余方程的一些基本性质与解法，主要对一次同余方程的解法进行了探讨，特别是对一次同余方程的欧拉定理算法，欧几里德算法等七种解法进行了比较与分析，并介绍了同余方程组、孙子定理、素
,p 的同余方程的解法。 数模的同余方程，模
关键词: 同余 同余方程 孙子定理
Abstract:
This paper mainly discusses the basic concepts of congruence equations and congruence equation some of the basic nature of solution,and highlights the Remainder Theorem,solution of the
,p congruence equation solution,congruence congruence equation,mod
equation of primes mode solution,etc.
Key words: Congruence Congruence equation Remainder Theorem
目录
引言 ...................................................... 1 1.同余与同余方程的基本性质 ............................... 2
1.1 同余的概念与基本性质 .............................. 2
1.2同余方程的概念与性质 ............................... 3 2.一次同余方程的解法...................................... 4
a, m 1,2.1 的情况 ................................... 4 ，，
2.2 amd,1,,的情况 ................................... 7 ，，
3.同余方程组的解法........................................ 8
3.1简单同余方程组的解法 ............................... 8
3.2 孙子定理........................................... 9 4.高次同余方程的的解法 .................................. 11
4.1素数模的同余方程 .................................. 11
,4.2模p的同余方程 .................................... 12 总结: ................................................... 17 参考文献 ................................................. 18 致谢: ................................................... 19
引言
对于同余方程的解法国内外的数学家们均对其做出了非常全面与细致的研究。在我国古代的数学名著《孙子算经》中就较早的给出了同余方程的算法即著名的“孙子定理”。我国宋代的大数学家秦九詔，也在他的杰作《数书九章》中也对同余方程的解法进行了系统的研究。教材中对于同余方程的解法虽然给出了一些方法，但对其研究还不够全面不彻底。所以对于同余方程的解法进行归纳总结，从而作进一步的研究就显得特别重要。
- 1 -
1.同余与同余方程的基本性质
1.1 同余的概念与基本性质
ab和定义1 给定一个正整数，如果用去除两个整数所得的余数相同，mm
abm，对模不那么称对模同余，记作a,b mod m;否则，称同余.记ab，m，，
作a,b mod m ，，
a,b定理1 设是一个正整数，是两个整数，则a,b mod m的充要条件是存m，，在一个整数使得 ka,，bkm
定理2 模同余是等价关系，即 m
aa,(mod m) (i)(自反性)对任意整数,; a
b(mod m,a) (ii)(对称性)若a,b mod m, 则; ，，
(iiia,b mod m)(传递性)若, bcmod m,cmod m,,()则()a，，
定理 3 整数同余的充分必要条件是除的余数相同. a, bm对模a, bm被
m是定理4 设一个整数， 是四个整数.如果 a,a,b,b1212
a,b mod ma,b mod m , 从而， ，，，，1122
mod m aabb，,，aabb,mod m， ，，，，12121212
x,y mod m ab,,, mod m ,0ik,定理 5 若, 则 ，，，，ii
kkaaxaxbbyby，，，,，，，......mod m ，，0101kk
m是ad,bd mod m d , m 1,,定理6设一个正整数，.如果则 ，，，，a,b mod m ，，
m是 0,k,a,b mod mak,bk mod m定理7 设一个正整数，, 则 ，，，，
m是a,b mod md | a , b , m,定理 8 设一个正整数，,如果整数则，，，，
abm,,,mod ,,ddd,,
- 2 -
d | m,定理9 设是一个正整数，a,b mod m, 如果则ab mod d,. m，，，，
i1, , k,？定理10 设是一个正整数， , , 则a,b(modm)mi
amm,？b(mod[, ,]) .1k
定理11 设是一个正整数， b mod m,, m b , maa,,则.. m，，，，，，1.2同余方程的概念与性质
n定义2 设fxaxaxa ,，，，是整系数多项式，称 ，，10n
fxm,0 mod (1) ，，，，是关于未知数的模的同余方程，简称为模的同余方程。 xmm
a,0 modm若，则称为次同余方程。 n，，n
1定义3 设是整数，当时式(1)成立，则称是同余方程的解。xxx,x，，000凡对于模同余的解，被视为同一个解。同余方程(1)的解数是指它的关于模mm
互不同余的所有解的个数，也即在模的一个完全剩余系中的解的个数。 m
由定义3，同余方程(1)的解数不超过 m。
定理12 下面的结论成立:
bx(?) 设是整系数多项式，则同余方程(1)与 ，，
fxbxbxm，, mod等价; ，，，，，，，，
bm, 1,(?) 设是整数，，则同余方程(1)与 b，，
bfxm,0 mod ，，，，等价;
fxgxhxgxhx ,，与(?) 设是素数，都是整系数多项式，又m，，，，，，，，，，设是同余方程(1)的解，则必是同余方程 xx00
gxmhxm,,0 mod0 mod或 ，，，，，，，，
的解。
- 3 -
2.一次同余方程的解法 定理13 同余方程 axbm,mod，，
(?) 若有唯一解 am,1,，，
|(?) 若amd,,， 没有解 db,，，
(?) 若amd,,，db 有个解 d，，
a, m 1,2.1 的情况 ，，
2.1.1观察法
0,1,21m,的完全剩余系中考虑同余式的解，此方法适用在当模较小在模mm
时或方程具有特殊形式的一次同余方程里
21mod3x,x,2mod3例1:的解为 ，，，，2.1.2欧拉定理算法
,m,,mm,1，，，，，，am,1modabam,modaxbm,mod由欧拉定理有，而可得 ，，，，，，
,m,1，，,m既得:为所求的解。此解法适合较小或较易求解 mxba,，，
89mod11x,例2:解 ，，
941094488923696262658mod11x,,,,,,,,,,,1110,解， ，，，，，，，，，，
2.1.3化为不定方程的解法
axbmy,,axbmy,,axbm,modxy,有解存在整数使得。即不定方程有,，，
解。此解法对模的要求较低。 m
89mod11x,例3:解 ，，
8119,uv,,解:原方程对应的不定方程为 其通解为(对任意的整数) t
utvt,，,，81158，
- 4 -
所以x,8mod11 ，，
2.1.4减小模数的解法
对于 axbm，,0mod10,mod2,,,，,,,abmaxbmymyba，，，，，，，，
mkacbpad,，,，,此时，然后去掉中的倍数不断将模,,cydamodam,a，，
myb,0变小此时若2有解，则为的解。 1yx,，，，，00a
经过几次转换后一般可以用观察法求解，在递推出原方程的解。此方法适合模数
较大的同余方程。
:解同余式32520mod161x, 例4，，
解:原同余式即是:320mod161x,，解同余式:16120mod3,21mod3xy,,, ，，，，，，
202161，，y,2mod3得:，所以原同余式的解是: x,,114mod161，，，，3
2.1.5欧几里得算法
可借用辗转相除法求整数的最大公因数的方法，结合同余式的性质，可转化为一
xrm,mod个形如的同解方程。当利用恒等变形将变小，直至将的ma,,ax，，
系数化为1.
aa, b m , , b 1,,1若, 且模数较大时, 可用取余的办法, 将变小, 然后a，，?
求出解。
12187 mod257x,例5: 解同余式. ，，
121, 257 1,解: ?, ?原同余式有1 个解。 ，，
?257 1212 15,，，,
1212872 mod257，,，x而 , ，，
？,, 15174 mod257x, ，，
？,,15174 mod257x 。 ，，
257 1517 2,，，?,
1517 17174 2958 131 mod257 , ，,,，,,,,x而 ，，
2131 mod257x,?, ，，
- 5 -
2131 257 388 mod257x,，,, ，，
为原同余式的解。 即x,194 mod257，，
a, ba, b2若a, b 1,, 且中至少有一个数大于m , 可根据同余知识, 将化，，?
小, 再用1方法去解。 ?
例6: 解5887 mod47x, ，，
解: ?5811 mod47 , 8740 mod47,,, ，，，，
1140(mod47)x,?原同余式化为: ?, 471143,，，
而11444016019 mod47，,，,,x, ，，?,,319 mod47x。 ，，
又 , 47 3152, 31515192853(mod47),，，,，,，,,而x23 mod47x,?。 ，，
x,25 mod47?为原同余式的解。 ，，
2.1.6分式法
bbaxbm,mod先把写成的形式(这里是一种形式的写法)然后xm,mod，，，，aa用与互素的数陆续的乘又端的分子和分母，目的在于把分母的绝对值变小，直m
到变成1为止。此方法使用模不太大如三位数或三位数以内的。
3725mod107x,例7:解同余是 ，，
25253757510732，,, 解x,,,,,,,,899mod107，，373731111111074，,
2.1.7威尔逊定理解法 axbmamamm,,,,mod,,1,0,为素数，由威尔逊定理有:，，，，
m,1!，，axbmmxbm,,,,,,1!modmod此方法适用模为素数且模不能，，，，，，a太大。
89mod11x,例8:解 ，，
- 6 -
10!解 8910!mod119mod11xx,,,,,，，，，8
2.2 amd,1,,的情况 ，，
damd,1,,， 有个解 db，，
法 2.2.1化为am,1,，，
对于amd,1,,先用去除同余式，在按am,1,的情况去解。 d，，，，
例9:求288mod44x,的解 ，，
解28,444, 原方程有4个解。用4去除同余式得: ？，，
72mod11,x,11714,42mod11,，，？,,x而 ，，，，
21mod11x,,，x,5mod11原同余式的解为x,5,16,27,38mod44 ，，，，，，2.2.2消去的系数解同余式 x
1逐次消去的系数 xa?
12961125mod1935x,例10: 解同余式。 ，，
1296,19359,91125,解:因为，同余式有个解。 9，，
144125mod215x,14412590mod215x,,,原同余式可化简为，， ，，，，144与,90的公因数18与215互质，可消去公因数18，同余式进一步化简为:
85210mod215x,,,22。8与210的公因数与215互质，可消去公因数，同，，
4105320mod215x,,x,8mod2154余式可化简为:，320是的倍数故:。，，，，
xtt,，,80215mod1935,0,1,2,3,,89原同余式的个解为:。 ，，，，
2利用辗转相除法消去 的系数 xa?
对于系数较大、较复杂的同余式, 可以采取辗转相除法消去 的系数。 x
1215560mod2755.x,例11:解同余式 ，，
1215,27555,5560,,5解:因为同余式有个解。 ，，
- 7 -
551243265,,，，24365348,,，，化简:243112mod551x,，用辗转相除法 ，，
6548117,,，，4817214,171413,,，，,，，14342,3211,，，,，，，将上述过程
反演得到:13231434531451714114517614,,,,,，,，,,，,，,,，,，, ，，，，
5176481721717648176548164817652348，,，,，,，,，,，,，,，,，,，,，，，，
17652324365323243866523243865512432，,，,，,,，，，,,，，，,，, ，，，，
86551195243.1=86551-1952431952431mod551，,，，，,，,由，可得到所以: ，，
所以,，,,，,195243195112200mod551x因为,，,1952431mod551, ，，，，x,200mod551,同余式的5个解为:xtt,，,200551mod2755,0,1,2,3,4. ，，，，，，3.同余方程组的解法
3.1简单同余方程组的解法
对于同余方程组
x,a(modm),11,x,a(modm),22 (1) ,？？,,x,a(modm)kk,
当k, 2时的简单解法。
例12. 解同余方程组
3x，5y,1(mod7),。 (2) ,2x,3y,2(mod7),
解 : 将(2)的前一式乘以2后一式乘以3再相减得到
194 mod 7y,,，，，
54 mod 7y,,， ，，
y,2 mod 7。，，
再代入(2)的前一式得到
3101 mod 7x，,，，，
x,4 mod 7。，，
- 8 -
即同余方程组(2)的解是xy,,42 mod 7，。，， 3.2 孙子定理
定理14(孙子定理) 设是正整数， mmm,,,12k
mmijkij, 11,,,,,，，。 ，，ij
记
m， ，， M,1,,ikmmmm,i12kmi
'则存在整数，使得 Mik()1,,i
'MMm,1 mod， ，，iii
并且
k
,xam,MMmod (3) ，，,0iiii,1
是同余方程组(1)对模的唯一解，即若有使方程组(1)成立，则 mx
xxm,mod。 ，，0定理15 同余方程组(1)有解的充要条件是
aammijn,,,mod ,1,，。，，，，ijij
fx定理16 设，其中是两两互素的正整数，是整系mmmm,mmm,,,，，12k12k
T数多项式，以与分别表示同余方程 Tik()1,,i
fxm,0 mod ，，，，与
fxm,0 mod ，，，，i的解的个数，则TTTT,？。 12k
357，，123，，。例13. 求整数，它被除的余数分别是 n
解:是同余方程组 n
nnn,,,1 mod 32 mod 53 mod 7，， ，，，，，，
- 9 -
的解。根据孙子定理，取
mmmm,,,,，，, 3 5 7 357 105，，，，123
MMM,,, 35 21 15，，，123
''' MMM,,,,1 1 1，，，123
则
n,，，,，，，，，，,135(1)2211315152 mod 105， ，，因此所求的整数 ntt,，, 52 105，。Z
例14. 解同余方程
256490 mod 60xx，，,。 (4) ，，
解: 因为，所以，由定理16可知，同余方程(4)等价于 60 345,，，
同余方程组
256490 mod 3 xx，，, (5) ，，
256490 mod 4xx，，, (6) ，，
256490 mod 5xx，，,。 (7) ，，分别解同余方程(5)，(6)，(7)得到解
11，，，，xx,,,11 mod 3，， ，，12
22，，，，xx,,,11 mod 4，， ，，12
3，，x,1 mod 5， ，，1
同余方程(4)的解可转化为下面的方程: x
xaxaxa,,,mod 3mod 4mod 5，，， ，，，，，，123
,1其中或，或。 a, 1,,1 1，aa, 1123
利用孙子定理，取
mmmm,,,, 3 4 5 60，，，，123
MMM,,, 20 15 12，，，123
'''MMM,,,, 21 3，，，123
则
xaaa,,，401536mod 60。 ，，123
- 10 -
将所有可能的取值代入上式，得到方程(4)的全部解是 aaa，，123
， x,，,，，，,4011513611 mod 60，，1
x,，,,，，，,,40(1)15136119 mod 60， ，，2
x,，,，,，，,40115(1)36131 mod 60， ，，3
x,，,,，,，，,40(1)15(1)36111 mod 60。 ，，4
4.高次同余方程的的解法
4.1素数模的同余方程
n|设fxaxaxa ,，，，是整系数多项式，是素数， 。 ppa,，，10nn
定理17 设若同余方程 kn,，
nfxaxaxap 0 mod,，，，, (1) ，，，，10n
有个不同的解则对于任意的整数有 kxxx,,,，x，12k
fxxxxxxxfxp,,,,() ()() mod， ，，，，，，12kk
nk,xfx其中是一个次数为nk,的整系数多项式，并且它的项的系数是 a。，，kn
定理18 同余方程(1)的解数 ,n。
p,1定理19 同余方程(1)与一个次数不超过的质数模同余式等价。
np,定理20 设，则同余方程
nn,1fxxaxaxap 0 mod,，，，，, ，，，，n,110
qxrxrx有个解的充要条件是存在整数多项式和，的次数使得 ,n，n，，，，，，
pxxfxqxprx,,，，。 ，，，，，，
paap,modFermat定理21 (定理)若p是素数，则 ，，
- 11 -
3例15. 判定同余方程2310 mod 7xx，，,是否有三个解。 ，，
3: 因为，所以，原方程与 解241 mod 7，,424340 mod 7，，，，,xx，，，，
3即xx,,,230 mod 7等价。由于 ，，
73422 xxxxxxxxx,,,,，，，，，， (23)(234)121612，
所以，由定理20和定理18可知，原方程的解数小于。 3
例16. 解同余方程
1410346180 mod 5xxx，，,,。 ，，
5解: 由定理，xx,mod 5， Fermat，，
14105952346183777618xxxxxxxxxx，，,,,，，，，,又因为 ，，，，
276180mod5xx，,,因此，由定理19原同余方程等价于: ，，
2230 mod 5xx，,,即 。 (2) ，，
x,,,012 mod 5，，将分别代入方程(2)进行验证，可知这个同余方程解是，，
x,1 mod 5。 ，，
,4.2模p的同余方程
a求解模的同余方程可以转化为对模的同余方程的求解。 pm
若是同余方程 x0
,fxp,0 (mod) (1) ，，
的解，则它必是方程
,,1fxp,0 (mod) (2) ，，
的解，因此，必有与相应的方程(2)的某个解，使 xx01
,,,,11xxpxxpt,,，(mod)，， 01010
此处，是某个适当的整数。 t0
- 12 -
n定理22设是素数，是整数，fxaxaxa ,，，，是整系数多项p,,2，，10n
'是同余方程(2)的一个解。以表示的导函数。 式，又设fxfxx，，，，1
'(?) 若fxp,0 mod，则存在整数，使得 t，，，，1
,,1 (3) xxpt,，1
是同余方程(1)的解。
'tp,, 01, 2,,1，(?) 若fxp,0 mod并且fxp,0 mod，则对于，，，，，，，，，11
x都式(3)中的是方程(1)的解。
由定理，可以把解同余方程(1)，转化为解同余方程
fxp,0 mod。 (4) ，，，，
2fxp,0 mod由方程(4)的解，利用定理，可以求出方程的解，再利用定理，，，，，
3fxp,0 mod又可以求出方程的解，？？，直到求出方程(1)的解。 ，，，，
推论1 使用定理的记号，
'xap,modfap,0 mod(?) 若是同余方程(4)的解，并且，则存在，，，，，，
,xxap，,mod，使得xxp,(mod)是同余方程(1)的解。 ，，,,,
'fxp,0 mod(?) 若与同余方程(4)没有公共解，则对于任意的整数a,1，同，，，，1
余方程(1)与(4)的解数相同。
例17. 解同余方程
3xx，,,3140 mod 45。 ，，
解: 根据定理16 原同余方程等价于同余方程组
3xx，,,3140 mod 9， (5) ，，
3xx，,,3140 mod 5。 (6) ，，
3xx，,,3140 mod 3x,2 mod 3先解同余方程(5)。同余方程的解是。 ，，，，
xt,， 23令并代入方程(5)，得到
3(23)3(23)140 mod 9，，，,,tt， (7) ，，
由定理22(?)这是一个对于任何整数t都成立的同余式，所以，方程(7)的解是
- 13 -
t,012 mod 3，，，于是方程(5)的解是 ，，
。 (8) x,258 mod 9，，，，
再解同余方程(6)。用去验证，得到(6)的解是 x, 01234，，，，
。 x,12 mod 5，，，
因此，原同余方程的解是下面六个同余方程组的解:
xaa,,mod 9 258，，，，，，11
xaa,,mod 5 12.，，，，22
利用孙子定理解这六个方程组，记
''， mmmMMMM,,,,,,,, 9 5 45 5 9 21，，，，，，121212
则
xaa,,109mod 45。 ，，12
将 aa和的不同取值代入，得到所求的解是12
x,，,，,1029111 mod 45， ，，1
x,，,，,102922 mod 45， ，，2
x,，,，,1059141 mod 45， ，，3
x,，,，,1059232 mod 45， ，，4
x,，,，,1089126 mod 45， ，，5
x,，,，,1089217 mod 45。 ，，6
例18. 解同余方程
23213340 mod 5xx，,,。 (9) ，，
解: 同余方程
2213340 mod 5xx，,, (10) ，，
x,,12 mod 5，有两个解。 ，，
1?令
xt,,，15， (11)
代入同余方程
- 14 -
22213340 mod 5x，,,， (12) ，，得到
2， 2(15)13(15)340 mod 25,，，,，,,tt，，
， ,，,45450 mod 25t，，
。 (13) 99 mod 51 mod 5tt,,，，，，，于是，将式(11)与式(13)联合，得到方程(12)的解
。 (14) xttt,,，，,，,15(15) 425，Z111将式(14)中的代入同余方程(9)，得到 x
232(425)13(425)340 mod 5，，，,,tt， ，，11
3507250 mod 5，,t， ，，1
2290 mod 5，,t， ，，1
t,2 mod 5。 ，，1
将上式与(14)联合，得到同余方程(9)的一个解
3xtt,，,，，, 425 425(25)54 mod 5。 ，，12
2x,2 mod 5? 从同余方程(10)的另一个解出发利用上述方法，可以求出，，
3x,2mod5同余方程(9)的另一个解为。 ，，
例19. 解同余方程
2kxk,,1 mod 2，N。 (15) ，，
x,1 mod 2解: 若k, 1，则方程(15)的解是。 ，，
x,,11 mod 4，若k, 2，则方程(15)的解是。 ，，
k,3若，则同余方程(15)，即
2kxxx,,，,,1 (1)(1)0 mod 2， ，，
xy,， 2 1的解必是奇数，设，则同余方程(1)成为
k(22)20 mod 2yy，,， ，，
- 15 -
k,2。 (16) yy(1)0 (mod 2)，,
k,2同余方程(16)的解是，即 yy,,,01 (mod 2)，12
kk,,22， yuyvuv,,,，, 212,，，Z12
所以，方程(15)的解是
kk,,11， xuxvuv,，,,, 21 21,，，Z12
即
kkk,,11x,，,,，112112mod 2，，，。 ，，
- 16 -
总结:
本文应用前人的研究成果，对同余方程的常用解法进行了系统的归纳总结，并对其解法进行了进一步的研究优化。其主要对一次同余方程的解法进行了详细的介绍，其次对用孙子定理来解同余方程组做了初步的总结，最后叙述了素数模
,及模的同余方程的解法，但本文只是讲了一些同余方程的常见解法，希望读p
者在这方面有更好更多的见解。
- 17 -
参考文献
,,, 柯召，孙琦.数论讲义上册[M]. 高等教育出版社,北京,2001年
严士健.初等数论第三版[M].高等教育出版社,北京,2003年 ,,, 闵嗣鹤,
,,, 潘乘洞、潘乘彪.初等数论[M].北京大学出版社第二版,北京，2003年 ,,, 杜德利.基础数论[M].周仲良,译.上海科技出版社,上海1982年
谈数论中的同余及其应用[J].衡水师专学报,2002年 ,,, 刘合义.
,,, 原新生.一次同余方程的几种解法[J].牡丹江教育学院学报,2009年
- 18 -
致谢:
时光匆匆，如白驹过隙。在毕业论文定稿之际，四年的大学本科生活也即将画上句号。遥想初入大学之时，还历历在目，恍如隔日，不免感叹光阴易逝、韶华难追。然而，艰辛而快乐的求学之路，也给我留下了很多难以忘怀的欣慰和幸福。在此，向四年来陪伴我一起走过，给予我帮助和关心的良师益友以及亲人们，致以最为真挚的谢意～
我衷心的感谢我的导师 ，她在我毕业设计的题目选择上给与了非常大的帮助，并且在整个毕业设计过程中一直指导、鼓励着我，使我能够顺利完成毕业设计的工作。
- 19 -
范文三：一次同余方程解法公式化
一次同余方程解法公式化 读写算2011年第33期文学教育研究
一
次同余方程解法公式化
孙粱
(凯里市教育局贵州凯里556000)
【摘要】运用余数方程";c(modm)周期表的自变律和周变性质,对首项余数进行模
运算再转化.简明扼要地推算任意两个
不等的正整数的最大公约数和余数方程的整数解.运算过程紧凑严密,环环相扣,
一气呵成.比较传统的方法,显得更为简明,快速
直接,不拖泥带水,容易记忆,使用方便,结束了一次同余方程不可能用公式一次计
算的历史.
【关键词】余数方程;周期表;自变律;公式化
余数方程"sc(modm)(a,c为整数,ITI为正整数)的解法 有多种,其中以"大衍求一术","欧几里德算法","欧拉定理解 法"着称于世驰名中外,经典永存.本工作用余数周期表…自变 定理推导的"模运算转化法",把余数方程未知数系数转化到归 零还原的子余数组建余数子方程(或子系不定方程)来讨论, 把方程是否有解?有解时解数是多少?如何求出一个绝对整数 解三大问题集中在余数子方程(或子系不定方程)中获得自然解 决,用公式一次性计算绝对最小整数解.不但回避了"大衍求一 术"多步骤,多环节的繁琐计算,而且还有效避免了"欧几里德算 法"反向推导的复杂代入程序;特别避免了"欧拉公式"望而生畏 的高次幂转化的浩大工作量."模运算转化法"集传统解法之众 长,避传统解法之众短,把求解一次同余方程(含二元一次不定 方程)的问题简化到象解普通的一元代数方程那样简单,快捷, 干净利落,真正走向了公式化,条理化的道路.为一次同余方程
和二元一次不定方程的求解,提出了一套全新的解决模式. 1,余数自变定理的推论和证明.
余数方程周期表首项余数模运算再转化的最终结局是余 数的归零还原,本文讨论的子余数就是能够归零还原的子余数. 设首项余数c.模运算再转化的n阶子余数是c自变后可以归 零还原,C只能有两种情况发生,第一种cIc.,即Icl:(a m);第二种c除不尽Co,fCf?(am).下面分别两种情况进 行研究.
定理1(余数自变定理)余数方程";c(modbm)周期表首 项余数c.经过n个自变环节的模运算转化得到归零还原的子 余数cIC.,由c组建的余数子方程是:
cPxECmodIn)(A)
此时,(A)与原方程同时有解或无解,且有解时解数相同. 若Px是(A)的一个整数解(即P=为整数),P.,P…P是 n
c0转化到c的r1个自变环节的n个商,则原方程的整数解可由 下式表出:
x—PIP2…PP(modm)
证明:原方程周期表首项余数经过n个自变环节的模运算 转化过程可用n个模运算递推式表出(因为使用同一个模,把 modm放在递推式末尾一次说明):
a;C0_.+CoPliCl_C1P2?C2_…(C一1P;CfC0 (modm)(N)
因为归零子余数clc.,所以(am)=(C.m)=(C.m)…
(A)有整数解,必有(Cm)Ic,也就是(am)I (Cm)=lcl,如
C,这正是原方程有解的充分必要条件J.因此,原方程也有整 数解,解数都是(am)=(Cm),如果(A)无整数解,必有(Cm) 除不尽c,也就是(am)除不尽c,原方程也无整数解. 又根据周期表白变律…推算:(N)中各自变环节的子余数
在周期表中的项数(即整数解)如下:
C0在l项一Cl在Pl项一c2在PIP2项一…cn在P1P2… P项.
设rl阶子余数C连续自变P次(不受模m限制)可产生指 定余数c,则有余数子方程CPzC(modm)成立,若(Cm)lc, 必有整数解,解数为(Cn1),因为C在P.P…P项,又自变P 次,则指定余数c在周期表中的项数是P.P2…PP,项,即指定 余数C的整数解是:
x;P,P:…PP(moam)证毕
定理2(余数自变定理2)余数方程;c(modm)周期表酋 项余数C.经过n个自变环节的模运算转化得到归零还原的子 余数C除不尽C.,C要转换C.为模,组建的不定子方程是: cM?C0N=C(modC0)(B)
(B)的两个整数解可用余数白变定理1解出.此时,(B)与 原方程同时有解或无解,且有解时解数相同,若M,N是(B)一组 特解,PlP2…P是模运算由c.转化到C的r1个自变环节的n 个商,则原方程的整数解可由下式表出:
xiPlP2…PM?N(modm)
(?号与(B)?号相对应,切记:cCo同号相减,异号相加). 证明:因为c除不尽Co,此时(Cm)?(CCO)?(am)? c此时(am)=(cc0)如果(B)有整数解,必有(CCo)lc_3], 也就是(arl1)Ic,这正是原方程有整数解的充分必要条件,且 (B)和原方程的解数都是(am)=(cC.),如果(B)无整数解, 必有(CC.)除不尽C,也就是(am)除不尽C,因此原方程也无 整数解.
若M,N是(B)的一组特解,则(B)表明:Cn连续自变M次 后的余数为cM,再以c.为标准它变(递增或递减)N欠产生指 定余数c.因为cn在P.P…P项(前证),连续自变M次后应 落在PP……PM项,又以c0为标准它变(递增或递减)N次,
应加上(或减去)c.的变化项l?N=N项.故指定余数c在周 期表中的项数是:PlP2…PM?N项,故原方程的整数解是: X-=PlP2…PM?N(m~tm)
注:(B)是否有解,有解时解数及M,N的整数值可用定理1 重复操作得出.
证毕.
定理1和定理2模运算转化的全过程用自变余数递推式记 写如下;
余数自变定理1aX~-Cod--)
平方程笨
a;&一c;e.一…cP.;c一P1一蠢(整数)
一X兰P'P2…Pxod.1)
余数自变定理2ax~---C(Ildo|) 蓬旱轻
a兰co—c.P,兰兰三c1一eP三三兰c.lco(-odm)一 龉霉
C?e,dt=l~(-od?一X三三三Pp2…P,II?K(1lod 定理t末?
?
181?
矗学教1r研霓2011年第33期读写算
2,自变余数的模运算应用技巧
模运算再转化的解题方法,无须事先判断方程有无整数解 和存解时的解数,也不用考虑用最大公约数去化简方程,也不用 考虑am是否互质,余数方程的全部问题都转化到归零子余数 组合的余数子方程(或不定方程)去解决,整个计算过程紧凑严 密,环环相扣,一气呵成.
例1判断余数方程1406X-=117(rood817)是否有整数解 解:1406g一228;(一228)?4;一95-+(一95)?9z一38
一(一38).22一191—228--.-*Px;?整数,无解(mod817) 例1中,转化得到最大公约数一l9除不尽117,说明余数子 方程无整数解,根据定理l,原方程也无整数解.全部转化工作 到此结束,如果方程P,=7--=整数,说明方程有整数解,则用定 n
理1将方程解直接转化到题目要求的答案.
例2,求2970X;983(mod83)正整数通解.
解2970;一18一(一18)?5一一7一(一7)?12=一1一 P.x;13----~X;5.12.13;33+83K(K>0)
(mod83)检验适合.解毕
对于模m<10'以内的中小模数方程,模运算再转化的方 法,显得尤为简捷快速.'
例3,求907X---2107(mod731)的绝对最小整数解. 解:907;l76一l76?4i一27一(一27)?27=2—23?66; 1---,,P,_2107
;一86-*X4.27.366(一86);一258(mod731) 检验适合.
小模数方程也同样遵循模运算自变法则转化,只不过变化 环节减少.
例4求15Xs11(mod7)的整数通解
解:15;l—P=竿4一x;1?4一一3+7K(K为整数) (mod"/)检验适合,解毕.
例5,求228X~23(mod47绝对值最小整数解)
,
解:228兰一7一(一7)一72_+(一2)'23三1P三竿 i23—x;7?23?23;7(rood47) 检验适合
当归零子余数Cn#?1时,要用最大公约数简换模后,才能 获得绝对值最小整数解.
例6,求4016X---136(mod2822)绝对最小整数解及解数. 解:4016=l224_1224?2i一374一(一374)?7;204 04.143411224_+Px;4一
x一2?7?14-4-~784(rood2822) 换模
一x-=----784------37+83K(mod:83)(k:o,1,2--.33)
通过模运转化知,绝对最小整数解是37,解数是34个,它们 是:X=37+83K(K=0…12…33)解毕.
模运算再转化的方法同样适用于大模数方程的求解,但用 ?
182?
公式计算苦干个商的连乘积时,因商值过大,普通计算器不能一 次计算绝对值最小整数解,要分成若干次模运算转化,才得到绝 对值最小整数解.
例7,求225600X~35(mod9253)绝对值最小整数解. 解:225600~-3528--*3528?3—1331----1331?7;64 —
,64.145i27—7.343i8—逗.1157g3
?
3084------一1---*Px~普;-35
一X;3-7?145?343?1157?3084?(一35)s1891 (mod9253)
检验适合
注:大模数方程可以采用模运算转化二次求解的方法简化 计算工作量.(本文略)
当模运算转化到归零子余数C除不尽C.时,C要选择co 为模,组合不定子方程,用定理1继续对C转化,求出不定方程 的一组特解,用定理2计算原方程的整数解.
例8求9253--=35(mod225600)绝对最小整数解
解:9253?24;一3528一(一3528)?64;一192除不尽9253 (rood225600)
建子方程:
(一192)M+9253N=35(mod9253)用定理1求M,N一(一 192)?48=37—37?250=一3—}(一3)?3084;l P=35一M=48?250?3084?35;一1205(mod9253)一N =一25
根据定理2:X=24?64?(一1205)+(一25)46105 (mod225600)
检验完毕
例8是古历会积中一道着名题目,在《吴文俊论数学机械 化》一书中提及,在求解这道题时,美国史丹福大学着名教学及 电脑科学家在其名着中引述的欧拉(Euier)函数法,即使使用一 台现代化电脑也很难快速完成任务,因为要涉及
9253的计算.本文运用模运算转化法,却能用普通计 算器在15分钟左右轻松快速地获取方程最佳结果,余数自变定 理解题的简捷程度可见一斑.
模运算转化法的除法运算比较辗转相除法来说,要方便快 捷得多,算式也简明直接,余数的本质属性(正负,大小,变化质) 表达含义准确,严密,因为模运算直接对自变余数进行转化.省 略了转化过程中不必要的数据,换模变号和多元未知数的假等; 其二是选择了一个变化质为零的不变模数进行转化,能够推导 出公式一次求解,避免了辗转相除法反向推导的复杂代入程序, 是值得总结和推广的好方法.
参考文献
[1]孙梁.余数周期表和辗转相除法[J].凯里学院,2008, (6)125—128.
[2]孙梁.公式化解决一次同余方程和一次不定方程的探索 [J3.科学教育家,2009,(3)1O一12.
[3]潘承洞,潘承彪.简明数论[M],北京大学出版社,1998,52
一
】62.
范文四：一次同余方程组的一种解法
一次同余方程组的一种解法 第22卷第3期
200t年6月
温州师范学院学撤(自然科学版)
JOURN;d~OFWENZHOUTEACHERSODLLEGE(NatSci
Vo【22No3
Jun200l
一
次同余方程组的一种解法
王靖庶
(温州帅范学院第一初等教育学院浙江瑞安325200) 摘要提出一个较孙子定理简易得多的一次同条方程组韵解法 关键词同泉方程组孙子定理递推累加
0075一(03) 中图分类号O156L文献标识码A文章编号10060375(2001)03—介绍同余方程组
fzI(rood
lz!(meal
【r"(rood)
(这里,~I'/2,…,m两两互素)的解法常采用孙子定理(或称中国剩余定理):若?2,令
M—m
m=M.=M_..?=mM,则(L)恰有一整数解.
三MIMIcI+M2M2c2十…+Mn(m.dM)
这里M.,是同余方程M.M1(mod.)的解,i=L,2,…,k 现提出另一种解法:
这里A4,是满足同余方程
MM】口,(reed+1)(3)
的整数解,i=1,2,…,k1,
则(1)的解就是,72a(rood),这里Ms=Im!…m.
本解法的基本思路是:先解(1)中任意两个方程构成的同余方程组,这里不妨就设
为
jI(modlr4)
lzc2(meal7;q2)
由形如(3)的同余方程解得整数M,因为n:?+MM&.+(一n)=c(mc~t"),满足(4)
中的
第二个方程,而:=el+C(roodm)又满足(4)中第一个方程,t,m互素,所以" (modM,)是(4)的解,接着再在(1)中取出一个方程(不妨就取第三个)构成如下同余
方程组
=日2(modM2)…
)
【ic3【modm3)
鞯馨品望躬).男.温州帅范学院第一初等教育学院高缎讲师 )
十
?
一
l
峨
d
m
m
=
令
温螂师范学院(自辅科学版)2001年第22卷
依(2),(3)求解,并类似可验证
.=n2+M2M2(roodM3)
是(5)的解,依次求解同余方程组
仁(moJM,)(moJr,J…)(6)
最后得到的
I(tBoJM')
就是同余方程组(1)的解实际上,ai即为(1)中前i个方程构成的同余方程组的解,i=l,2,一,,这是
一
种递推的解法
因为只是接连求解形如(6)的只含有两个方程的同余方程组,因此,此法理论简明,其依据就是:若
,互素,形~11(4)的同余方程组恰有解:
?(tBoJm1m2)
这里是满足同余方程组(4)的一个整数.(6)本质上亦即(4),因为M与m:1互素是显然的
每次求解(6)时需解的同余方程(3)相当于孙子定理中的同余方程MMI-----1(roodm)且M
较孙子定理中的数值要小(1)的整个求解过程中,需要解的同余方程还少一个,由此可见,其计算要简约
得多还可将本法最后的得解写成类似于孙子定理中最后得解的形式:(这里只是为了比较,实际求解时
即为最后的")
.
27=l十MlM1+M2M2+…+M'lM
现举"韩信点兵"问题(其文字表述见后)为例说明
fz1(5)
J=5(6)
T4(m7)
【z;10(rood11)
依孙子定理,列下表进行计算
表l
M!MM,MJ
46231386
385ll925
330ll320
210l2lcwl
最后得解
I386十1925十1320+2100673I21I1(m0d2310) 用本文提出的方法,也以列表进行计算:
袁2
l
1l
ll
l99
由(2)式,表中每行的M:,M:相乘,加该行的n即为下行的雹,1.表上作业更为简便 76?
(7)
蔫
3蝴王靖庶一改列泉方程蛆的一种解法
由表可得n一19g21ll(rood2310)即为(7)的解
对于投有同余方程知识的读者,如小学生,用本文解法的思路去解同余问题可如下进行:仍以"韩信点
兵"问题为例,有兵一队,若列成五行纵队,则余一人;列成六行纵队,则余五人;列成七行纵队,则余四人;
列成十一行纵队,则余十人,求兵数
第一步固五行纵队余一人,该队兵数或为6,或为1l,或为16,……即由1或1逐次累加5得到累
加的同时用6试除,求得第一个余数为5的数时,累加停止,得到同时满足前两个条件的最小自然数,这里
求得11
第二步为保证前两个条件总能满足,11或l1逐次累加5和6的最小公倍数3O,得到:l1,41,71,
……
累加同时用7试除,求得第一个余数为4时,累加停止,得到同时满足前三个条件的最小自然数这里
仍是11,属特例,无须累加
第三步为保证前三条件总能满足,11或11逐次累加5,6和7的最小公倍数,累加的同时用11试
除,求得第个余数为1O的数即为本题的解这里在第1O次累加试除后得2111 上述累加试除的过程在计算机上是极易实现的.
综上所述,本文提出的解法理论浅显,易懂易学,属于一种递推解法,启动快,计算得值小,易于计算机
编程
以上乞教于各位前辈同仁希冀此解法能得以推广,特别是在给中小学生讲解同余问题时运用
参考文献
【]陈景润初等数论fM]北京科学出版社.197812
2]叫景梅数论简明教程[M]银川:中夏^民版社,1998.8
ASolutionofaSystemofLinearCoresidualEquations wANGJing—sh
LTheFristE&vnemaryEducationCollege,WenzhouTeachers(}Ie
AbstractHereisanewmethodintroducedforsolvingasystemofc(residualequati0nsItonlyn
eed『()
solveasystemcomposedn{twoequationseachtime,andiseKsentlallyarecursivesoluti0n
口mcessFurthe卜
mOTCthemethodcanbeusedprimarilythroughaccumulatingandtria1dividing.
KeywordsG.,residualequationsChine-seremaindertheoremRecursi0nACCUmuIati[】g
范文五：一次同余方程组的简捷解法
第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<2111+30030t><40000, 有t="">
∴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?
转载请注明出处范文大全网 » 同余方程的解法（可编辑）
