数论算法讲义 3章（同余方程） .docVIP

同余方程 内容： 同余方程概念 解同余方程 解同余方程组 重点 解同余方程 应用 密码学，公钥密码学 基本概念及一次同余方程 同余方程 同余方程 【定义3.1.1】（定义1）设m是一个正整数，f(x)为n次多项式 其中是正整数（≠0（mod m）），则 (x)≡0（mod m） （1） 叫做模m的（n次）同余式（或模m的（n次）同余方程），n叫做f(x)的次数，记为deg f。 同余方程的解 若整数a使得 (a)≡0（mod m）成立，则a叫做该同余方程的解。 同余方程的解数 若a是同余方程（1）的解，则满足x≡a（mod m）的所有整数都是方程（1）的解。即剩余类 ＝{x｜x∈Z，x≡a（mod m）} 中的每个剩余都是解。故把这些解都看做是相同的，并说剩余类是同余方程(1)的一个解，这个解通常记为 x≡a（mod m） 当均为同余方程(1)的解，且对模m不同余时，就称它们是同余方程(2)的不同的解，所有对模m的两两不同余的解的个数，称为是同余方程（1）的解数，记作。显然 ≤m 同余方程的解法一：穷举法 任意选定模m的一组完全剩余系，并以其中的每个剩余代入方程（1），在这完全剩余系中解的个数就是解数。 【例1】（例1）可以验证，x≡2，4（mod 7）是同余方程 ≡0（mod 7） 的不同的解，故该方程的解数为2。 ＋0＋1＝1≡3 mod 7 ＋1＋1＝3≡3 mod 7 ＋2＋1＝35≡0 mod 7 ＋3＋1＝247≡2 mod 7 ＋4＋1＝1029≡0 mod 7 ＋5＋1＝3131≡2 mod 7 ＋6＋1＝7783≡6 mod 7 ≡0（mod 15）的解。 （解）取模15的绝对最小完全剩余系：－7，－6，…，－1，0，1，2，…，7，直接计算知x＝－6，3是解。所以，该同余方程的解是 x≡－6，3（mod 15） 且解数＝2。 【例3】求同余方程≡0（mod 15）的解 （解）同样直接计算知是解。所以它的解是 ， 解数为4。 【例4】求解同余方程。 （解）经直接计算知，本方程无解，即解数为0。 说明：当的系数都是模m的倍数时，显见，任意的整数值x都是同余方程（1）的解，这样的同余方程 （1）的解数为m。但这并不是同余方程（1）的解数为m的必要条件。 例如 21＋35x＋14≡0（mod 7） 显然，上方程等价于方程 0≡0（mod 7） 【例5】由Fermat－Euler 的解数为5；同余方程 的解数为7。 一般地，对素数p，同余方程 的解数为p。 【例6】同余方程 即 的解数为35。 （证）记，，，，由同余的性质， 存在i，j使得成立（因5、7都是素数） 直接计算：为奇函数，其余为偶函数 x＝0≡0（mod 5）≡0（mod 7）≡0（mod 5）≡0（mod 7）≡0（mod 35）＝＝ x＝±2时，≡5≡0（mod 5）≡21≡0（mod 7）＝，＝ x＝±3时，≡10≡0（mod 5）≡91≡0（mod 7）≡15≡0（mod 5）≡273＝39·7≡0（mod 7）≡±5≡0（mod 5）≡651＝93·7≡0（mod 7）≡35≡0（mod 35）≡50≡0（mod 5）≡±7≡0（mod 7）≡65≡0（mod 5）≡63≡0（mod 7）≡80≡0（mod 5）≡949·7≡0（mod 7）≡±10≡0（mod 5）≡1443·7≡0（mod 7）≡24·5≡0（mod 5）≡2109·7≡0（mod 7）≡29·5≡0（mod 5）≡2983·7≡0（mod 7） ≡34·5≡0（mod 5）≡24·7≡0（mod 7）≡39·5≡0（mod 5）≡±14≡0（mod 7） ≡±15≡0（mod 5）≡32·7≡0（mod 7） ≡51·5≡0（mod 5）≡9399·7≡0（mod 7） ≡58·5≡0（mod 5）≡11973·7≡0（mod 7）中x的幂都是奇数，故当x为其解释时，－x也是其解。 同余方程的性质 【定理3.1.1】（i）若两个多项式f(x)≡g(x)（mod m），则同余方程（1）的解和解数与同余方程g(x)≡0（mod m）相同，此时称两个方程同解。 （ii）若，则同余方程（1）的解和解数与同余方程相同。特别地，当时，取a≡（mod m），则多项式的首项系数为 （证）（i）显然。 （ii）因为时，有 (x)≡0（mod m） a(x)≡0（mod m） （当(a,m)＝1时，b≡c（mod m）ab≡ac（mod m）） 【例6】证明同余方程（mod 15）与方程（mod 15）同解。 （证）首先≡（mod 15），故方程（mod 15）与（mod 15）同解。 其次，由于≡4（mod 15），所以，原方程又可以化简为 ()≡