初等数论4同余式

《初等数论4同余式》由会员分享，可在线阅读，更多相关《初等数论4同余式（63页珍藏版）》请在金锄头文库上搜索。

1、第四章第四章 同同 余余 式式4.1 4.1 基本概念及一次同余式基本概念及一次同余式 2024/7/241一、基本概念一、基本概念是关于模是关于模m的同余方程，或同余式。的同余方程，或同余式。则称为则称为n次同余方程。次同余方程。 则剩余类则剩余类 里的元素都满足该方程。里的元素都满足该方程。 定义定义1 12024/7/242定义定义2 设设a是整数，当是整数，当 成立时，成立时， 则称则称 是同余方程是同余方程(1)的一个解。的一个解。 即与即与a同余的一切整数作为（同余的一切整数作为（1）式的一个解。）式的一个解。注：同余方程注：同余方程(1)的解数是指它的关于模的解数是指它的关于模m

2、互不同余互不同余的所有解的个数，也即在模的所有解的个数，也即在模m的一个完全剩余系中的一个完全剩余系中的解的个数。显然，同余方程的解的个数。显然，同余方程(1)的解数不超过的解数不超过m。2024/7/243二、等价同余式二、等价同余式定理定理1 1 下面的结论成立：下面的结论成立：（1）设）设b(x)是整系数多项式，则同余方程是整系数多项式，则同余方程(1)与与 f(x) b(x) b(x) (mod m)等价；等价；（2）设）设b是整数，是整数，(b, m) = 1，则同余方程，则同余方程(1)与与 bf(x) 0 (mod m)等价；等价；（3）设）设m是素数，是素数，f(x) = g(

3、x)h(x)，g(x)与与h(x)都是都是 整系数多项式，又设整系数多项式，又设x0是同余方程是同余方程(1)的解，的解， 则则x0必是同余方程必是同余方程 g(x) 0 (mod m) 或或 h(x) 0 (mod m)的解。的解。2024/7/244三、一次同余方程的基本解法三、一次同余方程的基本解法定理定理2 设设a，b是整数，是整数，a 0 (mod m)。则同余方程。则同余方程 ax b (mod m) (2) 有解的充要条件是有解的充要条件是(a, m) b。 若有解，则恰有若有解，则恰有d = (a, m)个解。个解。 特别地，若特别地，若(a, m)1，则方程（，则方程（2）有

4、唯一解。）有唯一解。证明证明 ax b (mod m) 同余方程同余方程(2)等价于不定方程等价于不定方程 ax my = b， (3)因此，第一个结论可由第二章第一节定理因此，第一个结论可由第二章第一节定理1P25得出。得出。2024/7/245若同余方程若同余方程(2)有解有解x0，则存在，则存在y0，使得，使得x0与与y0是是方程方程(3)的解，的解，由式由式(4)所确定的所确定的x都满足方程都满足方程(2)。 ax b (mod m) (2) ax my = b (3)此时，方程此时，方程(3)(3)的解是的解是记记d = (a, m)，以及，以及t = dq r，q Z，r = 0,

5、 1, 2, , d 1.0 r d 1。 2024/7/246容易验证，当容易验证，当r = 0, 1, 2, , d 1时，相应的解时，相应的解对于模对于模m是两两不同余的，所以同余方程是两两不同余的，所以同余方程(2)恰有恰有d个解。个解。解方程解方程(2)(2)的方法：的方法： 先求出相应不定方程先求出相应不定方程 ax my = b的一个特解的一个特解 2024/7/247例例1 1 解同余式解同余式 故原同余式有故原同余式有3 3个解。个解。 所以所以 原同余式的解为原同余式的解为 2024/7/248四、其他解法四、其他解法定理定理3 3 ax b (mod m)证证: 直接验算

6、，有直接验算，有 ax b ym b (mod m)。 注：注： 将一个对于较大模将一个对于较大模m的同余方程转化为一个对于的同余方程转化为一个对于较小模较小模a的同余方程，设的同余方程，设m r (mod a)，r 0，且，且(a, m) = 1，a1是是m对模对模a的最小的最小非负剩余，则同余方程非负剩余，则同余方程等价于同余方程等价于同余方程 ax b (mod m) 证：设证：设x是是ax b (mod m)的解，的解， 即即x是同余方程是同余方程 的解。的解。 由假设条件知：这两个同余方程都有且只有一个解，由假设条件知：这两个同余方程都有且只有一个解，所以这两个同余方程等价。所以这两

7、个同余方程等价。2024/7/2413例例3 解同余方程解同余方程6x 7 (mod 23)。解解 由定理由定理4 4，依次得到，依次得到6x 7 (mod 23) 5x 7 3 2 (mod 23) 3x 2 4 8 (mod 23) 2x 87 10 (mod 23) x 5 (mod 23)。ax b (mod m) 2024/7/2414定理定理5 5 四、其他解法四、其他解法 应用欧拉定理应用欧拉定理设设(a, m) = 1，并且有整数，并且有整数 0使得使得 a 1 (mod m)， 则同余方程则同余方程ax b (mod m)的解是的解是 x ba 1 (mod m).注注1 1

8、：直接验证即可。：直接验证即可。 注注2：由定理：由定理5及及Euler定理可知，若定理可知，若(a, m) = 1，则，则x ba (m) 1 (mod m) 是同余方程是同余方程ax b (mod m)的解。的解。例例4 4 解同余方程解同余方程 解：解：x ba (21) 1 2024/7/2415五、简单同余方程组五、简单同余方程组模相同模相同的解法的解法例例5 5 解同余方程组解同余方程组 解解: :将将(*)(*)的前一式乘以的前一式乘以2 2，后一式乘以，后一式乘以3 3，相减得到，相减得到 (*)(*)19y 4 (mod 7)，即即 5y 4 (mod 7)，y 2 (mod

9、 7)。再代入再代入(*)(*)的前一式得到的前一式得到 3x 10 1 (mod 7)， x 4 (mod 7)。即同余方程组即同余方程组(*)(*)的解是的解是x 4，y 2 (mod 7)。注：注：同余方程组的解法与方程组的解法相似。同余方程组的解法与方程组的解法相似。2024/7/24164.2 4.2 孙子定理孙子定理 2024/7/2417问题：问题：今有物不知其数，三三数之剩二，五五数之今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。剩三，七七数之剩二，问物几何。孙子算经孙子算经分析：分析：设所求物数为设所求物数为x，则有，则有 称之为同余式组。称之为同余式组

10、。即要求这些同余式的公共解。即要求这些同余式的公共解。2024/7/2418问题：问题：今有物不知其数，三三数之剩二，五五数之今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。剩三，七七数之剩二，问物几何。孙子算经孙子算经为什么啊？为什么啊？除除数数余余数数最小公最小公倍数倍数衍数衍数乘乘率率 各各 总总答答 数数最小最小答数答数3 32 2357357=105=10557572 235233523140+63140+63+30+30=233=233233-233-21052105=23=235 53 337371 1211321137 72 235351 115121512

11、2024/7/2419问题问题1：今有物不知其数，三三数之剩二，五五数之今有物不知其数，三三数之剩二，五五数之剩二，七七数之剩二，问物几何。剩二，七七数之剩二，问物几何。问题问题2：今有物不知其数，三三数之剩二，五五数之今有物不知其数，三三数之剩二，五五数之剩三，问物几何。剩三，问物几何。x-2是是3、5、7的公倍数。的公倍数。2024/7/2420问题：问题：今有物不知其数，三三数之剩二，五五数之今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。剩三，七七数之剩二，问物几何。孙子算经孙子算经2024/7/2421一、同余式组的解法一、同余式组的解法中国剩余定理中国剩余定理定

12、理定理1 1 孙子定理孙子定理 m1, m2, , mk是两两互质的正整数，是两两互质的正整数， 记记 m = m1m2mk ， 则则(1)的解为的解为 其中，整数其中，整数Mi （1 i k），满足），满足MiMi 1 (mod mi). 设有同余式组设有同余式组2024/7/2422证明：证明： 由由 (Mi, mi) = 1，利用辗转相除法可以求出，利用辗转相除法可以求出Mi 与与yi ，使得，使得MiMi yimi = 1， aiMiMi ai (mod mi)，1 i k。2024/7/2423反之，若反之，若 是（是（1）的解，）的解， 又又 m1, m2, , mk两两互质，两两

13、互质， 故方程（故方程（1 1）的解只能为（）的解只能为（2 2）式。）式。2024/7/2424例例1 1 解同余式组解同余式组 衍数衍数乘率乘率2024/7/2425例例2 2 韩信点兵韩信点兵有兵一队，若列成五行纵队，则有兵一队，若列成五行纵队，则末行末行1 1人；成六行纵队，则末行人；成六行纵队，则末行5 5人；成七行纵队，人；成七行纵队，则末行则末行4 4人；成十一行纵队，则末行人；成十一行纵队，则末行1010人。求兵数。人。求兵数。余数余数衍数衍数2024/7/2426列表如下：列表如下：其他略其他略14623 53851 43301 102101 673131112024/7/2

14、427定理定理2 在定理在定理1的条件下，若式的条件下，若式(1)中的中的a1, a2, , ak分别通过模分别通过模m1, m2, , mk的完全剩余系，则式的完全剩余系，则式(2)中中的的x通过模通过模m1m2mk的完全剩余系。的完全剩余系。证明：证明：则则x通过通过m1m2mk个整数，个整数， 且容易它们是两两不同余的。且容易它们是两两不同余的。2024/7/2428二、同余方程组解的存在性及解数的判定二、同余方程组解的存在性及解数的判定引理引理：设：设a1，a2是整数，是整数，m1，m2是正整数，则是正整数，则 同余同余方程组方程组有解的充要条件是有解的充要条件是 a1 a2 (mod

15、 (m1, m2) (4)若有解，则对模若有解，则对模m1, m2是唯一的，即若是唯一的，即若x1与与x2都是都是同余方程组同余方程组(3)的解，的解，则则 x1 x2 (mod m1, m2)。 (5)证证 必要性必要性 2024/7/2429充分性充分性记记(m1, m2)d.若式若式(4)(4)成立，成立， 则同余方程则同余方程m2y a1 a2 (mod m1) 有解有解y y0 (mod m1)， 记记x0 = a2 m2y0，则，则 x0 a2 (mod m2).并且并且 x0 = a2 m2y0 a2 a1 a2 a1 (mod m1)，因此因此x0是同余方程组是同余方程组(3)

16、的解。的解。若若x1与与x2都是方程组都是方程组(3)的解，的解， 则则 x1 x2 (mod m1)，x1 x2 (mod m2)，从而有从而有 x1 x2 (mod m1, m2)。2024/7/2430定理定理3 3 同余方程组同余方程组(1)有解的充要条件是有解的充要条件是ai aj (mod (mi, mj)，1 i, j n。 (6)2024/7/24312024/7/24322024/7/24334.3 4.3 高次同余式的解数及解法高次同余式的解数及解法 2024/7/2434一、化合数模为两两互质的模一、化合数模为两两互质的模例例1 解同余方程解同余方程 5x2 6x 49

17、0 (mod 60)。（。（1）解：解： 60 = 3 4 5，同余方程同余方程(1)等价于同余方程组等价于同余方程组5x2 6x 49 0 (mod 3) 即即-x2 1 0 (mod 3) (2)5x2 6x 49 0 (mod 4) 即即x2 2x 1 0 (mod 4) (3)5x2 6x 49 0 (mod 5) 即即x -1 0 (mod 5) (4)由由(2)(2)得：得： x1(1) 1，x2(1) 1 (mod 3)，由由(3)(3)得：得： x1(2) 1，x2(2) 1 (mod 4)，由由(4)(4)得：得： x1(3) 1 (mod 5)2024/7/2435这样，同

18、余方程这样，同余方程(1)的解的解x可由下面的方程组决定：可由下面的方程组决定：x1(1) 1，x2(1) 1 (mod 3)，x1(2) 1，x2(2) 1 (mod 4)， x1(3) 1 (mod 5)x a1 (mod 3)，x a2 (mod 4)，x a3 (mod 5)，其中其中a1 = 1或或 1，a2 = 1或或 1，a3 = 1。 利用孙子定理，其中利用孙子定理，其中m1 = 3，m2 = 4，m3 = 5，m = 60.M1 = 20，M2 = 15，M3 = 12，M1 = 2，M2 = 1，M3 = 3，则则 x 40a1 15a2 36a3 (mod 60)。将将a

19、1，a2，a3所有可能的取值代入上式，得到方程所有可能的取值代入上式，得到方程(1)的全部解是的全部解是x1 1 (mod 60)，x2 19 (mod 60)，x3 31 (mod 60)，x4 11 (mod 60)。2024/7/2436注注：由定理：由定理4及算术基本定理，解一般模的同余方程及算术基本定理，解一般模的同余方程可以转化为解模为素数幂的同余方程。可以转化为解模为素数幂的同余方程。定理定理4 设设m = m1m2mk ，其中，其中m1, m2, , mk 是两两是两两互素的正整数，互素的正整数，f(x)是整系数多项式，以是整系数多项式，以T与与Ti（1 i k）分别表示同余方

20、程）分别表示同余方程f(x) 0 (mod m) （1）与与 f(x) 0 (mod mi) ，1 i k. （2）的解的个数，的解的个数，则则T = T1T2Tk 。2024/7/2437定理的证明：定理的证明：因为因为 a b (mod mi )，1 i k a b (mod m)，所以所以 同余方程同余方程(1)(1)等价于同余方程组（等价于同余方程组（2 2） f(x) 0 (mod m) （1）f(x) 0 (mod mi) ，1 i k. （2）对于每个对于每个i（1 i k），设同余方程），设同余方程(2)的全部解是的全部解是则同余方程组则同余方程组(3)等价于下面的等价于下面的

21、T1T2Tk个方程组：个方程组：其中其中 通过式通过式(3)中的数值，即通过方程中的数值，即通过方程(2)的全部解。的全部解。2024/7/2438f(x) 0 (mod m) （1）f(x) 0 (mod mi) ，1 i k. （2）由孙子定理，对于选定的每一组由孙子定理，对于选定的每一组 同余方程组同余方程组(4)对模对模m有唯一解。有唯一解。 而且，由而且，由4.2定理定理2， 当每个当每个 通过通过(3)式中的值时，式中的值时， 所得到的所得到的T1T2Tk个同余方程组个同余方程组(4)的解对于模的解对于模m都是都是两两不同余的。两两不同余的。 2024/7/2439二、方幂模的解法

22、二、方幂模的解法若若x0是同余方程是同余方程 f(x) 0 (mod p ) (1) 的解，的解，则必是方程则必是方程 f(x) 0 (mod p -1) (2) 的解的解. .因此，必有与因此，必有与x0相应的方程相应的方程(2)的某个解的某个解x1，使，使x0 x1 (mod p)，x0 = x1 p -1 t0，即可以从方程即可以从方程(2)(2)的解中去求方程的解中去求方程(1)(1)的解。的解。 但对于方程但对于方程(2)的每个解的每个解x1，是否必有方程，是否必有方程(1)的解的解x0与之对应？若有，如何去确定它？与之对应？若有，如何去确定它？ 2024/7/2440定理定理5 5

23、 设设p是素数，是素数，n 2，f(x) = anxn a1x a0是整系数多项式，又设是整系数多项式，又设x1是同余方程是同余方程(2)的一个解。的一个解。以以f (x)表示表示f(x)的导函数。的导函数。则对于则对于t = 0，1, 2, , p 1，式，式(3)中的中的x都是都是方程方程(1)(1)的解。的解。f(x) 0 (mod p ) (1)f(x) 0 (mod p -1) (2)是方程是方程(1)(1)的解。的解。2024/7/2441证明：如何确定式证明：如何确定式(3)(3)中的中的t， 使使x1 p 1t满足同余方程满足同余方程(1)， an(x1+p 1t)n+an 1

24、(x1+p 1t)n 1+a1(x1+p 1t)+a0 0 (mod p ) 即要使即要使由二项式定理展开可得由二项式定理展开可得 f(x1) p 1tf (x1) 0 (mod p ) （4）f(x) 0 (mod p ) (1)f(x) 0 (mod p -1) (2)下面考虑两种情形下面考虑两种情形 2024/7/2442(1) 若若f (x1) 0 (mod p)， 则关于则关于t的同余方程的同余方程(5)有唯一解有唯一解t t0 (mod p)， 即即t = t0 pk（k Z），）， 于是于是 x x1 p 1t0 (mod p ) 是同余方程是同余方程(1)的解。的解。(2) 若

25、若f (x1) 0 (mod p)，并且，并且f(x1) 0 (mod p )， 则式则式(5)对于任意的整数对于任意的整数t成立，成立， 即同余方程即同余方程(5)有有p个解个解 t i (mod p)，0 i p 1。于是于是 x x1 p 1i (mod p )，0 i p 1，都是，都是同余方程同余方程(1)的解。的解。 2024/7/24432024/7/2444例例2 2 解同余方程解同余方程 考虑方程：考虑方程：则则(2)(2)的解可表示为：的解可表示为：代入代入(2)(2)，得，得2024/7/2445则则(2)(2)的解可表示为：的解可表示为：即即(2)(2)的解可表示为：的

26、解可表示为：从而从而(1)(1)的解可表示为：的解可表示为：2024/7/2446推论推论1 1若若x a (mod p)是同余方程是同余方程 2024/7/2447推论推论2 22024/7/2448三、一般高次同余式的解法三、一般高次同余式的解法例例3 解同余方程解同余方程 x3 3x 14 0 (mod 45) 解：解： 原同余方程等价于同余方程组原同余方程等价于同余方程组 x3 3x 14 0 (mod 9)， (1) x3 3x 14 0 (mod 5). (2)先求先求(1)(1)的解：的解： x3 3x 14 0 (mod 3)的解为的解为 x 2 (mod 3)。令令x = 2

27、 3t并代入方程并代入方程(1)，得到，得到(2 3t)3 3(2 3t) 14 0 (mod 9)，恒成立。恒成立。于是方程于是方程(1)的解是的解是 x 2，5，8 (mod 9)。 2024/7/2449例例3 解同余方程解同余方程 x3 3x 14 0 (mod 45) (2) 的解为：的解为： x 1，2 (mod 5)。解：解： 原同余方程等价于同余方程组原同余方程等价于同余方程组 x3 3x 14 0 (mod 9)， (1) x3 3x 14 0 (mod 5). (2)(1) 的解是：的解是： x 2，5，8 (mod 9)。x a1 (mod 9)， a1 = 2，5，8，

28、x a2 (mod 5)， a2 = 1，2。因此，原同余方程的解是下面六个同余方程组的解：因此，原同余方程的解是下面六个同余方程组的解：利用孙子定理解这六个方程组利用孙子定理解这六个方程组. . 2024/7/2450记记 m1 = 9，m2 = 5，m = 45，M1 = 5，M2 = 9， 将将a1和和a2的不同取值代入，得到所求的解是的不同取值代入，得到所求的解是x1 10 2 9 1 11 (mod 45)，x2 10 2 9 2 2 (mod 45)，x3 10 5 9 1 41 (mod 45)，x4 10 5 9 2 32 (mod 45)，x5 10 8 9 1 26 (mo

29、d 45)，x6 10 8 9 2 17 (mod 45) 2024/7/24514.4 4.4 质数模的同余式质数模的同余式 2024/7/2452 在上节证明了，对于素数在上节证明了，对于素数p，模，模p 的同余的同余方程的求解可以转化为模方程的求解可以转化为模p的同余方程的求解。的同余方程的求解。本节要对素数模的同余方程做些初步研究。本节要对素数模的同余方程做些初步研究。以下，设以下，设f(x) = anxn a1x a0是整系数多项式，是整系数多项式， 2024/7/2453f(x) = anxn a1x a0 0 (mod p) (1)定理定理1 1 同余方程同余方程与一个次数不超过

30、与一个次数不超过p-1的同余式等价。的同余式等价。证：由带余数除法，存在整系数多项式证：由带余数除法，存在整系数多项式 由费马定理知，由费马定理知， 2024/7/2454定理定理2 2 设设k n，若同余方程，若同余方程(1)有有k个不同的解个不同的解其中其中fk(x)是一个次数为是一个次数为n k的整系数多项式，的整系数多项式，x1, x1, , xk，则对，则对 有有f(x) (x x1) (x x2)(x xk)fk(x) (mod p)，并且它的并且它的xn k项的系数是项的系数是an.证明：证明：由多项式除法，有由多项式除法，有f(x) = (x x1)f1(x) r1， (2)f

31、1(x)是首项系数为是首项系数为an的的n 1次整系数多项式，次整系数多项式，r1是常数。是常数。 在式在式(2)两边令两边令x = x1，则可知，则可知f(x1) = r1 0 (mod p)， 因此，式因此，式(2)成为成为 f(x) (x x1)f1(x) (mod p) (3)即即 当当k = 1时，定理成立。时，定理成立。 2024/7/2455如果如果k 1，在，在(3)式中，令式中，令x = xi（i = 2, 3, , k），）， 则有则有 0 f(xi) (xi x1)f1(xi) (mod p) (4)由于由于x1, x2, , xk对于模对于模p是两两不同余的，是两两不同

32、余的， f1(xi) 0 (mod p)，i = 2, , k。 (5)所以，由所以，由(4)(4)式得出式得出由此及归纳法，即可证明定理。由此及归纳法，即可证明定理。 f(x) (x x1)f1(x) (mod p) (3)2024/7/2456定理定理3 3 (1) 若若p是素数，则对于任何整数是素数，则对于任何整数x，有，有 x p 1 1 (x 1)(x 2)(x p 1) (mod p)。(2)Wilson定理定理 证明证明: : (1)由由Fermat定理，数定理，数1, 2, , p 1是同余方程是同余方程x p 1 1 (mod p)，即，即x p 1 1 0(mod p)的解

33、，的解， 因此，利用定理因此，利用定理2可得可得 x p 1 1 (x 1)(x 2)(x p 1) fk(x) (mod p)其中其中fk(x)an1，所以所以 x p 1 1 (x 1)(x 2)(x p 1) (mod p)。2024/7/2457定理定理4 4 同余方程同余方程(1)的解数的解数 n。证明证明: 假设同余方程假设同余方程(1)有有n + 1个不同的解个不同的解x xi (mod p)，1 i n 1。由定理由定理2，有，有f(x) an(x x1)(x xn) (mod p)， 因此因此 0 f(xn + 1) an(xn + 1 x1)(xn + 1 xn) (mod

34、 p)。 矛盾！矛盾！2024/7/2458定理定理5 5 设设n p，则同余方程，则同余方程f(x) = xn an 1xn 1 a1x a0 0 (mod p) (1)有有n个解的充要条件是个解的充要条件是 存在整数多项式存在整数多项式q(x)和和r(x)，r(x)的次数的次数 n，使得，使得 x p x = f(x)q(x) p r(x)。 证明证明 必要性必要性 由多项式除法，存在整系数多项式由多项式除法，存在整系数多项式 q(x)与与r1(x)，r1(x)的次数的次数 n，使得，使得 x p x = f(x)q(x) r1(x)。 若同余方程若同余方程(1)有有n个解个解x xi (

35、mod p)（1 i n），）， 2024/7/2459从而，从而， r1(xi) 0 (mod p)，1 i n， x p x = f(x)q(x) r1(x)。 又又r1(x)的次数的次数 n， 可知可知r1(x)的系数都能被的系数都能被p整除，即整除，即r1(x) = p r(x)，2024/7/2460充分性充分性 由由Fermat定理，对于任何整数定理，对于任何整数x，有，有 x p x 0(mod p)， 由由x p x = f(x)q(x) p r (x)得：得： 0 x p x f(x)q(x) (mod p) 又又 x p x 0 (mod p)有有p个解，个解，所以同余方程

36、所以同余方程 f(x)q(x) 0 (mod p)有有p个解。个解。但是，但是，q(x)是是p n次多项式，次多项式， 所以由定理所以由定理4，方程，方程q(x) 0 (mod p)的解数的解数 p n。 以以 表示同余方程表示同余方程f(x) 0 (mod p)的解数，的解数， 则有则有 + p n p， n， 利用定理利用定理4，得到，得到 = n。 2024/7/2461例例1 判定同余方程判定同余方程2x3 3x 1 0 (mod 7)是否有三个解。是否有三个解。解：解： 因为因为2 4 1 (mod 7)，所以，原方程与，所以，原方程与4 2x3 4 3x 4 0 (mod 7)即即

37、x3 2x 3 0 (mod 7) 等价。等价。 由于由于x7 x= ( x3 2x 3)(x4 2x2 3x 4) 12x2 16x 12，其中其中 12x2 16x 12不能写成不能写成7r(x)的形式，的形式，由定理由定理4，5可知，原方程的解数小于可知，原方程的解数小于3。 2024/7/2462例例2 解同余方程解同余方程 3x14 4x10 6x 18 0 (mod 5)。解：解： 由由Fermat定理，定理，x5 x (mod 5)， 因此，原同余方程等价于因此，原同余方程等价于 2x2 x 3 0 (mod 5)。 将将x 0， 1， 2 (mod 5)分别代入方程进行验证，分别代入方程进行验证， 可知这个同余方程解是可知这个同余方程解是x 1 (mod 5)。2024/7/2463