初等数论教案第四节一次同余式

1、第四节一次同余式教学目的： 1、把握同余方程的基本概； 2、把握一次同余方程基本性质；3、求解一次同余方程 .教学重点： 1、一次同余方程基本性质；2、求解一次同余方程 .教学课时： 4 课时教学过程本节要介绍同余方程的基本概念及一次同余方程.在这里，我们总假定 m 是正整数 .1、定义 1设 fx = anxna1xa0 是整系数多项式，称fx0 mod m1是关于未知数 x 的模 m 的同余方程，简称为模m 的同余方程 .如 an0 mod m，就称为 n 次同余方程 .2、定义 2 设 x0 是整数，当 x = x0 时式 1成立，就称 x0 是同余方程1的解. 凡关于模 m 同余的解，

2、被视为同一个解 . 同余方程 1的解数是指它的关于模 m 互不同余的全部解的个数，也即在模 m 的一个完全剩余系中的解的个数 .由定义 2，我们知道同余方程 1的解数不超过 m.3、定理 1下面的结论成立： 设 bx是整系数多项式，就同余方程1与fxbxbx mod m等价； 设 b 是整数， b, m = 1，就同余方程 1与bfx0 mod m等价； 设 m 是素数， fx = gxhx，gx与 hx都是整系数多项式，又设 x0 是同余方程 1的解，就 x0 必是同余方程gx0 mod m或 hx0 mod m的解.4、定理 2设 a, m1 ，就同余方程axb mod m2恰有一个解 .

3、证明： 略.5、定理 3在定理 2 的条件下， xba m1 mod m同余方程 2的唯独解 .证明： 略.6、定理 4设 a， b 是整数， a0 mod m.就同余方程axb mod m2有解的充要条件是 a, mb.如有解，就恰有d = a, m个解.证明： 明显，同余方程等价于不定方程axmy = b，3因此，第一个结论可由二元一次不定方程有解条件得出.如同余方程有解x0，就存在 y0，使得 x0 与 y0 是方程 3的解，此时，方程3的全部解是x x0y y0mt a, mata, m， tz .4由 4式所确定的 x 都满意同余方程（ 2） .记 d = a, m，以及t = dq

4、r ，qz ，r = 0, 1, 2, d1，就0x = x0qmm rxdm r mod m，0rd1.d简单验证，当 r = 0, 1, 2, d1 时，相应的解x0， x 0m ， x0 d2 m ， d， x0d1 m d对于模 m 是两两不同余的，所以同余方程（2）恰有 d 个解.证毕在定理的证明中，同时给出明白方程（2）的方法，但是，对于具体的方程，经常可采纳不同的方法去解.例 1设a, m = 1，且存在整数y，使得 abym，就是方程 2的解.xbym mod ma解： 直接验算，有 axbymb mod m.注：例 1 说明，求方程 2的解可以转化为求方程myb mod a5

5、的解，这有两个便利之处：第一，将一个对于大模m 的同余方程转化为一个对于小模a 的同余方程， 因此有可能通过对模a 的完全剩余系进行逐个验证，以求出方程5和2的解；其次，设mr mod a， r < a，就又可连续转化成一个对于更小的模r 的同余方程 .例 2解同余方程325x20 mod 1616解： 同余方程 6即是3x20 mod 161.解同余方程161y20 mod 3， 2y1 mod 3，得到 y2 mod 3，因此方程 6的解是202161x3= 114 mod 161.例 3设 a > 0，且a, m = 1，a1 是 m 对模 a 的最小非负剩余，就同余方程等价

6、于同余方程 2.a1xbm mod m7a解： 设 x 是2的解，就由 m = a m aa1 得到a1 xma m x aax m ab m mod m，a即 x 是同余方程 7的解.但是由假设条件可知同余方程2与7都有且只有一个解 .所以这两个同余方程等价.注：用本例的方法，可以将同余方程2转化成未知数的系数更小 一些的同余方程，从而易于求解.例 4解同余方程 6x7 mod 23.解： 由例 3，依次得到6x7 mod 235x7 32 mod 233x2 48 mod 232x8710 mod 23x5 mod 23.例 5设a, m = 1，并且有整数> 0 使得a1 mod

7、m，就同余方程 2的解是xba1 mod m.解： 直接验证即可 .例 6解同余方程81x324x25x230 mod 7.解： 原同余方程即是3x33x22x20 mod 7.用 x = 0， 1， 2， 3 逐个代入验证，得到它的解是x11， x22，x32 mod 7.注：本例使用的是最基本的解同余方程的方法，一般说来，它的运算量太大，不有用 .例 7解同余方程组3x5 y2 x3 y1mod 72mod 7.8解： 将8的前一式乘以 2 后一式乘以 3 再相减得到19y4 mod 7，5y4 mod 7， y2 mod 7.再代入 8的前一式得到3x101 mod 7，x4 mod 7.即同余方程组 8的解是 x4， y2 mod 7.例 8设 a1， a2 是整数， m1，m2 是正整数，证明：同余方程组xa1 modxa 2 modm1 m2 9有解的充要条件是a1 a2 mod m1, m2.10 如有解，就对模 m1, m2 是唯独的，即如 x1 与 x2 都是同余方程组 9的解，就x1x2 mod m1, m2.11解： 必要性是明显的 .下面证明充分性如式 10成立，就同余方程m2ya1a2 mod m1有解 yy0 mod m1，记 x0 = a2m2y0，就x0a2 mod