初等数论教案8

第四节 一次同余式

教学目的：1、掌握同余方程的基本概； 2、掌握一次同余方程基本性质； 3、求解一次同余方程.

教学重点：1、一次同余方程基本性质； 2、求解一次同余方程. 教学课时：4课时 教学过程

本节要介绍同余方程的基本概念及一次同余方程. 在这里，我们总假定m是正整数. 1、定义1 设f(x) = anxn ? ? ? a1x ? a0是整系数多项式，称

f(x) ? 0 (mod m) (1)

是关于未知数x的模m的同余方程，简称为模m的同余方程.

若an??0 (mod m)，则称为n次同余方程.

2、定义2 设x0是整数，当x = x0时式(1)成立，则称x0是同余方程(1)的解. 凡关于模m同余的解，被视为同一个解. 同余方程(1)的解数是指它的关于模m互不同余的所有解的个数，也即在模m的一个完全剩余系中的解的个数.

由定义2，我们知道同余方程(1)的解数不超过m. 3、定理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)

的解.

4、定理2 设(a,m)恰有一个解.

证明：略.

5、定理3 在定理2的条件下，x?1，则同余方程

ax ? b (mod m) (2)

?ba?(m)?1(modm)是同余方程(2)的唯一解.

证明：略.

6、定理4 设a，b是整数，a??0 (mod m). 则同余方程

ax ? b (mod m) (2) 有解的充要条件是(a, m)?b. 若有解，则恰有d = (a, m)个解.

证明：显然，同余方程等价于不定方程

ax ? my = b， (3)

因此，第一个结论可由二元一次不定方程有解条件得出.

若同余方程有解x0，则存在y0，使得x0与y0是方程(3)的解，此时，方程(3)的全部解是

- 1 -

m??x?x0?(a,m)t?，t?Z. (4) ??y?y?at0?(a,m)?由 (4) 式所确定的x都满足同余方程（2）. 记d = (a, m)，以及

t = dq ? r，q?Z，r = 0, 1, 2, ?, d ? 1，

则

x = x0 ? qm ?

mmr?x0?r(mod m)，0 ? r ? d ? 1. dd容易验证，当r = 0, 1, 2, ?, d ? 1时，相应的解

(d?1)mm2m x0，x0?，x0?，?，x0?ddd对于模m是两两不同余的，所以同余方程（2）恰有d个解. 证毕

在定理的证明中，同时给出了解方程（2）的方法，但是，对于具体的方程，常常可采用不同的方法去解.

例1 设(a, m) = 1，且存在整数y，使得a?b ? ym，则

x ?

b?ym(mod m) a是方程(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，则又可继续转化成一个对于更小的模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)的解是

20?2?161x ?= 114 (mod 161).

3例3 设a > 0，且(a, m) = 1，a1是m对模a的最小非负剩余，则同余方程

ma1x ? ?b[](mod m) (7)

a等价于同余方程(2).

解：设x是(2)的解，则由m =a[m]? a1得到 aa1x?(m?a[m])x??ax[m]??b[m](mod m)， aaa - 2 -

即x是同余方程(7)的解.但是由假设条件可知同余方程(2)与(7)都有且只有一个解. 所以这两个同余方程等价.

注：用本例的方法，可以将同余方程(2)转化成未知数的系数更小一些的同余方程，从而易于求解.

例4 解同余方程6x ? 7 (mod 23). 解：由例3，依次得到 6x ? 7 (mod 23) ? 5x ? ?7?3 ? 2 (mod 23)

? 3x ? ?2?4 ? ?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).

解：直接验证即可.

例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).

注：本例使用的是最基本的解同余方程的方法，一般说来，它的计算量太大，不实用.

?3x?5y?1(mod7)例7 解同余方程组 ?. (8)

?2x?3y?2(mod7)解：将(8)的前一式乘以2后一式乘以3再相减得到

19y ? ?4 (mod 7)， 5y ? ?4 (mod 7)，

y ? 2 (mod 7).

再代入(8)的前一式得到 3x ? 10 ? 1 (mod 7)，

x ? 4 (mod 7).

即同余方程组(8)的解是x ? 4，y ? 2 (mod 7).

例8 设a1，a2是整数，m1，m2是正整数，证明：同余方程组

?x?a1(modm1) (9) ?x?a(modm)22?有解的充要条件是 a1 ? a2 (mod (m1, m2)). (10)

若有解，则对模[m1, m2]是唯一的，即若x1与x2都是同余方程组(9)的解，则

x1 ? x2 (mod [m1, m2]). (11)

解：必要性是显然的. 下面证明充分性

若式(10)成立，则同余方程 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).

7、作业 P62：ex22

- 3 -