初等数论教案6

1、第二章 同余式第一节 同余的基本概念与基本性质教学目的：同余的基本定义与性质.教学重点：同余的性质.教学课时：2课时教学过程1、定义1 给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a与b同余，关于模m，记为a b (mod m)，此时也称b是a对模m的同余.如果整数a与b之差不能被m整除，则称a与b对于模m不同余，或称a与b不同余，模m，记为ab (mod m).2、定理1 下面的三个叙述是等价的：() a b (mod m)；() 存在整数q，使得a = b + qm；() 存在整数q1，q2，使得a = q1m + r，b = q2m + r，0 r 0 a b

2、(mod d)；() a b (mod m)，k 0，kN ak bk (mod mk)；() a b (mod mi )，1 i k a b (mod m1, m2, L, mk)；() a b (mod m) (a, m) = (b, m)；() ac bc (mod m)，(c, m) = 1 a b (mod m).证明：结论()()的证明，留作习题.() 由ac bc (mod m)得到mc(a - b)，再由(c, m) = 1，得到ma - b，即a b (mod m).证毕.例1 设N =是整数N的十进制表示，即N = an10n + an - 110n - 1 + L + a

3、110 + a0 ，则() 3N 3；() 9N 9；() 11N 11；() 13N 13.解：由100 1，101 1，102 1，L (mod 3)及式(2)可知N =(mod 3)，由上式可得到结论().结论()，()用同样方法证明.为了证明结论()，只需利用式(2)及100 1，101 -3，102 -4，103 -1，L (mod 13)和N = .注：一般地，在考虑使N =被m除的余数时，首先是求出正整数k，使得10k -1或1 (mod m)，再将N =写成N =的形式，再利用式(2).例2 求N =被7整除的条件，并说明1123456789能否被7整除.解：100 1，101

4、 3，102 2，103 -1 (mod 7)，因此即 7N 7.由于789 - 456 + 123 - 1 = 455，7455，所以71123456789.例3 说明是否被641整除.解：依次计算同余式22 4，24 16，28 256，216 154，232 -1 (mod 641).因此 0 (mod 641)，即641.注：一般地，计算ab (mod m)常是一件比较繁复的工作. 但是，如果利用Euler定理或Fermat定理就可以适当简化.例4 求(25733 + 46)26被50除的余数.解：利用定理4有(25733 + 46)26 (733 - 4)26 = 7(72)16 -

5、 426 7( -1)16 - 426 = (7 - 4)26 326 = 3(35)5 3(-7)5 = -37(72)2 -21 29 (mod 50)，即所求的余数是29.例5 求n =的个位数.解：我们有71 -3，72 -1，74 1 (mod 10)，因此，若77 r (mod 4)，则n = (mod 10). (3)现在 (-1)7 -1 3 (mod 4)，所以由式(3)得到n = 73 (-3)3 -7 3 (mod 10)，即n的个位数是3.注：一般地，若求对模m的同余，可分以下步骤进行：() 求出整数k，使ak 1 (mod m)；() 求出正整数r，r k，使得 r

6、(mod k)；() a r (mod m).例6 证明：若n是正整数，则1342n + 1 + 3 n + 2 .解：由42n + 1 + 3 n + 2 = 442n + 93 n = 416n + 93 n 43n + 93 n = 133 n 0 (mod 13)得证.例7 证明：若2a，n是正整数，则 1 (mod 2n + 2). (4)解：设a = 2k + 1，当n = 1时，有a2 = (2k + 1)2 = 4k(k + 1) + 1 1 (mod 23)，即式(4)成立.设式(4)对于n = k成立，则有 1 (mod 2k + 2) = 1 + q2k + 2，其中qZ

7、，所以= (1 + q2k + 2)2 = 1 + q 2k + 3 1 (mod 2k + 3)，其中q 是某个整数.这说明式(4)当n = k + 1也成立.由归纳法知式(4)对所有正整数n成立.例8 设p是素数，a是整数，则由a2 1(mod p)可以推出a 1或a -1 (mod p).解：由a2 1 (mod p) pa2 - 1 = (a + 1)(a - 1)，所以必是pa + 1或pa - 1，即a -1 (mod p)或a 1 (mod p).例9 设n的十进制表示是，若792n，求x，y，z.解：因为792 = 8911，故792n 8n，9n及11n.我们有8n 8 z = 6，以及9n 91 + 3 + x + y + 4 + 5 + z = 19 + x + y 9x + y + 1， (5)11n 11z - 5 + 4 - y + x - 3 + 1 = 3 - y + x 113 - y + x. (6)由于0 x, y 9，所以由式(5)与式(6)分别得出x + y