初等数论第五章同余方程.docx
《初等数论第五章同余方程.docx》由会员分享，可在线阅读，更多相关《初等数论第五章同余方程.docx（62页珍藏版）》请在冰点文库上搜索。
初等数论第五章同余方程
第五章同余方程
本章主要介绍同余方程的基础知识，并介绍几类特殊的同余方程的解法。
第一节同余方程的基本概念
本节要介绍同余方程的基本概念及一次同余方程。
在本章中，总假定m是正整数。
定义1设f（x）=anxnaixao是整系数多项式，称
f（x）0（modn）
（1）
是关于未知数x的模m的同余方程，简称为模m的同余方程。
若an0（modm，则称为n次同余方程。
定义2设xo是整数，当x=xo时式
（1）成立，则称xo是同余方程
（1）的解。
凡对于模m同余的解，被视为同一个解。
同余方程
（1）的解数是指它的关于模m互不同余的所有解的个数，也即在模m的一个完全剩余系中的解的个数。
由定义2,同余方程
（1）的解数不超过m
定理1下面的结论成立：
（i）设b（x）是整系数多项式，则同余方程
（1）与
f（x）b（x）b（x）（mod
等价；
（ii）设b是整数,（b,m=1，则同余方程⑴与
bf（x）0（modm
等价；
（iii）设m是素数，f（x）=g（x）h（x）,g（x）与h（x）都是整系数
多项式，又设xo是同余方程⑴的解，则xo必是同余方程
g（x）0（modm或h（x）0（modn）
的解。
证明留做习题。
下面，我们来研究一次同余方程的解。
定理2设a,b是整数，a0（modm）。
则同余方程
ax
b（modm
（2）
有解的充要条件是
（a,m
b。
若有解，则恰有
d=（a,m个解。
证明显然，
同余方程
（2）等价于不定方程
ax
my=b，
（3）
因此，第一个结论可由第四章第一节定理1得出。
若同余方程
（2）有解xo，则存在yo，使得xo与yo是方程（3）的解,此时，方程（3）的全部解是
由式⑷所确定的x都满足方程⑵。
记d=（a,m，以及
t=dq
r，qZ，r=0,1,2,
d1，
则
x=xo
qm
m
rXod
mr（modm，ord1。
d
容易验证，当
r=
0,1,2,
d1
时,
相应的解
m
2m
（d1）m
xo,
xo，xo
xo
d
d
d
对于模m是两两不同余的，所以同余方程
（2）恰有d个解。
证毕。
在定理的证明中，同时给出了解方程
（2）的方法，但是，对于具体
xo
yo
t
（a,m）
（a,m）
ym则
的方程
（2），常常可采用不同的方法去解。
例1设（a,m=1，又设存在整数y,使得ab
xb_ym（modm
a
是方程
（2）的解。
解直接验算，有
axbymb（modn）。
注：
例1说明，求方程
（2）的解可以转化为求方程
my
b（moda）
（5）
m的同余方程转化
的解，这有两个便利之处：
第一，将一个对于大模
为一个对于小模a的同余方程，因此有可能通过对模a的完全剩余系
进行逐个验证，以求出方程（5）和
（2）的解；第二，设mr（moda），r例2解同余方程
325x20（mod161）（6）
解同余方程⑹即是
3x20（mod161）。
解同余方程
161y20（mod3），
2y1（mod3），
得到y2（mod3），因此方程⑹的解是
x20_=114（mod161）。
3
例3设a>0，且（a,m=1，a1是m对模a的最小非负剩余，则同余方程
a1xb[m]（modn）（7）
a
等价于同余方程
（2）。
解设x是⑵的解，则由m=a[m]ai得到
a
mmm
aix（ma[]）xax[]b[]（modn）,
aaa
即x是同余方程（7）的解。
但是由假设条件可知同余方程
（2）与（7）都有
且只有一个解。
所以这两个同余方程等价。
注：
用本例的方法，可以将同余方程
（2）转化成未知数的系数更小
一些的同余方程，从而易于求解。
例4解同余方程6x7（mod23）。
解由例3，依次得到
6x7（mod23）
5x
73
2（mod23）
3x
2
4
8（mod23）
2x
8（
7）
10（mod23）
x
5（mod23）。
例5设（a,m=1，并且有整数>0使得
a1（modm，
则同余方程⑵的解是
1
xba（modm。
解直接验证即可。
注：
由例5及Euler定理可知，若（a,m=1，则
ba
（modm
总是同余方程
（2）的解。
例6解同余方程
32
81x24x5x230（mod7）。
解原同余方程即是
3x33x22x20（mod7）。
用x=0,1,2,3逐个代入验证，得到它的解是
Xi1，X22，X32（mod7）。
注：
本例使用的是最基本的解同余方程的方法，一般说来，它的计算量太大，不实用。
例7解同余方程组
3x5y1（mod7）
。
（8）
2x3y2（mod7）
解将（8）的前一式乘以
2后一式乘以3再相减得到
19y4（mod7），
5y4（mod7），
y2（mod7）。
再代入（8）的前一式得到
x4（mod7）。
即同余方程组（8）的解是x
4，y2（mod7）。
例8设ai,a2是整数，m,m是正整数，证明：
同余方程组
xai（modmi）
xa2（modm2）
（9）
有解的充要条件是
ai
a2（mod（m,m））。
（io）
若有解，则对模[m,m]是唯一的，即若xi与X2都是同余方程组（9）的解，则
XiX2（mod[m,m]）。
（11）
解必要性是显然的。
下面证明充分性。
若式（10）成立，由定理2，同余方程
myaia2（modm）
有解yyo（modm），记xo=a2myo，贝U
xoaa（modm）
并且
xo=a2myoa2aia2ai（modm）,
因此Xo是同余方程组的解。
若Xi与X2都是方程组（9）的解，则
由同余的基本性质，得到式（ii）。
1.证明定理1。
2.解同余方程：
（i）31x5（mod17）;
（ii）3215x160（mod235）。
3.解同余方程组：
3x5y38（mod47）
xy10（mod47）
4.设p是素数，0xb
（1）a1（p1）（p2）（pa1）（mod
a!
是同余方程axb（modp）的解。
5.
b（modn）有
证明：
同余方程ax182X2anxn
解的充要条件是
（a1,a2,,an,m=db。
若有解，则恰有dm1个解，modm
第二节孙子定理
本节要讨论同余方程组
xa1（modm1）
xa2（modm2）
（1）
F面考察一般
o
xak（modmk）
在第一节的例题中，我们已讨论了k=2的情形。
情形。
定理1（孙子定理）设m,m,,m是正整数，
（m，m）=1，1i,jk，ij。
记
m=mmm,Ml=—，1ik，
mi
则存在整数M（1ik），使得
MMI1（modm），
MIMI0（modm），1jk，ij，
并且
k
XoaiMiMi（modn）
i1
是同余方程组
（1）对模m的唯一解，即若有x使方程组
（1）成立，则
xo（modn）。
证明由式⑵，有（M,mi）=1，因此利用辗转相除法可以求出M与yi,使得
MMyim=1，
即M满足式⑶和式⑷。
由式⑶与式⑷，对于1ik，有
xoaMMa（modm），1ik。
若x也使式⑴成立，则
xxo（modm），1ik，
因此
xxo（mod[m,m,,m]）。
但是，由式
（2）可知[m,m,,m]=m这就证明了式（6）。
证毕。
定理2在定理1的条件下，若式
（1）中的a,a2,,ak分别通过模m,m,,m的完全剩余系，则式（5）中的xo通过模mmm的
完全剩余系。
证明这是第二章第二节习题6的特例。
证毕。
定理3同余方程组
（1）有解的充要条件是
aia（mod（m,m）），1i,jn。
（7）
证明必要性是显然的。
下面证明充分性。
当n=2时，由第一节例8可知充分性成立。
假设充分性当n=k时成立。
假设式⑺当n=k1时成立。
我们来考虑同余方程组
xai（modm）,1
ik1o
由第-
节例8,存在bk,使得x
bk（mod[m,nu+1]）满足同余
方程组
xak（modm）,x
ak+1（modm+1）。
在同余方程组
xa1（modmJ
xaki（modmk1）
xb（mod[mk,mki]）
中，由式⑺有
aa（mod（m,m）），1i,jk1，
因此，若能证明
aibk（mod（m,[m,m+1]）），1则由归纳假设就可以证明充分性。
由bk的定义，有
akbk（modm），ak+1
而且，由于假设式（7）当n=k
k1有
ik1o（8）
bk（modm+1）（9）
1时成立，所以，对于1
ak+1（mod（m,m+1））,
由此及式（9）得到，对于1
k1，有
aak（mod（m,m）），ai
因此
abk（mod[（m,m）,（m,m+i）]）。
由上式及第一章第六节例2,就得到式（8）。
证毕。
定理4设m=mmm，其中m,m,,m是两两互素的正整
数，f（x）是整系数多项式，以T与Ti（1i
k）分别表示冋余方
程
f（x）
0（mod
m
（10）
与
f（x）
0（mod
m）
（11）
的解的个数，贝U
T=T1T2…
'Tk。
证明
由第「
章第一节疋理5可知，冋余方程
（10）等价于同余方
程组
f（x）
0（mod
m）,1
ik
0
（12）
对于每i
（1
ik）,
设同余方程
（11）的全部解是
xX：
"
x2二用）
（modmi）,
（13）
则同余方程组（12）等价于下面的T1T2…Tk个方程组:
xxj（modm1）
⑵
xX：
（modm2）
八,（14）
xxjk）（modmk）
Jk
其中x（i）通过式（13）中的数值，即通过同余方程（11）的全部解。
由孙子定理，对于选定的每一组{x
（1）,x
（2）,,x（：
）}，同余方程组（14）对模m有唯一解，而且，由定理2,当每个x（i）通过（13）式中的值时，所得到的T1T2…Tk个同余方程组（14）的解对于模m都是两两不同余的。
证毕。
由定理4及算术基本定理，解一般模的同余方程可以转化为解模为素数幕的同余方程。
例1求整数n,它被3,5,7除的余数分别是1,2,3。
解n是同余方程组
n1（mod3）,n2（mod5）,n3（mod7）
的解。
在孙子定理中，取
m=3,m=5,m=7,m=357=105,
M=35,M=21,M=15,
M=1,M=1,M=1,
则
n135
（1）2211315152（mod105）
因此所求的整数n=52+105t,t乙
例2解同余方程
5x2
6x
49
0（mod60）。
（15）
解
因为60=3
45,所以，同余方程（15）等价于同余方程组
5x2
6x
49
0（mod3）
（16）
5x2
6x
49
0（mod4）
（17）
5x2
6x
49
0（mod5）。
（18）
分别解同余方程
（16），
（17）
，（18）得到解
X1⑴
1，
（1）
X2（）1（mod3）
X1⑵
1，
X2⑵1（mod4）
X1⑶
1（mod5），
这样，同余方程
（15）的解x
可由下面的方程组决定:
x
a（mod3）
，x
a2（mod4），x
a3（mod5），
其中a1=
:
1或
1，a：
>=1
或1，aa=1。
利用孙子定理，取
m=3
，m
=4，m=5，m=60
M:
=20
，M=15，M=12，
M=
2，
M=1，M=3
则
40a115a?
36as（mod60）。
X1
40
1
15
1
36
1
1（mod60），
X2
40
（
1）
15
1
361
19（mod60），
X3
40
1
15
（
1）
36
131（mod60），
X4
40
（
1）
15
（1）
36
111（mod60）。
习题二
x
b|（mod5）
1.解同余方程组：
x
b2（mod6）
x
b3（mod7）
x
b4（mod11）。
x
8（mod15）
2.解同余方程组：
x
5（mod8）
x
13（mod25）。
3.有一队士兵，若三人一组，则余1人；若五人一组，则缺2
人；若十一人一组，则余3人。
已知这队士兵不超过170人，问这队
士兵有几人
4.求一个最小的自然数n使得它的1是一个平方数，它的1是
23
一个立方数，它的1是一个5次方数。
5
5.证明：
对于任意给定的n个不同的素数pi,P2,…,pn,必存
在连续n个整数，使得它们中的第k个数能被Pk整除。
6.解同余方程：
3x211x200（mod105）。
第三节模P的同余方程
在第二节中，我们已经看到，求解模m的同余方程可以转化为对
模p的同余方程的求解。
本节要对模p的同余方程做进一步讨论。
容易看出，若Xo是同余方程
f（x）0（modp）
（1）
的解，则它必是方程
1
f（x）0（modp）
（2）
的解，因此，必有与Xo相应的方程
（2）的某个解X1，使
11丄
X。
X1（modp），X。
=X1pt°,
此处，t0是某个适当的整数。
这提示我们：
可以从方程
（2）的解中去求方程
（1）的解。
于是，现
在的问题是，对于方程
（2）的每个解X1,是否必有方程
（1）的解X。
与之对应若有，如何去确定它
定理设p是素数，2是整数，f（x）=anxna1X
f（x）的导函数。
（i）若f（Xi）0（modp），则存在整数t，使得
1
x=Xipt（3）
是同余方程⑴的解。
（ii）若f（xi）0（modp），并且f（xi）0（modp）,
则对于t
证明
=0,i,2,,pi，式⑶中的x都是方程（i）的解。
我们来说明，如何确定式
（3）中的t,使xi
p
it满足
同余方程
（i），即要使
an（Xi+p
it）n+ani（xi+pit）ni+
+ai（xi+p
it）+ao
0（modp）,
（4）
即
f（xi）pitf（xi）0（modp），
tf（xi）f（xii）（modp）。
（5）
p
下面考虑两种情形。
（i）若f（x）0（modp），则关于t的同余方程⑸有唯一解
tto（modp），即t=10pk（kZ）,于是
i
xxipto（modp）
是同余方程⑴的解。
（i）若f（xi）0（modp），并且f（xi）0（modp）,
则式（5）对于任意的整数t成立，即同余方程（5）有p个解
ti（modp）,0ip1。
于是xxip1i（modp）,0ip1,都是同余方
程
（1）的解。
证毕。
在定理中，没有对f（X1）0（modp）并且f（xj0（modp）
的情形进行讨论。
事实上，此时，同余方程（5）无解。
即，我们无法从
同余方程⑵的解X1出发去求得同余方程
（1）的解。
由定理，可以把解同余方程
（1），转化为解同余方程
f（x）0（modp）。
（6）
2事实上，由方程（6）的解，利用定理，可以求出方程f（x）0（modp）
的解，再利用定理，又可以求出方程f（x）0（modp3）的解，，
直到求出方程
（1）的解。
推论使用定理的记号，
（i）若xa（modp）是同余方程⑹的解，并且f（a）0（modp），则存在x,xa（modp），使得xx（modp）是同余方程
（1）的解。
（ii）若f（x）0（modp）与同余方程⑹没有公共解，则对
于任意的整数1，同余方程
（1）与⑹的解数相同。
证明留做习题。
例1解同余方程
解原同余方程等价于同余方程组
3
x
3x140（mod9），
（7）
3
x
3x140（mod5）。
（8）
先解同余方程（7）。
容易验证，同余方程x33x140（mod
3）的解是
x2（mod3）。
令x
=2
3t并代入方程⑺，得到
（2
3t）3
3（23t）140（mod9），
（9）
容易看出，
这是
•个对于任何整数t都成立的同余式，
所以，方程（9）
的解是t
0，
1，2（mod3），于是方程（7）的解是
x2，5，8（mod9）。
（10）
再解同余方程（8）。
用x=0,1,2,3,4去验证，得到（8）的解是
x1，2（mod5）。
因此，原同余方程的解是下面六个同余方程组的解：
xai（mod9），ai=2，5，8，
xa2（mod5），a2=1，2。
利用孙子定理解这六个方程组，记
m=9，m=5，m=45，M=5，M=9，M=2，M=1，
则
2x213x340（mod5）
（12）
将ai和a2的不同取值代入，得到所求的解是
X1
10
2
9
1
11（mod45），
X2
10
2
9
2
2（mod45）
X3
10
5
9
1
41（mod45）
X4
10
5
9
2
32（mod45）
X5
10
8
9
1
26（mod45）
X6
10
8
9
2
17（mod45）
。
例2解同余方程
2
2x13x
34
0（mod5
3
）。
（11）
解容易验证，同余方程
有两个解x1，2（mod5）。
令
x=
15t，
（13）
代入同余方程
2x213
2
340（mod5），
（14）
得到
2
2（15t）
13（15t）34
0（mod25），
于是，将式（15）与式（13）联合，得到方程（14）的解
x=15（15t"=425t1,t1Z。
（16）
将式（16）中的x代入同余方程（11），得到
2（425td213（42511）340（mod53）,
3
50725110（mod5）,
229110（mod5）,
112（mod5）。
将上式与（16）联合，得到同余方程（11）的一个解
x=42511=425（2512）54（mod5）。
（ii）从同余方程（12）的另一个解x2（mod5）出发利用上述方法，可以求出同余方程（11）的另一个解。
（略，请读者补足）。
例3解同余方程
2k.
x1（mod2）,kNo（17）
解若k=1，则方程（17）的解是x1（mod2）。
若k=2，则方程（17）的解是x1,1（mod4）。
若k3，则同余方程（17），即
2k
x1=（x1）（x1）0（mod2）,
的解必是奇数，设x=2y+1,则同余方程
（1）成为
k
y（yi）
o（mod2
k）。
（i8）
同余方程（18）的解是yi
o,y2
i（mod2'
k2）,即
k2
yi=2u,
y2=i
2v,u,
vZ,
所以，方程（i7）的解是
Xi=2kiui
-k
X2=2
ivi,
u,vZ,
即
k
i
ki
k
Xi,i2
i,
i2
（mod2）
2
例4解同余方程X
2（mod7
3
）。
解设X是这个冋余方程的解，则它可以表示成
i2,
X:
2
=Xo7Xi7X2,oXi6,o
代入原方程,
得到
（
Xo7Xi7協2
2（mod73）,
（i9）
因此
2
2
（Xo7xi
升级会员 