《同余方程的概念》课件1.pptx

1、3.1 同余方程的概念,人教B版数学选修4-6初等数论初步,同余方程的概念,本节要介绍同余方程的基本概念及一次同余方程。 在本章中，总假定m是正整数。,定义1 设f(x) = anxn a1x a0是整系数多项式，称 f(x) 0 (mod m) (1) 是关于未知数x的模m的同余方程，简称为模m的同余方程。,若an 0 (mod m)，则称为n次同余方程。,定义2 设x0是整数, 当x = x0时式(1)成立, 则称x0是同余方程(1)的解. 凡对于模m同余的解, 被视为同一个解. 同余方程(1)的解数是指它的关于模m互不同余的所有解的个数, 也即在模m的一个完全剩余系中的解的个数.,由定义

2、2，同余方程(1)的解数不超过m。,定理1 下面的结论成立： () 设b(x)是整系数多项式,则同余方程(1)与 f(x) b(x) b(x) (mod m) 等价; () 设b是整数, (b, m) = 1, 则同余方程(1)与 bf(x) 0 (mod m) 等价;,() 设m是素数, f(x) = g(x)h(x), g(x)与h(x)都是整系数多项式, 又设x0是同余方程(1)的解,则x0必是同余方程 g(x) 0 (mod m) 或 h(x) 0 (mod m) 的解.,证明 留做习题。,下面，我们来研究一次同余方程的解。,定理2 设a，b是整数, a 0 (mod m). 则同余方

3、程 ax b (mod m) (2) 有解的充要条件是(a, m)b。若有解，则恰有d = (a, m)个解。,证明 显然，同余方程(2)等价于不定方程 ax my = b， (3),因此，第一个结论可由第四章第一节定理1得出。,若同余方程(2)有解x0，则存在y0，使得x0与y0是方程(3)的解，此时，方程(3)的全部解是,由式(4)所确定的x都满足方程(2)。记d = (a, m)，以及 t = dq r，qZ，r = 0, 1, 2, , d 1， 则 x = x0 qm (mod m)，0 r d 1。,容易验证，当r = 0, 1, 2, , d 1时，相应的解,对于模m是两两不同余

4、的，所以同余方程(2)恰有d个解。证毕。,在定理的证明中，同时给出了解方程(2)的方法，但是，对于具体的方程(2)，常常可采用不同的方法去解。,例1 设(a, m)=1, 又设存在整数y, 使得ab ym，则 是方程(2)的解。,证明 直接验算，有 ax b ym b (mod m)。,注: 例1说明, 求方程(2)的解可以转化为求方程 my b (mod a) (5) 的解, 这有两个便利之处：第一 , 将一个对于大模m的同余方程转化为一个对于小模a的同余方程, 因此有可能通过对模a的完全剩余系进行逐个验证, 以求出方程(5)和(2)的解; 第二, 设m r (mod a), r a, 则又

5、可继续转化成一个对于更小的模r的同余方程.,例2 解同余方程 325x 20 (mod 161) (6),解 同余方程(6)即是 3x 20 (mod 161)。 解同余方程 161y 20 (mod 3)， 2y 1 (mod 3)， 得到y 2 (mod 3)，因此方程(6)的解是 x = 114 (mod 161)。,例3 设a 0，且(a, m) = 1，a1是m对模a的最小非负剩余，则同余方程 a1x b (mod m) (7) 等价于同余方程(2)。,解 设x是(2)的解，则由m = a1得到,(mod m)， 即x是同余方程(7)的解。,但是由假设条件可知同余方程(2)与(7)都

6、有且只有一个解.所以这两个同余方程等价.,注：用本例的方法，可以将同余方程(2)转化成未知数的系数更小一些的同余方程，从而易于求解。,例4 解同余方程6x 7 (mod 23)。,解 由例3，依次得到 6x 7 (mod 23) 5x 73 2 (mod 23) 3x 24 8 (mod 23) 2x 8(7) 10 (mod 23) x 5 (mod 23)。,例5 设(a, m) = 1，并且有整数 0使得 a 1 (mod m)， 则同余方程(2)的解是 x ba 1 (mod m)。,解 直接验证即可。,注: 由例5及Euler定理可知，若(a, m) = 1，则 x ba(m) 1

7、(mod m) 总是同余方程(2)的解。,例6 解同余方程 81x3 24x2 5x 23 0 (mod 7)。,解 原同余方程即是 3x3 3x2 2x 2 0 (mod 7)。 用x = 0，1，2，3逐个代入验证，得到它的解是 x1 1，x2 2，x3 2 (mod 7)。,注: 本例使用的是最基本的解同余方程的方法, 一般说来, 它的计算量太大, 不实用.,例7 解同余方程组 . (8),解 将(8)的前一式乘以2后一式乘以3再相减得到 19y 4 (mod 7)， 5y 4 (mod 7)， y 2 (mod 7)。,再代入(8)的前一式得到 3x 10 1 (mod 7)， x 4

8、 (mod 7)。 即同余方程组(8)的解是: x 4，y 2 (mod 7).,例8 设a1，a2是整数，m1，m2是正整数，证明：同余方程组 (9) 有解的充要条件是 a1 a2 (mod (m1, m2)。 (10) 若有解，则对模m1, m2是唯一的，即若x1与x2都是同余方程组(9)的解，则 x1 x2 (mod m1, m2)。 (11),证明 必要性是显然的。下面证明充分性。 若式(10)成立，由定理2，同余方程 m2y a1 a2 (mod m1) 有解y y0 (mod m1)，记x0 = a2 m2y0，则 x0 a2 (mod m2) 并且 x0 = a2 m2y0 a2 a1 a2 a1 (mod m1)， 因此x0是同余方程组的解。,若x1与x2都是方程组(9)的解，则 x1 x2 (mod m1)，x1 x2 (mod m2)， 由同余的基本性质，得到式(11)。,习 题,1. 证明定理1。 2. 解同余方程： () 31x 5 (mod 17)； () 3215x 160 (mod 235)。 3. 解同余方程组： 。,习 题,4. 设p是素数，0 a p，证明： (mod p)。 是同余方程ax b (mod p)的