初等数论第四章同余式.ppt

2019/4/3,1,第四章 同 余 式,4.1 基本概念及一次同余式,2019/4/3,2,一、基本概念,是关于模m的同余方程，或同余式。,则称为n次同余方程。,则剩余类 里的元素都满足该方程。,定义1,2019/4/3,3,即与a同余的一切整数作为（1）式的一个解。,注：同余方程(1)的解数是指它的关于模m互不同余 的所有解的个数，也即在模m的一个完全剩余系中 的解的个数。显然，同余方程(1)的解数不超过m。,2019/4/3,4,二、等价同余式,定理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(x)h(x)，g(x)与h(x)都是 整系数多项式，又设x0是同余方程(1)的解， 则x0必是同余方程 g(x) 0 (mod m) 或 h(x) 0 (mod m)的解。,2019/4/3,5,三、一次同余方程的基本解法,定理2 设a，b是整数，a 0 (mod m)。则同余方程,ax b (mod m) (2),有解的充要条件是(a, m)b。,若有解，则恰有d = (a, m)个解。,特别地，若(a, m)1，则方程（2）有唯一解。,证明 ax b (mod m),同余方程(2)等价于不定方程 ax my = b， (3),因此，第一个结论可由第二章第一节定理1P25得出。,2019/4/3,6,若同余方程(2)有解x0，则存在y0，使得x0与y0是 方程(3)的解，,由式(4)所确定的x都满足方程(2)。,ax b (mod m) (2),ax my = b (3),此时，方程(3)的解是,记d = (a, m)，以及t = dq r，qZ，r = 0, 1, 2, , d 1.,0 r d 1。,2019/4/3,7,容易验证，当r = 0, 1, 2, , d 1时，相应的解,对于模m是两两不同余的，所以同余方程(2)恰有d个解。,解方程(2)的方法：,先求出相应不定方程 ax my = b的一个特解,2019/4/3,8,例1 解同余式,故原同余式有3个解。,所以 原同余式的解为,2019/4/3,9,四、其他解法,定理3,ax b (mod m),证: 直接验算，有,ax b ym b (mod m)。,注： 将一个对于较大模m的同余方程转化为一个对于 较小模a的同余方程，设m r (mod a)，r a，则又可 继续转化成一个对于更小的模r的同余方程。,减小模,2019/4/3,10,例2 解同余方程 325x 20 (mod 161),解 d=1,原同余方程即是 3x 20 (mod 161)。,解同余方程 161y 20 (mod 3)，,2y 1 (mod 3)，,得到y 2 (mod 3)，因此原方程的解是,2019/4/3,11,补充说明,2019/4/3,12,例1 解同余式,另解：,先解同余方程,2019/4/3,13,四、其他解法,减小系数,定理4,设a 0，且(a, m) = 1，a1是m对模a的最小,非负剩余，则同余方程,等价于同余方程 ax b (mod m),证：设x是ax b (mod m)的解，,即x是同余方程 的解。,由假设条件知：这两个同余方程都有且只有一个解，,所以这两个同余方程等价。,2019/4/3,14,例3 解同余方程6x 7 (mod 23)。,解 由定理4，依次得到,6x 7 (mod 23), 5x 73 2 (mod 23), 3x 24 8 (mod 23), 2x 87 10 (mod 23), x 5 (mod 23)。,ax b (mod m) ,2019/4/3,15,定理5,四、其他解法,应用欧拉定理,设(a, m) = 1，并且有整数 0使得 a 1 (mod m)，,则同余方程ax b (mod m)的解是 x ba 1 (mod m).,注1：直接验证即可。,注2：由定理5及Euler定理可知，若(a, m) = 1，则,x ba(m) 1 (mod m) 是同余方程ax b (mod m)的解。,例4 解同余方程,解：x ba(21) 1,2019/4/3,16,五、简单同余方程组模相同的解法,例5 解同余方程组,解:将(*)的前一式乘以2，后一式乘以3，相减得到,(*),19y 4 (mod 7)，,即 5y 4 (mod 7)，,y 2 (mod 7)。,再代入(*)的前一式得到,3x 10 1 (mod 7)，,x 4 (mod 7)。,即同余方程组(*)的解是x 4，y 2 (mod 7)。,注：同余方程组的解法与方程组的解法相似。,2019/4/3,17,4.2 孙子定理,2019/4/3,18,问题：今有物不知其数，三三数之剩二，五五数之 剩三，七七数之剩二，问物几何。孙子算经,分析：设所求物数为x，则有,称之为同余式组。,即要求这些同余式的公共解。,2019/4/3,19,问题：今有物不知其数，三三数之剩二，五五数之 剩三，七七数之剩二，问物几何。孙子算经,为什么啊？,2019/4/3,20,问题1：今有物不知其数，三三数之剩二，五五数之 剩二，七七数之剩二，问物几何。,问题2：今有物不知其数，三三数之剩二，五五数之 剩三，问物几何。,x-2是3、5、7的公倍数。,2019/4/3,21,问题：今有物不知其数，三三数之剩二，五五数之 剩三，七七数之剩二，问物几何。孙子算经,2019/4/3,22,一、同余式组的解法中国剩余定理,定理1孙子定理,m1, m2, , mk是两两互质的正整数，,记 m = m1m2mk ，,则(1)的解为,其中，整数Mi（1 i k），满足MiMi 1 (mod mi).,设有同余式组,2019/4/3,23,证明： 由 (Mi, mi) = 1，利用辗转相除法可以求出,Mi与yi ，使得,MiMi yimi = 1，,aiMiMi ai (mod mi)，1 i k。,2019/4/3,24,反之，若 是（1）的解，,又 m1, m2, , mk两两互质，,故方程（1）的解只能为（2）式。,2019/4/3,25,例1 解同余式组,衍数,乘率,2019/4/3,26,例2 韩信点兵有兵一队，若列成五行纵队，则 末行1人；成六行纵队，则末行5人；成七行纵队， 则末行4人；成十一行纵队，则末行10人。求兵数。,余数,衍数,2019/4/3,27,列表如下：,其他略,14623,53851,43301,102101,6731,3,1,1,1,2019/4/3,28,定理2 在定理1的条件下，若式(1)中的a1, a2, , ak 分别通过模m1, m2, , mk的完全剩余系，则式(2)中 的x通过模m1m2mk的完全剩余系。,证明：,则x通过m1m2mk个整数，,且容易它们是两两不同余的。,2019/4/3,29,二、同余方程组解的存在性及解数的判定,引理：设a1，a2是整数，m1，m2是正整数，则 同余 方程组,有解的充要条件是 a1 a2 (mod (m1, m2) (4),若有解，则对模m1, m2是唯一的，即若x1与x2都是 同余方程组(3)的解， 则 x1 x2 (mod m1, m2)。 (5),证 必要性,2019/4/3,30,充分性记(m1, m2)d.,若式(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)的解。,若x1与x2都是方程组(3)的解，,则 x1 x2 (mod m1)，x1 x2 (mod m2)，,从而有 x1 x2 (mod m1, m2)。,2019/4/3,31,定理3 同余方程组(1)有解的充要条件是,ai aj (mod (mi, mj)，1 i, j n。 (6),2019/4/3,32,2019/4/3,33,2019/4/3,34,4.3 高次同余式的解数及解法,2019/4/3,35,一、化合数模为两两互质的模,例1 解同余方程 5x2 6x 49 0 (mod 60)。（1）,解： 60 = 345，同余方程(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)得：,x1(1) 1，x2(1) 1 (mod 3)，,由(3)得：,x1(2) 1，x2(2) 1 (mod 4)，,由(4)得：,x1(3) 1 (mod 5),2019/4/3,36,这样，同余方程(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)。,将a1，a2，a3所有可能的取值代入上式，得到方程(1) 的全部解是,x1 1 (mod 60)，x2 19 (mod 60)， x3 31 (mod 60)，x4 11 (mod 60)。,2019/4/3,37,注：由定理4及算术基本定理，解一般模的同余方程 可以转化为解模为素数幂的同余方程。,定理4 设m = m1m2mk ，其中m1, m2, , mk 是两两,互素的正整数，f(x)是整系数多项式，以T与Ti,（1 i k）分别表示同余方程,f(x) 0 (mod m) （1）,与 f(x) 0 (mod mi) ，1 i k. （2）,的解的个数，,则T = T1T2Tk 。,2019/4/3,38,定理的证明：,因为 a b (mod mi )，1 i k,a b (mod m)，,所以 同余方程(1)等价于同余方程组（2）,f(x) 0 (mod m) （1）,f(x) 0 (mod mi) ，1 i k. （2）,对于每个i（1 i k），设同余方程(2)的全部解是,则同余方程组(3)等价于下面的T1T2Tk个方程组：,其中 通过式(3)中的数值，即通过方程(2)的全部解。,2019/4/3,39,f(x) 0 (mod m) （1）,f(x) 0 (mod mi) ，1 i k. （2）,由孙子定理，对于选定的每一组,同余方程组(4)对模m有唯一解。,而且，由4.2定理2，,当每个 通过(3)式中的值时，,所得到的T1T2Tk个同余方程组(4)的解对于模m都是,两两不同余的。,2019/4/3,40,二、方幂模的解法,若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)的解中去求方程(1)的解。,但对于方程(2)的每个解x1，是否必有方程(1)的解x0 与之对应？若有，如何去确定它？,2019/4/3,41,定理5 设p是素数，n 2，f(x) = anxn a1x a0 是整系数多项式，又设x1是同余方程(2)的一个解。 以f (x)表示f(x)的导函数。,则对于t = 0，1, 2, , p 1，式(3)中的x都是,方程(1)的解。,f(x) 0 (mod p ) (1),f(x) 0 (mod p -1) (2),是方程(1)的解。,2019/4/3,42,证明：如何确定式(3)中的t，,使x1 p 1t满足同余方程(1)，,an(x1+p 1t)n+an 1(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),下面考虑两种情形,2019/4/3,43,(1) 若f (x1) 0 (mod p)，,则关于t的同余方程(5)有唯一解t t0 (mod p)，,即t = t0 pk（kZ），,于是 x x1 p 1t0 (mod p) 是同余方程(1)的解。,(2) 若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)的解。,2019/4/3,44,2019/4/3,45,例2 解同余方程,考虑方程：,则(2)的解可表示为：,代入(2)，得,2019/4/3,46,则(2)的解可表示为：,即(2)的解可表示为：,从而(1)的解可表示为：,2019/4/3,47,推论1,若x a (mod p)是同余方程,2019/4/3,48,推论2,2019/4/3,49,三、一般高次同余式的解法,例3 解同余方程 x3 3x 14 0 (mod 45),解： 原同余方程等价于同余方程组,x3 3x 14 0 (mod 9)， (1) x3 3x 14 0 (mod 5). (2),先求(1)的解：,x3 3x 14 0 (mod 3)的解为,x 2 (mod 3)。,令x = 2 3t并代入方程(1)，得到,(2 3t)3 3(2 3t) 14 0 (mod 9)，,恒成立。,于是方程(1)的解是 x 2，5，8 (mod 9)。,2019/4/3,50,例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， x a2 (mod 5)， a2 = 1，2。,因此，原同余方程的解是下面六个同余方程组的解：,利用孙子定理解这六个方程组.,2019/4/3,51,记 m1 = 9，m2 = 5，m = 45，M1 = 5，M2 = 9，,将a1和a2的不同取值代入，得到所求的解是,x1 102 91 11 (mod 45)，x2 102 92 2 (mod 45)， x3 105 91 41 (mod 45)，x4 105 92 32 (mod 45)， x5 108 91 26 (mod 45)，x6 108 92 17 (mod 45),2019/4/3,52,4.4 质数模的同余式,2019/4/3,53,在上节证明了，对于素数p，模p的同余 方程的求解可以转化为模p的同余方程的求解。 本节要对素数模的同余方程做些初步研究。,以下，设f(x) = anxn a1x a0是整系数多项式，,2019/4/3,54,f(x) = anxn a1x a0 0 (mod p) (1),定理1 同余方程,与一个次数不超过p-1的同余式等价。,证：由带余数除法，存在整系数多项式,由费马定理知，,2019/4/3,55,定理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),f1(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时，定理成立。,2019/4/3,56,如果k 1，在(3)式中，令x = xi（i = 2, 3, , k），,则有 0 f(xi) (xi x1)f1(xi) (mod p) (4),由于x1, x2, , xk对于模p是两两不同余的，,f1(xi) 0 (mod p)，i = 2, , k。 (5),所以，由(4)式得出,由此及归纳法，即可证明定理。,f(x) (x x1)f1(x) (mod p) (3),2019/4/3,57,定理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)的解，,因此，利用定理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)。,2019/4/3,58,定理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 p)。,矛盾！,2019/4/3,59,定理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) pr