下载文档原格式
第 3 章 同余方程（一） 内容：● 同余方程概念● 解同余方程● 解同余方程组（二） 重点● 解同余方程（三） 应用● 密码学，公钥密码学3.1 基本概念及一次同余方程(一) 同余方程（1） 同余方程【定义3.1.1】（定义1）设m 是一个正整数，f(x)为n 次多项式()0111a x a x a x a x f n n n n ++++=--其中i a 是正整数（n a ≠0（mod m ）），则f (x)≡0（mod m ） （1）叫做模m 的（n 次）同余式（或模m 的（n 次）同余方程），n 叫做f(x)的次数，记为deg f 。
（2） 同余方程的解若整数a 使得 f (a)≡0（mod m ）成立，则a 叫做该同余方程的解。
（3） 同余方程的解数若a 是同余方程（1）的解，则满足x ≡a （mod m ）的所有整数都是方程（1）的解。
即剩余类a C ＝{x ｜x ∈Z ，x ≡a （mod m ）}中的每个剩余都是解。
故把这些解都看做是相同的，并说剩余类a C 是同余方程(1)的一个解，这个解通常记为x ≡a （mod m ）当21,c c 均为同余方程(1)的解，且对模m 不同余时，就称它们是同余方程(2)的不同的解，所有对模m 的两两不同余的解的个数，称为是同余方程（1）的解数，记作()m f T ;。
显然()m f T ;≢m（4） 同余方程的解法一：穷举法任意选定模m 的一组完全剩余系，并以其中的每个剩余代入方程（1），在这完全剩余系中解的个数就是解数()m f T ;。
【例1】（例1）可以验证，x ≡2，4（mod 7）是同余方程15++x x ≡0（mod 7）的不同的解，故该方程的解数为2。
50＋0＋1＝1≡3 mod 751＋1＋1＝3≡3 mod 752＋2＋1＝35≡0 mod 753＋3＋1＝247≡2 mod 754＋4＋1＝1029≡0 mod 755＋5＋1＝3131≡2 mod 756＋6＋1＝7783≡6 mod 7【例2】求同余方程122742-+x x ≡0（mod 15）的解。
第六讲 同余方程板块1 一次同余方程含有未知数的同余式叫做同余方程。
比如下面这个就是最简单的同余方程：一次同余方程。
ax ≡ b (mod m ) 其中系数是整数（本讲默认这一点）我们先研究这个方程什么时候有解。
ax ≡ b (mod m )那么存在整数y 满足my=ax-b也就是说ax-my=b 有整数解。
由前面讲的不定方程有解条件，(a,m )|b所以ax ≡ b (mod m ) 有整数解的条件是(a,m )|b【例】1631(mod3500)x ≡【解析】根据解的存在性，方程的解存在且唯一。
3500=125×7×4，所以我们只要知道x 在模125,4,7下的余数就能知道x 属于3500的哪个同余类。
1631(mod 4)31(mod 4)3(mod 4)1631(mod 7)21(mod 7)4(mod 7)x x x x x x ≡≡≡≡≡≡为了求解1631(mod125)x ≡我们先来求解1631(mod 25)x ≡131(mod 25)2(mod 25)x x ≡≡ 所以x 在模125之下余数可能是2,27,52,77,102逐个实验得到102(mod125)x ≡我们先满足条件3(mod 4)x ≡，102(mod125)x ≡得到227(mod500)x ≡在227,727 ,1227,1727,2227,2727,3227当中，满足4(mod7)x ≡的是2727。
. 所以原同余方程的解是2727(mod3500)x ≡上例要点是1. 模的分解。
只要是一次同余方程就可以尝试此方法。
2. 质数模的一次同余方程没有一般方法。
3. 如果模是质数的幂，可以对模进行降次。
下面再看一个同余方程组的例子。
【例】解同余式31(mod5)7101(mod5)a b a b +≡⎧⎨-≡⎩【解析】由于两个式子的模是相同的，第一个式子乘10与第二个相加，得到 3711(mod 5)3(mod 5)a a ≡≡带入第一个式子得到2(mod5)b ≡【总结】1 同余和整除是等价的。
