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

同余方程 内容： 同余方程概念 解同余方程 解同余方程组 重点 解同余方程 应用 密码学，公钥密码学 基本概念及一次同余方程 同余方程 同余方程 【定义3.1.1】（定义1）设m是一个正整数， 其中是正整数（≠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 【例2】求同余方程≡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） x＝±1时，≡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） x＝±4时，≡15≡0（mod 5）， ≡273＝39·7≡0（mod 7） x＝±5时，≡±5≡0（mod 5）， ≡651＝93·7≡0（mod 7） x＝±6时，≡35≡0（mod 35）， x＝±7时，≡50≡0（mod 5）， ≡±7≡0（mod 7） x＝±8时，≡65≡0（mod 5）， ≡63≡0（mod 7） x＝±9时，≡80≡0（mod 5）， ≡949·7≡0（mod 7） x＝±10时，≡±10≡0（mod 5）， ≡1443·7≡0（mod 7） x＝±11时，≡24·5≡0（mod 5）， ≡2109·7≡0（mod 7） x＝±12时，≡29·5≡0（mod 5）， ≡2983·7≡0（mod 7） x＝±13时， ≡34·5≡0（mod 5）， ≡24·7≡0（mod 7） x＝±14时，≡39·5≡0（mod 5）， ≡±14≡0（mod 7） x＝±15时， ≡±15≡0（mod 5）， ≡32·7≡0（mod 7） x＝±16时， ≡51·5≡0（mod 5）， ≡9399·7≡0（mod 7） x＝±17时， ≡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）因为时