初等数论$4同余式.ppt

第四章 同 余 式;一、基本概念;定义2 设a是整数，当 ;二、等价同余式;三、一次同余方程的基本解法;若同余方程(2)有解x0，则存在y0，使得x0与y0是 方程(3)的解，;容易验证，当r = 0, 1, 2, ?, d ? 1时，相应的解;例1 解同余式 ;四、其他解法;例2 解同余方程 325x ? 20 (mod 161) ;补充说明;例1 解同余式 ;四、其他解法;例3 解同余方程6x ? 7 (mod 23)。;定理5 ;五、简单同余方程组〔模相同〕的解法;§4.2 孙子定理 ;问题：今有物不知其数，三三数之剩二，五五数之 剩三，七七数之剩二，问物几何。〔《孙子算经》〕;问题：今有物不知其数，三三数之剩二，五五数之 剩三，七七数之剩二，问物几何。〔《孙子算经》〕;问题1：今有物不知其数，三三数之剩二，五五数之 剩二，七七数之剩二，问物几何。;问题：今有物不知其数，三三数之剩二，五五数之 剩三，七七数之剩二，问物几何。〔《孙子算经》〕;一、同余式组的解法——中国剩余定理;证明： 由 (Mi, mi) = 1，利用辗转相除法可以求出;反之，若 是（1）的解， ;例1 解同余式组 ;例2 〔韩信点兵〕有兵一队，若列成五行纵队，则 末行1人；成六行纵队，则末行5人；成七行纵队， 则末行4人；成十一行纵队，则末行10人。求兵数。;列表如下：;定理2 在定理1的条件下，若式(1)中的a1, a2, ?, ak 分别通过模m1, m2, ?, mk的完全剩余系，则式(2)中 的x通过模m1m2?mk的完全剩余系。;二、同余方程组解的存在性及解数的判定;〔充分性〕记(m1, m2)＝d.;定理3 同余方程组(1)有解的充要条件是;Date;Date;§4.3 高次同余式的解数及解法 ;一、化合数模为两两互质的模;这样，同余方程(1)的解x可由下面的方程组决定：;注：由定理4及算术基本定理，解一般模的同余方程 可以转化为解模为素数幂的同余方程。;定理的证明：;f(x) ? 0 (mod m) （1）;二、方幂模的解法;定理5 设p是素数，n ? 2，f(x) = anxn ? ? ? a1x ? a0 是整系数多项式，又设x1是同余方程(2)的一个解。 以f ?(x)表示f(x)的导函数。;证明：如何确定式(3)中的t， ;(1) 若f ?(x1) 0 (mod p)， ;Date;例2 解同余方程 ;则(2)的解可表示为：;推论1;推论2;三、一般高次同余式??解法;例3 解同余方程 x3 ? 3x ? 14 ? 0 (mod 45) ;记 m1 = 9，m2 = 5，m = 45，M1 = 5，M2 = 9， ;§4.4 质数模的同余式 ; 在上节证明了，对于素数p，模p?的同余 方程的求解可以转化为模p的同余方程的求解。 本节要对素数模的同余方程做些初步研究。;f(x) = anxn ? ? ? a1x ? a0 ? 0 (mod p) (1);定理2 设k ? n，若同余方程(1)有k个不同的解;如果k 1，在(3)式中，令x = xi（i = 2, 3, ?, k）， ;定理3 ;定理4 同余方程(1)的解数? n。;定理5 ;从而， r1(xi) ? 0 (mod p)，1 ? i ? n， ;〔充分性〕 由Fermat定理，对于任何整数x，有 ;例1 判定同余方程2x3 ? 3x ? 1 ? 0 (mod 7)是否有三个解。;例2 解同余方程 3x14 ? 4x10 ? 6x ? 18 ? 0 (mod 5)。