下载文档原格式
同余法解题集团标准化办公室：[VV986T-J682P28-JP266L8-68PNN]五年级奥数培训资料第六讲同余法解题一、同余这个概念最初是由德国数学家高斯发明的。
同余的定义是这样的：两个整数，a,b,如果他们同时除以一个自然数m，所得的余数相同，则称a,b对于模m同余。
记作a≡b（mod.m）。
读作：a同余于b模m。
同余的性质也比较多，主要有以下一些：1..对于同一个除数，两个数的乘积与它们余数的乘积同余。
例如201×95的乘积对于除数7，与201÷7的余数5和95÷7的余数4的乘积20对于7同余。
2..对于同一个除数，如果有两个整数同余，那么它们的差就一定能被这个除数整除。
例如519和399对于一个除数同余，那么这个除数一定是519与399的差的因数，即519与399的差一定能被这个除数整除。
3..对于同一个除数，如果两个数同余，那么他们的乘方仍然同余。
例如20和29对于一个除数同余，那么20的任何次方都和29的相同次方对于这个除数同余，当然余数大小随次方变化。
4．对于同一个除数，若三个数a≡b（mod m），b≡c（mod m），那么a,b,c三个数对于除数m都同余（传递性）例如60和76同余于模8，76和204同余于模8，那么60,76,204都同余于模8。
5. 对于同一个除数，若四个数a≡b（mod m），c≡d（mod m），那么a±c≡c±d （mod m），（可加减性）6. 对于同一个除数，若四个数a≡b（mod m），c≡d（mod m），那么ac≡cd（mod m），（可乘性）二、中国剩余定理解法一个数被3除余1，被4除余2，被5除余4，这个数最小是几？解法：求3个数：第一个：能同时被3和4整除，但除以5余4，即12X2＝24第二个：能同时被4和5整除，但除以3余1，即20X2＝40第三个：能同时被3和5整除，但除以4余2，即15x2＝30这3个数的最小公倍数为60，所以满足条件的最小数字为24＋40+30-60=3412X2＝24 20X2＝40 15x2＝30中2的来历。
二次同余式的一般形式ax2＋bx＋c≡0(mod m)由算术基本定理知道m可以分解成一些素数乘积,再由孙子定理知道ax2＋bx＋c≡0(mod m)可以转化为同余式组ax2＋bx＋c≡0(mod pα)因此,本章只讨论模为素数幂pα的同余式设p是素数，我们来研究素数模p的二次同余方程ax2+bx+c≡0 (mod p)。
(1)如果p= 2，则可以直接验证x≡0或1 (mod 2)是否方程(1)的解。
如果(a, p) = p，则方程(1)成为一元一次同余方程。
因此，只需考察p > 2，(a, p) = 1的情形。
此时，因为(4a, p) = 1，所以，方程(1)等价于方程4a2x2+4abx+4ac≡0 (mod p)，即(2ax+b)2≡b2-4ac(mod p)。
这样，研究方程(1)归结为对方程x2≡a(mod m) (2)定义１给定整数m，对于任意的整数a，(a，m) = 1，若方程x2 a(mod m)有解，则称a是模m的二次剩余；否则，称a是模m的二次非剩余.例1验证1是模4的平方剩余,‐1是是模4的非平方剩余 例21,2,4 是模7的平方剩余,‐1,3,5是模7的非平方剩余解因为,12≡1, 22≡4, 32≡2, 42≡2，52≡4，62≡1（mod7），例3 求满足方程E:y2≡x3+x+1(mod 7)的所有点 解x ≡0, y2 ≡1(mod 7) y ≡1,6 (mod 7)x ≡1, y2 ≡3(mod 7) 无解x ≡2, y2 ≡4(mod 7) y ≡2,5 (mod 7)x ≡3, y2 ≡3(mod 7) 无解x ≡4, y2 ≡6(mod 7) 无解x ≡5, y2 ≡5(mod 7) 无解x ≡36, y2 ≡6(mod 7) 无解4.2模为奇素数的平方剩余与非平方剩余 在这节里讨论模为素数的二次同余式定理１(欧拉判别条件) 若(a , p ) = 1，p 是奇素数则 (ⅰ) a 是模p 的二次剩余的充要条件是≡1 (mod p )；(3) (ⅱ) 若a 是模p 的二次剩余，则方程(2)有两个解； (ⅲ) a 是模p 的二次非剩余的充要条件是 ≡-1 (mod p )。
第4讲同余定理同余定理是奥数考试中最常考的题型，同时也是数论知识中最具有代表性的知识之一。
本讲将带领大家一起领略巧妙的数论方法，相信大家一定会被同余的意想不到的魅力所吸引。
若a c ÷余数为m ，b c ÷余数为n ，则()a b c +÷的余数等于()m n c +÷的余数；()a b c -÷的余数等于()m n c -÷的余数（m n >）或()m c n c +-÷的余数（m n <）。
a b c ⨯÷的余数等于m n c ⨯÷的余数。
特别的，当m n =时，()a b -是c 的倍数。
若两个整数a 、b 被同一个非零自然数c 除，余数相同，那么称a 、b 对于m 同余，用式子表示为(mod )a b c ≡.编写说明知识要点【例1】 有三个自然数a ，b ，c ，其中a 除以c 的余数是1，b 除以c 的余数是2，a b +恰好是c 的倍数，求c 的值。
【分析】 根据同余定理，a b +除以c 的余数是3，而a b +恰好是c 的倍数，所以3c =。
【拓展】 已知：6a b c -=，其中a 、b 、c 均为正整数，且b 除以6的余数是3，则a 除以6的余数是多少?【分析】 a b -是6的倍数，所以a 和b 除以6的余数相同，a 除以6的余数是3。
【温馨提醒】这边可以帮助学生总结出和（或差）的余数等于余数的和（或差）的余数。
【例2】 135********⨯⨯⨯⨯⨯的乘积除以8的余数是多少？【分析】 1，3，5，7，9，...，2007，2009除以8的余数分别为1，3，5，7，1，3，5，7， (1)3，5，7，1，1357⨯⨯⨯除以8的余数是1，所以135********⨯⨯⨯⨯⨯除以8的余数是1。
【温馨提示】这边可以帮助学生总结出积的余数等于余数的积的余数。
【拓展】 234199077777+++++的末两位是多少？【分析】 要求末两位，可以转化为求其除以100的余数是多少，7除以100余数是7，27除以100余数是49，37343=除以100余数为43，472401=除以100余数是1，54777=⨯除以100的余数是7，依此类推，余数是以7，49，43，1循环的，199044972÷=，所以所有余数的和是(749431)497749497+++⨯++=，49756除以100的余数是56，所以和的末两位是56。
第一章 整数的可除性§1 整除的概念·带余除法 1．证明定理3定理3 若12n a a a ，，，都是m 得倍数，12n q q q ，，，是任意n 个整数，则1122n n q a q a q a +++是m 得倍数．证明：12,,n a a a 都是m 的倍数。
∴ 存在n 个整数12,,n p p p 使 1122,,,n n a p m a p m a p m ===又12,,,n q q q 是任意n 个整数1122n nq a q a q a ∴+++1122n n q p m q p m q p m =+++1122()n n p q q p q p m =+++即1122n n q a q a q a +++是m 的整数2．证明 3|(1)(21)n n n ++ 证明(1)(21)(1)(2n n n n n n n ++=+++-(1)(2)(1)(n n n n n n =+++-+ 又(1)(2)n n n ++，(1)(2)n n n -+是连续的三个整数故3|(1)(2),3|(1)(1)n n n n n n ++-+3|(1)(2)(1)(1)n n n n n n ∴+++-+从而可知3|(1)(21)n n n ++3．若00ax by +是形如ax by +（x ，y 是任意整数，a ，b 是两不全为零的整数）的数中最小整数，则00()|()ax by ax by ++．证：,a b 不全为0∴在整数集合{}|,S ax by x y Z =+∈中存在正整数，因而有形如ax by +的最小整数00ax by +,x y Z ∀∈，由带余除法有0000(),0ax by ax by q r r ax by +=++≤<+则00()()r x x q a y y q b S =-+-∈，由00ax by +是S 中的最小整数知0r =00|ax by ax by ∴++00|ax by ax by ++ （,x y 为任意整数） 0000|,|ax by a ax by b ∴++ 00|(,).ax by a b ∴+ 又有(,)|a b a ，(,)|a b b00(,)|a b ax by ∴+ 故00(,)ax by a b +=4．若a ，b 是任意二整数，且0b ≠，证明：存在两个整数s ，t 使得||,||2b a bs t t =+≤成立，并且当b 是奇数时，s ，t 是唯一存在的．当b 是偶数时结果如何？ 证：作序列33,,,,0,,,,2222b b b bb b ---则a 必在此序列的某两项之间即存在一个整数q ，使122q q b a b +≤<成立 ()i 当q 为偶数时，若0.b >则令,22q qs t a bs a b ==-=-，则有 02222b q q qa bs t ab a b b t ≤-==-=-<∴<若0b < 则令,22q qs t a bs a b =-=-=+，则同样有2b t <()ii 当q 为奇数时，若0b >则令11,22q q s t a bs a b ++==-=-，则有 1102222b b q q t a bs a b a b t ++-≤=-=-=-<∴≤ 若 0b <，则令11,22q q s t a bs a b ++=-=-=+，则同样有2b t ≤，综上所述，存在性得证．下证唯一性当b 为奇数时，设11a bs t bs t =+=+则11()t t b s s b -=->而111,22b bt t t t t t b ≤≤∴-≤+≤ 矛盾 故11,s s t t ==当b 为偶数时，,s t 不唯一，举例如下：此时2b为整数 11312(),,22222b b b b b b b t t ⋅=⋅+=⋅+-=≤§2 最大公因数与辗转相除法 1．证明推论4.1推论4.1 a ，b 的公因数与（a ，b ）的因数相同． 证：设d '是a ，b 的任一公因数，∴d '|a ，d '|b 由带余除法111222111111,,,,,0n n n n n n n n n n a bq r b r q r r r q r r r q r r r r b---++-=+=+=+==≤<<<<∴(,)n a b r =∴d '|1a bq -1r =， d '|122b r q r -=，┄, d '|21(,)n n n n r r q r a b --=+=,即d '是(,)a b 的因数。
同余的概念与应用概念与性质1. 定义：若整数a,b 被整数m(m≥1)除的余数相同,则称a 同余于b 模m,或a,b 对模m 同余.记为a≡b(modm).余数r:0≤r<1.2. 性质：(ⅰ)a≡b(modm)⇔m|a-b,即a=b+mk,k ∈Z.(ⅱ)若a≡b(modm),b≡c(modm),则a≡c(modm).(ⅲ)若a 1≡b 1(modm),a 2≡b 2(modm)，则a 1±a 2≡b 1±b 2(modm),a 1a 2≡b 1b 2(modm);(ⅳ)设f(x)=a n x n +a n-1x n-1+…+a 1x+a 0,g(x)=b n x n +b n-1x n-1+…+b 1x+b 0是两个整系数多项式,满足a i ≡ b i (modm)(0≤i≤n).若a≡b(modm),则f(a)≡f(b)(modm).(ⅴ)ac≡bc(modm)⇔a≡b(mod ),(m c m ), (ⅵ)若m≥1,(a,m)=1,则存在整数c 使得ac≡1(modm).称c 为a 对模m 的逆或倒数,记为c=a -1(modm);(ⅶ)⎩⎨⎧≡≡)(mod )(mod 21m b a m b a 同时成立⇔≡a b (mod[m 1,m 2]);(ⅷ)若a≡b(modm 1),a≡b(modm 2),且(m 1,m 2)= 1,则a≡b(modm 1m 2).3. 剩余类：设m 为正整数，把全体整数按对模m 的余数分成m 类，相应m 个集合记为：K 0,K 1,…,K m-1,其中K r ={qm+r|q ∈Z,0≤余数r≤m -1}称为模m 的一个剩余类。
性质：(ⅰ)i m i K Z 10-≤≤= 且K i ∩K j =φ(i≠j).(ⅱ)每一整数仅在K 0,K 1,…,K m-1一个里.(ⅲ)对任意a 、b ∈Z ，则a 、b ∈K r ⇔a≡b(modm).4. 完全剩余系：设K 0,K 1,…,K m-1为模m 的全部剩余类，从每个K r 里任取一个a r ，得m 个数a 0,a 1,…,a m-1组成的数组，叫做模m 的一个完全剩余系。
知识框架一、带余除法的定义及性质1. 定义：一般地，如果a是整数，b是整数（b工0若有a4）=q••…r，也就是a= b X q+ r,0奇v b ;我们称上面的除法算式为一个带余除法算式。
这里：（1）当r 0时：我们称a可以被b整除，q称为a除以b的商或完全商（2）当r 0时：我们称a不可以被b整除，q称为a除以b的商或不完全商一个完美的带余除法讲解模型：如图屈这是一堆书，共有a本，这个a就可以理解为被除数，现在要求按照b本一捆打包，那么b就是除数的角色，经过打包后共打包了c捆，那么这个c就是商，最后还剩余d本，这个d就是余数。
这个图能够让学生清晰的明白带余除法算式中4个量的关系。
并且可以看出余数一定要比除数小。
2. 余数的性质⑴ 被除数除数商余数；除数（被除数余数）商；商（被除数余数）除数；⑵余数小于除数.二、余数定理：1.余数的加法定理a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。
例如：23, 16除以5的余数分别是3和1 ,所以23+16 = 39除以5的余数等于4,即两个余数的和3+1. 当余数的和比除数大时，所求的余数等于余数之和再除以c的余数。
例如：23, 19除以5的余数分别是3和4，所以23+19 = 42除以5的余数等于3+4=7除以5的余数为22.余数的加法定理a与b的差除以c的余数，等于a,b分别除以c的余数之差。
例如：23, 16除以5的余数分别是3和1，所以23 —16= 7除以5的余数等于2,两个余数差3- 1当余数的差不够减时时，补上除数再减。
例如：23, 14除以5的余数分别是3和4 , 23- 14= 9除以5的余数等于4,两个余数差为3 + 5-4 =43.余数的乘法定理a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。
例如：23, 16除以5的余数分别是3和1,所以23X 16除以5的余数等于3X1= 3。
一、带余除法的定义及性质：一般地，如果a是整数，b是整数（b≠0）,若有a÷b=q……r，也就是a＝b×q＋r,0≤r＜b；我们称上面的除法算式为一个带余除法算式。
这里：r时：我们称a可以被b整除，q称为a除以b的商或完全商(1)当0r时：我们称a不可以被b整除，q称为a除以b的商或不完全商(2)当0一个完美的带余除法讲解模型:如图，这是一堆书，共有a本，这个a就可以理解为被除数，现在要求按照b本一捆打包，那么b就是除数的角色，经过打包后共打包了c捆，那么这个c就是商，最后还剩余d本，这个d就是余数。
这个图能够让学生清晰的明白带余除法算式中4个量的关系。
并且可以看出余数一定要比除数小。
二、三大余数定理：1.余数的加法定理a与b的和除以c的余数，等于a,b分别除以c的余数之和，或这个和除以c的余数。
例如：23，16除以5的余数分别是3和1，所以23+16=39除以5的余数等于4，即两个余数的和3+1.当余数的和比除数大时，所求的余数等于余数之和再除以c的余数。
例如：23，19除以5的余数分别是3和4，故23+19=42除以5的余数等于3+4=7除以5的余数，即2.2.余数的乘法定理a与b的乘积除以c的余数，等于a,b分别除以c的余数的积，或者这个积除以c所得的余数。
例如：23，16除以5的余数分别是3和1，所以23×16除以5的余数等于3×1=3。
当余数的和比除数大时，所求的余数等于余数之积再除以c的余数。
例如：23，19除以5的余数分别是3和4，所以23×19除以5的余数等于3×4除以5的余数，即2.3.同余定理若两个整数a、b被自然数m除有相同的余数，那么称a、b对于模m同余，用式子表示为：a≡b ( mod m )，左边的式子叫做同余式。
同余式读作：a同余于b，模m。
由同余的性质，我们可以得到一个非常重要的推论：若两个数a，b除以同一个数m得到的余数相同，则a，b的差一定能被m整除用式子表示为：如果有a≡b ( mod m )，那么一定有a－b＝mk,k是整数，即m|(a－b)三、弃九法原理：在公元前9世纪，有个印度数学家名叫花拉子米，写有一本《花拉子米算术》，他们在计算时通常是在一个铺有沙子的土板上进行，由于害怕以前的计算结果丢失而经常检验加法运算是否正确，他们的检验方式是这样进行的：例如：检验算式12341898189226789671789028899231234除以9的余数为 11898除以9的余数为818922除以9的余数为 4678967除以9的余数为7178902除以9的余数为0这些余数的和除以9的余数为 2而等式右边和除以9的余数为3，那么上面这个算式一定是错的。
第四章 同余式§1 基本概念及一次同余式作为一个解。
中的一切数，即成立，故把都能使中的任意整数，则剩余类的合理性：若定义的一个解。
叫做成立的一个整数，则是使若称为次数。
，则的同余式。
若称为模，则，其中，设余方程）的求解问题。
课题是研究同余式（同初等数论中的一个基本)(mod )(mod 0)()(mod 0)(2)(mod 0)()(mod )(mod 0)()(mod 0)(mod 0)()(011m a x K m a f a K m a f m x f m a x m a f a n m a m m x f a a x a x a x f m a a n i n n n n ≡≡''≡≡≡≡≡/≡∈+++=∈--+定义2定义1Z Z 。
，解数为，的解为同余式，所以，，的一切整数解为因为不定方程。
有解不定方程有解同余式的任一个解。
是同余式其中，，个解，它们是余式共有。
当此条件成立时，同有解的充分必要条件是，则一次同余式设d d k m dmk x x m b ax t t dmx x b my ax b d b my ax m b ax m b ax x d k m dmk x x d b d m b ax d m a 1,,1,0)(mod )(mod )2(|)(mod )1()(mod 1,,1,0)(mod |)(mod ),(0000-=⋅+≡≡∈+==+⇔=+⇔≡≡-=⋅+≡≡= Z 证明定理。
解时，一次同余式有唯一当)(mod 1),(1)(m b a x m a m -≡=ϕ注同余式的解法1、代入法（适用于模较小时） 。
，得的完全剩余系逐一代入以，，所以同余式有唯一解因为解同余式)17(mod 6171)17,3()17(mod 13≡=≡x x 解例1 2、公式法（适用于模较小时） 。
从而，，，所以同余式有唯一解因为解同余式)11(mod 8656)2()2()3(98981)11,8()11(mod 98491101)11(≡⋅≡⋅-≡-⋅-≡⋅≡⋅≡=≡--ϕx x 解例23、变换系数法。
（解答题36道）第四章同余式第四章同余式三、解答题1、设(,)1a m =，k 与m 是正整数，又设0(mod )k x a m ≡，证明同余方程(mod )kx a m ≡的一切解x 都可以表示成0(mod )x yx m ≡，其中y 满足同余方程1(mod )ky m ≡。
解：设1x 是0(mod )kx a m ≡的任意一个解，则一次同余方程01(mod )yx x m ≡有解y ，再由001()(mod )k k k k ky a y x yx x a m ≡≡≡≡得1(mod )ky m ≡，即1x 可以表示成0(mod )x yx m ≡，其中y 满足同余方程1(mod )ky m ≡；反之，易知如此形式的x 是(mod )kx a m ≡的解。
2、解同余方程组()()31mod1047mod15x x ≡≡??解：这同余方程组的解与同余方程组()()()()31mod 2,31mod5,47mod3,47mod5x x x x ≡??≡??≡??≡?的解相同，但第二个同余方程()31mod5x ≡可化为()2mod5x ≡, 第四个同余方程()47mod5x ≡可化为()2mod5x ≡-, 与()2mod5x ≡矛盾，所以原同余方程组无解.3、设素数2p >,求同余方程()21mod lx p ≡的解解：同余方程可写为()()()110mod lx x p-+≡由于()1,1|2x x -+,所以上式等价于()10mod lx p -≡或()10mod lx p+≡因此，对任意的1l ≥解为()1,1mod l x p ≡- 解数为2.4、求同余式32()4560(mod 27)f x x x x =-+-≡ 解：∵()0(mod3),()0(mod3)f x f x '≡≡无公解∴20有唯一解0(mod3)x ≡以13x t =代入()0(mod9)f x ≡得1(0)3(0)0(mod9)f t f '+≡ 但(0)3(mod9)f ≡，(0)5(mod9)f '≡故1360(mod 9)t +≡，2120(mod 3)t +≡，11(mod 3)t ≡ 因此12213,39t t x t =+=+是()0(mod9)f x ≡的唯一解将239x t =+代入()0(mod 27)f x ≡得2(3)9(3)0(mod 27)f t f '+≡ 但(3)0(mod 27)f ≡，(3)8(mod 27)f '≡故2890(mod 27)t ?≡，280(mod 3)t ≡，20(mod3)t ≡设2333,327,3(mod 27)t t x t x ==+≡是()0(mod 27)f x ≡的唯一解。
5、4521(mod132)x ≡.解：因为(45,132)3=∣21 ,所以同余式有3个解. 将同余式化简为等价的同余方程)44(mod 715≡x . 我们再解不定方程74415=-y x ,得到一解(21,7). 于是定理4.1中的210=x . 因此同余式的3个解为)132(mod 21≡x ,)132(mod 65)132(mod 313221≡+≡x , )132(mod 109)132(mod 3132221≡?+≡x .6、11175(mod321)x ≡.解：因为(111,321)3=∣75,所以同余式有3个解. 将同余式化简为等价的同余方程)107(mod 2537≡x . 我们再解不定方程2510737=+y x , 得到一解(8,3)-.于是定理4.1中的80-=x . 因此同余式的3个解为)321(mod 8-≡x ,)321(mod 99)321(mod 33218≡+-≡x , )321(mod 206)321(mod 332128≡?+-≡x .7、??≡≡≡)9(mod 3)8(mod 2)7(mod 1x x x .解: 因为(7,8,9)=1,所以可以利用定理5.1.我们先解同余式)7(mod 172≡x ,)8(mod 163≡x ,)9(mod 156≡x ,得到)9(m od 4),8(m od 1),7(m od 4321-=-==x x x .于是所求的解为).494(mod 478)494(mod 510 )494(mod 3)4(562)1(631472=-=?-?+?-?+??≡x8、判定()322310mod5x x x -+-≡是否有3个解解：()322310mod5x x x -+-≡等价于()323430mod5x x x -+-≡，又()()()532223433561215x x x x x x x x x -=-+-+++-+，其中()261215r x x x =-+的系数的都不是5的倍数，故方程没有3个解9、解同余式95(mod 25)x ≡解：95(mod 25)1810(mod 25)x x ≡?-≡- 710(mod 25)x ?≡- 45(mod 25)x ?≡ 5(mod 25)x ?≡-10、同余方程256490(mod 60)x x ++≡的解的个数. 解：因为60345=?? 所以2 56490(mod60)x x++≡等价于256490(mod3)x x ++≡ （1） 256490(mod 4)x x ++≡ （2）256490(mod5)x x ++≡ （3）解同余方程（1）（2）（3）得到111x≡ 121(mod3)x ≡- 221211(mod 4)x x ≡≡- 311(mod5)x≡所以原方程的解得个数有2*2*1=4个。
11、解同余式89(mod11)x ≡ 解：Q (8,11)1=Q 同余式只有一个解 Q 11是素数(11)10?∴=9988(mod11)x ∴≡?≡12、解同余方程组2(mod 3)3(mod 5)2(mod 7)x x x =??=??=?解：利用孙子定理有，357105m =??=,135M =,221M =,315M =∴''11351(mod3)2(mod3)M M ≡?≡''22211(mod 5)1(mod 5)M M ≡?≡''33151(mod 7)1(mod 7)M M ≡?≡∴0235232112151(mod105)23(mod105)x ≡??+??+??≡13、求整数n ，它被3，5，7除的余数分别是1，2，3。
解：n 是同余方程组1(mod 3)2(mod 5)3(mod 7)n n n ≡??≡??≡?的解.在孙子定理中，取1233,5,7,345105m m m m ====??=，12335,21,15,M M M === 123'1,'1,'1,M M M =-==则135(1)2211315152(mod105)n ≡??-+??+??≡ 因此所求的整数52105,n t t z =+∈.14、求()()()3mod85mod37mod5x x x ≡??≡??≡?的解解：23530M =??=；13515M =?=而()'111mod2M M ?≡所以()'11mod 2M ≡同理210M =而()'221mod3M M ?≡所以()'21mod3M ≡36M =，而()'331mod5M M ?≡所以()'31mod5M ≡所以()3'11153110516717mod 30i i i M M x =≡?≡??+??+??≡∑15、解同余方程组1(mod 3)1(mod 5)2(mod 7)2(mo11)x x x x =??=-?=??=-?解：取12343,5,7,11m m m m ====，都是素数，满足条件。
∴12345711,3711,3511,357M M M M =??=??=??=??我们来求1j M -.由于1(1)(1)(1)1(mod 3)M ≡-??-≡知，111111(mod 3)M M M --≡≡，因此可取111M -=.由2(2)(2)11(mod5)M ≡-??≡知， 112221(mod 5)M M M --≡≡因此可取121M -=，由33544(mod 7)M ≡??≡知，1133314(mod 7)M M M --≡≡因此可取132M -=.由4357476(mod11)M ≡??≡?≡知， 1144416(mod11)M M M --≡≡ 因此可取142M -=.所以同余方程的解为：(5711)11(3711)1(1)(3511)22(357)2(2)(mod35711)x ≡+-++-???，即385231660420394(mod1155)x ≡-+-≡16、解同余方程()432890mod35x x x +++≡ ()1解：因为3557=?，所以同余方程()1等价于同余方程组()432890mod5x x x +++≡ ()2()432890mod7x x x +++≡ ()3()()23分别解同余方程，得到解()()()11121,4mod5x x ≡≡()()()()2221233,5,6mod7x x x ≡≡≡()1x 这样，同余方程的解可由下面的方程组决定：()()12mod5,mod7x a x a ≡≡其中11a =或4，23a =或5或6.利用孙子定理，取125,7,35m m m ===()()''12127,5,71mod5,51mod7M M M M ==≡≡''123,3M M ==则()122115mod35x a a =+()121a a 将，所有可能的取值代入上式，得到方程的全部解是()()()()()()12345621115331mod 3521115526mod 352111566mod 3521415324mod 3521415519mod 3521415634mod 35x x x x x x ≡?+?≡≡?+?≡≡?+?≡≡?+?≡≡?+?≡≡?+?≡17、解同余式()89mod11x = 解：Q ()8,111=∴同余式只有一个解 11Q 是素数()1110?=∴9988mod11x ≡?≡（）18、解同余方程：()315mod17x ≡解：若()()00mod f x m ≡，则()()()()000mod f x b x b x m +≡成立，反之，若()()()()000mod f x b x b x m +≡，则()()00mod f x m ≡成立；19、解同余方程1410346180(mod 5).x x x ++-≡解：由Fermat 定理得，5(mod5),x x ≡因此，原同余方程等价于2230(mod 5)x x +-≡ 将0,1,2(mod5)x =±±分别代入方程2230(mod 5)x x +-≡中进行检验，可得原同余方程的解是：1(mod5)x ≡20、解同余方程3x 2x 120mod81-+≡（）解：方程3x 2x 120mod3-+≡（）有一解()x 0mod3≡，故1x 3t =，()3f x -2x 12x =+，()2f x 3x -2'=，(0)12f =, '(0)2f =-解2112230(mod 3)t -?≡，得21t 2(mod3)≡，12t 23t =+ ，2x 63t2=+?，(6)216f = ，'(6)106f =,解2322161063t 0(mod3)+?≡，得32t 0(mod3)≡ 故23t 3t =，33x 63t =+，再解()3432161063t 0mod3+?≡，得()43t 1mod3≡故4344t 13t ,333t x =+=+原方程的解为()x 33mod81≡21、1、求同余方程96(mod15)x o的所有解. 解：因为(9,15)3=且3整除6所以同余方程96(mod15)x o恰有三个解.先求同余方程32(mod5)x o的唯一解，显然321012(mod5),4(mod5)x x汉所以原同余方程96(mod15)x o的三个解为4(mod15),9(mod15),14(mod15)x xx 汉?2、求一次同余方程组2(mod 35)9(mod14)7(mod 20)x y z ìooí??o 解：由于35、14、20两两不互质，所以不能直接用孙子定理，原一次同余方程组与一次同余方程组2(mod5)2(mod 7)9(mod 2)9(mod 7)7(mod 4)7(mod5)x x x x x x ìoo???oíoo?o??等价显然，去掉相同的一次同余方程后，此一次同余方程组又与一次同余方程组2(mod 5)2(mod 7)9(mod 2)7(mod 4)x x x x ìooí?oo等价，由于4,22=（）能被92-（）整除，此一次同余方程组又与一次同余方程组{2(mod 5)2(mod 7)7(mod 4)x x x ìooí??o等价此时574、、两两互质，由孙子定理知，原一次同余方程组有唯一解12,3574140,7428,5420,5735,1(mod ),13,i i i m i iNM M M M M m =创==?=?=?海Ｎ求得,,,1232,6,3M M M === 所以2282220673531087107(mod140)x 捍?创+创汉为原一次同余方程组的解.3、解同余方程组()()351mod 7232mod 7x y x y +≡-≡??解:()194mod7y ≡-()54mod7y ≡- ()2mod7y ≡再代入()351mod7x y +≡()3101mod7x +≡ ()4mod7x ≡即方程组的解是()4,2mod7x y ≡≡4、解同余方程()67mod23x ≡.解：()67mod23x ≡()5732mod23x ?≡-?≡()3248mod23x ?≡-?≡- ()()28710mod23x ?≡--≡ ()5mod23x ?≡5、解同余式. 12150(mod15)x +≡解：因为()12,453=︱5,所以同余式有解,而且解的个数为3.又同余式等价于450(mod15x +≡即4515x y +=. 我们利用解不定方程的方法得到它的一个解是()10,3, 即定理4.1中的010x = . 因此同余式的3个解为()10mod45x ≡ ,()()4510mod 4525mod 253x ≡+≡, ()()45102mod 4540mod 253x ≡+?≡.6、韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵数. 解：1234(mod5),(mod 6),(mod 7),(mod11)x b x b x b x b ≡≡≡≡，此时：567112310m ==16711462M =??= 25711385M =??= 35611330M =??= 4567210M =??=1(mod ),1,2,3,4i i i M M m i '?== 得1234M =3,M =1,M =1,M =1''''故：12343462385330210(mod 2310)x b b b b ≡?+?+?+?又12341,5,4,10b b b b ====Q34621385533042101067312111(mod 2310)x ∴≡??+?+?+?≡≡7、解同余方程53140(mod 45)x x +-≡.解：原同余方程等价于同余方程组53140(mod 9)x x +-≡， (1) 53140(mod 5)x x +-≡. (2)先解同余方程(1).容易验证，同余方程53140(mod3)x x +-≡的解是2(mod3)x ≡. 令23x t =+并代入方程(1)，得到5(23)3(23)140(mod 9)t t x +++-≡ ， (3)容易看出，这是一个对于任何整数t 都成立的同余式，所以，方程(3)的解是0,1,2(mod3)t ≡，于是方程(1)的解是2,5,8(mod9)x ≡. (4)再解同余方程(2).用0,1,2,3,4x =去验证，得到(2)的解是1,2(mod5)x ≡.因此，原同余方程的解是下面六个同余方程组的解：11(mod9),2,5,8x a a ≡=，22(mod5),1,2x a a ≡=.利用孙子定理解这六个方程组，记1212129,5,45,5,9,2,1m m m M M M M ''=======-则12109(mod 45)x a a ≡-.将1a 和2a 的不同取值代入，得到所求的解是110.29.111(mod 45)x ≡-≡，210.29.22(mod 45)x ≡-≡，310.59.141(mod 45)x ≡-≡，410.59.232(mod 45)x ≡-≡，510.89.126(mod 45)x ≡-≡，610.89.217(mod 45)x ≡-≡.8、解同余方程256490(mod 60)x x ++≡.（理由：考察孙子定理，解同余方程组.）解：因为60345=??，所以，原同余方程等价于同余方程组()()()256490(mod 3)156490(mod 4)256490(mod 5)3x x x x x x ?++≡??++≡??++≡??L L L L L L L L L 分别解同余方程()()()1,2,3，得到解()()()()()()11122212311,1(mod3),1,1(mod 4),1mod5x x x x x ≡≡-≡≡-≡这样，原同余方程的解可由下面的方程组决定：()()()123mod3mod 4mod5x a x a x a ≡??≡??≡? 其中1231,1;1,1;1a a a =-=-=.利用孙子定理，令1233,4,5,60m m m m ====12312320,15,122,1,3M M M M M M ==='''==-=则123401536(mod 60)x a a a ≡-+将123,,a a a 所有可能的取值带入上式，得到原方程的全部解是11114011513611(mod 60)40(1)15136119(mod 60)40115(1)36131(mod 60)40(1)15(1)36111(mod 60)x x x x ≡?-?+?≡≡?--?+?≡-≡?-?-+?≡≡?--?-+?≡9、判定同余方程32310(mod 7)x x ++≡是否有三个解.（理由：考察素数模的同余方程的解的个数，应用第四节的Fermat 定理及定理4.）解：因为()241mod7?≡，所以，原方程与3 424340(mod 7)x x ?+?+≡即3230(mod 7)x x --≡等价.由于()(7342223234121612x x x x x x x x x -=--++++++，所以，由定理4可知，原方程的解数小于3.10、有一对士兵，若三人一组则余一人，若五人一组，则余2人，若十一人一组，则余3人，已知这对士兵不超过170人，问这对士兵有几人？解：设士兵有x 人，则由题意得1(mod 3)x ≡，-2(mod 5)x ≡3(mod 11)x ≡ 由孙子定理得58(mod 165)x ≡ 故58x =人.12、求一个最小的自然数n ，使得它的12是一个平方数，它的13是一个立方数，它的15是一个5次方数.解：可设352y n βα=，由条件得()()()1mod2,0mo d3,0mod5;ααα≡≡≡()()()0mod2,1mod3,0mod5;βββ≡≡≡()()()0mod2,0mod3,mod5,γγγ≡≡≡由孙子定理得()()()15mod30,10mod30,6mod30,αβγ≡≡≡故10615352n =.13、解同余方程组 ()()351mod 7232mod 7x y x y +≡-≡??解：()194mod7y ≡-()54mod7y ≡- ()2mod7y ≡再代入()351mod7x y +≡()3101mod7x +≡ ()4mod7x ≡即方程组的解是()4,2mod7x y ≡≡14、证明不定方程333123494x x x x ++=±没有整数解.证明：取9m =.因为310x ≡，1(mod9)±，于是同余式3331234(mod 9)x x x ++≡±无解，由此知原方程无整数解.15、解同余方程()()234150mod75f x x x =+-≡.解：因27535=?，先解()()0mod3f x ≡，用逐一代入法得解()0mod3x ≡；再解()()20mod5f x ≡，用逐一代入法得()()0mod5f x ≡的解为()0,2mod5x ≡，对于()0mod5x ≡，令5x t=代入()()0mod25f x ≡得()2mod5t ≡，于是()225251025x t t =+=+，即()10mod25x ≡是()()0mod25f x ≡的一个解，对于()2mod5x ≡，令25x t=+代入()()0mod25f x ≡得()4mod5t ≡，于是()2225452225x t t =++=+，即()22mod25x ≡是()()0mod25f x ≡的一个解；最后构造同余方程组()1mod3x b ≡，()2mod25x b ≡，10b =，210,22b =，由孙子定理得()()0mod75f x ≡的两个解()10,72mod75x ≡.16、设p 是素数，0a p <<，证明：()1(1)(2)(1)(1)mod !a p p p a xb p a ----+≡-.是同余方程()mod ax b p ≡的解.解：首先易知!)1()2)(1()1(1a a p p pb a +-----是整数，又由(),1a p =知方程()mod ax b p ≡解唯一，故只须将()1(1)(2)(1)(1)mod !a p p p a xb p a ----+≡-代入()mod ax bp ≡验证它是同余方程的解即可.17、证明：同余方程()1122...mod n n a x a x a x b m +++=有解的充要条件是()12,,...,,|n a a a m d b =.若有解，则恰有1n d m -?个解，mod m .解：必要性显然，下证充分性.当1n =时，由定理2知命题成立.假设n k =时结论已真，考虑()1122...mod n n a x a x a x b m +++=，令()121,,...,,n a a a m d =，()11,k d a d +=，因为同余方程()111mod k k a x b d ++=有解，其解数为d ，1mod d ，记11m m d =，则解数为1dm ，mod m .现在固定一个解1k x +，由归纳假定知()1122...mod k k a x a x a x b m +++= 有解，其解数为11k d m -，mod m，从而()1122...mod n n a x a x a x b m +++= 有解，其解数为111k k dm d m d m -?=?，mod m .由归纳原理知命题对于一切1n ≥成立.18、解同余方程：()2311200mod15x x +-≡.解：因105357=?? 同余方程()2311200mod3x x +-≡的解为()1mod3x ≡，同余方程()2311200mod5x x +-≡的解为()0,3mod5x ≡，同余方程()2311200mod7xx +-≡的解为()2,6mod7x ≡，故原同余方程有4解，mod105. 作同余方程组：()1mod3x b ≡，()2mod5x b ≡，()3mod7x b ≡，其中1231,0,3,2,6b b b ===由孙子定理得原同余方程的解为()13,55,58,100mod105x ≡.19、解同余方程组：??≡≡≡。
