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

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