母减去或加上模的倍数及分子、分母乘以不为0的整数或约去一个与模数互素的数等若干次（这相当于对同余式的两边使用同余的性质）, 使分母的绝对值变小, 直至最后将“分数”变成整数, 即得(1.9.1)**的解, 由此便可求得(1.9.2)的解, 此法可称为“分式法”. 又例：
例1. 20 求解同余方程1593x?1125(mod1926).
解 因(1593,1926)?91125, 所以同余方程有九个解,将其简化得
177x?125(mod214).
因此
x?125125?214339113113?5565????? 1771771775959?5295137137?2143511313?7192367??????? 81818133?71213?1??67?147(mod214).
所以原方程的9个解为：
x?147,361,575,789,1003,1217,1431,1645,1859(mod1926). ▋
对于给定的一个同余方程, 用何种方法求解简单方便？若模m较小, 则用公式法直接简单. 若模m较大, 则用“数乘除法 ” 、还是“分式法”求解简捷, 应视具体情况而定.
练习1. 19
1. 下列同余方程有无解？有解时有几个解？
1) 3) 2.
1998x?1999(mod2000); 2) 111x?1110(mod1011); 891x?918?0(mod198); 4) ax?54?0(mod45).
b取何值时, 方程14x?b(mod114)
1) 在0?x?114中有多于一个的解？ 2) 无解.
3．利用本节提到的几种方法, 求解下列同余方程.
1) 3)
3x?12?0(mod15); 2) 49x?84?0(mod104); 5x?2(mod7) ; 4) 71x?1997(mod1999);
4. 知某一正整数的99次方除以97后得余数7, 而该正整数的100次方除97后得余数79, 问该正整数除以97后得到的余数是多少？
26
§1. 10 一次同余方程组与孙子定理
定义1. 13 有多个同余方程构成的组合称为同余方程组；称(1.10.1)式为一次同余方程组.
d1)?a1x?b1?0(mom?ax?b?0(momd2)?22 (1.10.1) ? ?????anx?bn?0(modmn)其中m1,m2,?,mn是正整数.
如果存在整数
x0使aix0?bi?0(modmi),(i?1,2,?,n),则称x?x0(modm)是(1.10.1)的一个解, 这里m??m1,m2,?,mn?.
本节的目的就是讨论(1.10.1)的解问题.
若(1.10.1)有解, 则(1.10.1)中每个同余方程有解；反之, 若(1.10.1)中某个同余方程无解, 则
(1.10.1)无解, 所以要研究(1.10.1)的解,可转化为研究下列同余方程的解.
?x?c1(modm1)?x?c(modm)?22 . (1.10.2) ? ?????x?cn(modmn)关于模
定理1.18(中国剩余定理) 若
m1,m2,?,mn是n个两两互素的正整数,则(1.10.2)m?m1m2?mn有唯一解
其中xi是
x?mx1c1?mx2c2???mxncn(modm), (1.10.3)
m1m2mnmx?1(modm)的一个整数解?i?1,2,?,n?. imim,m)?1.于是由定理1. 17知, 同余方 mii证 （存在性） 由m1,m2,?,mn两两互素知(程
mx?1(modm)(i?1,2,?,n) (1.10.4)
imi（i有唯一解. 设为x?x(modm). 即有mxi?1(modmi). 从而由mi|miimjmi?j）得
27
mxc?mxc???mxc?mxc?1?c?c(modm).
iiim111m222mnnnmiii这说明
x?mx1c1?mx2c2???mxncn(modm)
m1m2mn是(1.10.2)的一个解.
(唯一性) 若x?x1(modm)及x?x2(modm)是(1.10.2)的两个解, 则有x1?ci(modmi)及
?,n)两两互素得x2?ci(modmi)(i?1,2,?,n).于是x1?x2(modmi),从而由mi(i?1,2,, 亦即x1?x2(modm). 这说明x1(modm)与x2(modm)是(1.10.2)的x1?x2(modm1?mn)同一个解, 所以(1.10.2)只有一个解. ▋
定理1.18的存在性的证明过程具体给出了在mi两两互素的情况下同余方程组(1.10.2)的解法：首先分别求出每个方程
mx?1(modm) (i?1,2,?,n)
imi的一个整数解xi, 然后代入(1.10.3)式计算化简即得(1.10.2)的解.
定理1.18其实就是著名的孙子剩余定理, 国际上一般称之为中国剩余定理（Chinese Remainder Theorem， 又简称为CTR定理）.
历史回顾：公元五世纪前后, 我国出现了一部著名的著作-《孙子兵法》, 书中提出了这样一个问题：“今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何?”该问题简称“物不知数”问题.
如设所要求的物数为x, 则x就是下列同余方程组(1.10.5)的一个正整数解.
?x?2(mod3)??x?3(mod5). (1.10.5) ?x?2(mod7)?对于“物不知数”问题的解法,《孙子算经》中记述：“凡三三数之剩一, 置七十；五五数之剩一, 置二十一；七七数之剩一, 则置十五；一百零六以上, 以一百零五减知即得.”
明朝程大位在一五九三年出的一部著作《算经统宗》中关于“物不知数”问题有一首解法歌诀：
“三人同行七十稀, 五树梅花二十一支, 七子团圆整半月, 除百零五便得知.”
也就是说 , 该问题的解答是x例1. 21 解同余方程组
?70?2?21?3?15?2?233?23(mod105).
28
? x?1(mod5)??3x?2(mod7). ?5x?7(mod9)?解 该方程组形同(1.10.1), 先化为(1.10.2)的形式：即
?x?1(mod5)??x?3(mod7). ?x?5(mod9)?再利用孙子定理, 解形如
(1.10.4)的三个方程：
63x?1(mod, 545x?3(mod7)及
35x?5(mod9). 分别解之得x1?2,x2??2及x3??1各是上述同余方程的一个整数解.于是由(1.10.3)得原同余方程组的唯一的解为
x?63?2?1?45?(?2)?3?35?(?1)?5
??319??4(mod315). ▋
例1. 22 解同余方程组
?3x?11(mod28). ??5x?17(mod44)解
3x?11(mod285x?17(mod28)分别等价于 及
?3x?11(mod4) 及 ?3x?11(mod7)?从而原方程等价于
?5x?17(mod4), ?5x?17(mod11)??3x??1(mod4)?3x?4(mod7)?, 亦即 ?5x?1(mod4)???5x?6(mod11)然后如例1. 21那样解最后这个方程组即可.
例1. 23 解同余方程组
?x?1(mod4)??3x?4(mod7). ?5x?6(mod11)?? 2x? 4(mod8). ?15x?18(mod33)?解 因方程
2x?4(mod8)有两个解x?2,6(mod8), 方程15x?18(mod33)有三个解
x??1,10,21(mod33).
29
于是原同余方程组的解为下列六个同余方程组的全部解.
?x?2(mod8) ； ??x??1(mod33)?x?6(mod8) ； ?x??1(mod33)??x?2(mod8)； ??x?10(mod33)?x?6(mod8)； ?x?10(mod33)??x?2(mod8); ??x?10(mod33)?x?6(mod8). ?x?21(mod33)?分别利用孙子定理解之便得原同余方程组的六个解：
x?98,10,186,230,142,54(mod264). ▋
练习1.10
1. 解下列同余方程组
?x?1(mod7)?1）?x?2(mod8); 2)
?x?3(mod9)?2. 解答下列各题：
?11x?7(mod10)??3x?10?0(mod11); ?5x?3?0(mod13)?1) 有物不知其数. 三数余一, 五数余二, 七数余三, 11数余四, 问该物数.
2) 今有数不知总数. 以五累减之无剩, 以七百十五累减之剩十, 以二百四十七累减之剩一百四十,
以三百九十一累减之剩二百四十五, 以一百八十七累减之剩一百零九, 问总数若干？
3．有一电脑病毒每隔十三天连续发作两天, 有一次该病毒刚好在星期六、星期日发作,问该病毒至少要几星期后再在星期六发作？
4. 求既能被7除余3, 又能被11除余4的所有三位自然数之和.
5．试求一个满足下列条件的最大的负整数：该负整数用15除余8, 用10除余3, 用8除余1.
§1. 11 原根的定义
设m是大于1的正整数. 若(a,m)?1, 则由欧拉定理知a定义1. 14 1）设m?(m)?1(modm).
为模数
?1且(a,m)?1. d是方程ax?1(modm)的最小正整数解, 则称dm的阶，记作ordm(a). 2）设m?1且(a,m)?1. 如果对于所有的正整数k??(m), 都有ak?m, )则称a为模数m的一个原根. ?1(mod例如, 若m?7, a?2, 则20?1, 21?2, 22?4, 23?1(mod7), 因此ord7(2)?3.
例如,3是模数7的原根, 也是模数10的原根. 但是并非所有的模数m都有原根, 例如模数8就没有原根, 因为?(8)?4,而12?32?52?72?1(mod8).
例1. 24 设(a,m)?1, m?1,
a1 ,a2 ,? ,a?(m)是小于m且与m互素的不同的正整数.如果
30