初 等 数 论 辅导课程五 主讲教师：曹洪平

第三章 同 余 1. 同余的概念及基本性质 2. 剩余类及完全剩余系 3. 简化剩余系与欧拉函数 4. 欧拉定理, 费尔马定理及其对循环小数 第三章 同 余 1. 同余的概念及基本性质 2. 剩余类及完全剩余系 3. 简化剩余系与欧拉函数 4. 欧拉定理, 费尔马定理及其对循环小数 的应用

同余的概念及基本性质 掌握同余的定义 掌握同余的基本性质 会用同余的基本性质进行计算 与证明

同余的定义 给定一个正整数m, 把它叫做模. 如果用m 去除任意两个整数a与b所得的余数相同, 我们就说a, b对模m同余, 记做ab(mod m) . 如果余数不同, 我们就说a, b对模m不同 余, 记做a≢b(mod m).

例 由于8除5的余数为5，8除13的余数也是5，因此5与13对模8同余，即513(mod 8)。

同余的判别 定理 整数a，b对模m同余的充要条件是m|a-b。即a=b+mt，t是整数。

证明 设a=mq1+r1, b=mq2+r2, 0r1, r2<m.若ab(mod m), 则r1=r2, 因此 a-b=m(q1-q2), 所以m|a-b. 反之, 若m|a-b, 则m|m(q1-q2)+(r1-r2), 因此m|r1-r2. 但|r1-r2|<m, 故r1=r2, 由定义知ab(mod m).

例 对13与5，因为8|13-5，所以 13≡5(mod 8)。 对15与3，因为8∤15-3，所以 15≢3(mod 8)。

同余的基本性质 1. 同余关系是一个等价关系, 即 (1) aa(mod m); (2) 若ab(mod m), 则ba(mod m); (3) 若ab(mod m), bc(mod m), 则 ac(mod m).

2. 若a1b1(mod m), a2b2(mod m), 则 a1+a2b1+b2(mod m), a1-a2b1-b2(mod m), a1a2b1b2(mod m). 证明 由已知知m|a1-b1, m|a2-b2, 由整除的性质可得m|(a1-b1)+(a2-b2), 所以 m|(a1+a2)-(b1+b2), 从而 a1+a2b1+b2(mod m).

3. 若a=a1d, b=b1d, (d, m)=1, 而 ab(mod m), 则a1b1(mod m). 证明 由ab(mod m)得m|a-b, 但 a-b=d(a1-b1), (m, d)=1, 所以 m|(a1-b1), 于是a1b1(mod m).

4. 若aibi(mod m), i=0, 1, 2, …,n, 且x为整数, 则 anxn+…+a1x+a0bnxn+…+b1x+b0(mod m). 5. 若ab(mod m), k>0, 则akbk(mod mk). 若ab(mod m), d是a, b及m的任一正公因数, 则a/db/d(mod m/d).

同余的应用 定理 一个整数能被3(或9)整除的充要条件是它的十进位数码的和能被3(或9整除). 证明 可假定a为正整数, 将a写成 a=an10n+an-110n-1+…+a0, 因101(mod 3), 所以由同余的性质可得 aan+an-1+…+a0(mod 3), 于是 3|a当且仅当3| an+an-1+…+a0.

例 判断3能否整除5874192. 解 因5+8+7+4+1+9+2=36, 3能整除36, 所以3能整除5874192.

例 求3406的十进位表示中的个位数字。 解 本题实质上就是求10除3406的余数， 即求3406a(mod 10) 中的a，0a9。 因为329-1(mod 10) ，所以 341(mod 10)，因此3404(34)101 1(mod 10) ，所以 3406  340432  -1 9(mod 10)，即3404的 个位数是9。

剩余类及完全剩余系 掌握剩余类及完全剩余系的定义. 能判断几个整数是否构成模m的一个完全剩余系.

定理 若m是一个给定的正整数, 则全部整数可分成m个集合, 记做K0, K1,…,Km-1, 其中Kr(r=0, 1, …, m-1)是由一切形如qm+r (q=0, 1, 2, …)的整数所组成的. 这些集合具有下列性质: (1)每一整数必包含在而且仅包含在上述的一个集合里面. (2)两个整数同在一个集合的充要条件是这两个整数对模m 同余.

证明 (1)由带余数除法知, 对任一整数a有 a=q1m+r, 0r<m. 于是a在Kr内, 再由r的唯一性知a只在Kr内. (2)设a, b是两个整数, 并且都在Kr内, 则 a=q1m+r, b=q2m+r, 0r<m. 故ab(mod m). 反之, 若ab(mod m), 则由同余的定义知a, b同在某一Kr内.

定义 把上面定理中的K0, K1,…,Km-1, 叫做模m的剩余类 定义 把上面定理中的K0, K1,…,Km-1, 叫做模m的剩余类. 若a0, a1,…,am-1是m个整数, 并且其中任何两数都不同在一个剩余类里, 则称 a0, a1,…,am-1为模m的一个完全剩余系. 例 0, 1, 2, …, m-1是模m的一个完全剩余系; 25, 1, -3, 8, 14是模5的一个完全剩余系.

定理 m个整数作成模m的一个完全剩余系的充要条件是这m个数两两对模m不同余。 例 3，10，-1，17，6中任何两个对模5 不同余，故它们构成模5的一个完全剩余 系。

性质 若m1, m2是互质的两个整数, 而x1, x2分别通过模m1, m2的完全剩余系, 则m2x1+m1x2通过模m1m2的完全剩余系.