初等数论教案第二章同余式

1、其次章 同余式第一节同余的基本概念与基本性质教学目的：同余的基本定义与性质.教学重点：同余的性质.教学课时： 2 课时教学过程1、定义 1给定正整数 m，假如整数 a 与 b 之差被 m 整除，就称a 与 b 对于模 m 同余，或称 a 与 b 同余，关于模 m，记为ab mod m，此时也称 b 是 a 对模 m 的同余 .假如整数 a 与 b 之差不能被 m 整除，就称 a 与 b 对于模 m 不同余， 或称 a 与 b 不同余，模 m，记为 ab mod m.2、定理 1下面的三个表达是等价的： ab mod m； 存在整数 q，使得 a = bqm； 存在整数 q1， q2，使得 a

2、= q1mr， b = q2mr ，0r < m.证明： 留作习题 .3、定理 2同余具有下面的性质： aa mod m； ab mod mba mod m； ab，bc mod mac mod m.证明： 留作习题 .4、定理 3设 a， b，c，d 是整数，并且ab mod m， cd mod m，1就 acbd mod m； acbd mod m； anbnmod m； fafb mod m ,其中 fx是任意整系数多项式 .证明： 由式1及定义 1 可知mab，mcd，因此macbd，此即结论 ； 由式1及定理 1 可知，存在整数q1 与 q2 使得a = bq1m，c = dq

3、2m，因此ac = bdq1q2mq1dq2bm， 再利用定理 1，推出结论 .证毕.5、定理 4设 ai ，bi（ 0in）以及 x，y 都是整数，并且xy mod m，aibi mod m，0in，就证明： 留作习题 .nia x ii 0nib y ii 0mod m.26、定理 5下面的结论成立： ab mod m， dm，d > 0ab mod d； ab mod m， k > 0， knakbk mod mk； ab mod mi ， 1ikab mod m1, m2, mk ； ab mod ma, m = b, m； acbc mod m，c, m = 1ab mo

4、d m.证明： 结论的证明，留作习题 . 由acbc mod m得到 mcab，再由 c, m = 1，得到 mab，即ab mod m.证毕.例 1设 n = an an1a0是整数 n 的十进制表示，即n = an10nan110n1a110a0 ，就n 3n3|ai ；i0n 9n9|ai ；i0n 11n11|i01) i a；i 13n13a2 a1a0a5a 4 a3.解： 由1001， 1011， 1021，mod 3及式2可知n =i由上式可得到结论 .nai 10i0nai mod 3，i 0结论 ， 用同样方法证明 .为了证明结论 ，只需利用式 2及1001，1013， 1

5、024， 1031，mod 13和n = aaa aaa a100aaa103.n 1n210210543注：一般地，在考虑使n = an1 a n 2a1a 0 被 m 除的余数时，第一是求出正整数 k，使得10k1 或 1 mod m，再将 n = an1an2a1a 0 写成n = ak1ak2a1a0100a2k1a2h2a10kk的形式，再利用式 2.例 2求 n = a n1a n 2a1 a 0 被 7 整除的条件，并说明1123456789能否被 7 整除.解： 1001， 1013， 1022，1031 mod 7，因此nan1an2a1 a 0a2 a1a0100a5 a4

6、 a3103a2 a1a0即7n7a5 a4 a3 a2 a1a0a8 a7 a6a5 a4a3moda8 a7 a67 ，.由于7894561231 = 455，7455，所以 71123456789.5例 3说明 2 21 是否被 641 整除.解： 依次运算同余式224， 2416， 28256，216154，2321 mod 641.因此5即 6412 21 .22150 mod 641，注：一般地，运算 ab mod m常是一件比较繁复的工作.但是，假如利用 euler 定理或 fermat 定理就可以适当简化 .例 4求257334626 被 50 除的余数 .解： 利用定理 4

7、有257334626733426 = 7 72164267 116426 = 7426326 = 3 3553 75 =3 7 7222129 mod 50，即所求的余数是29.7例 5求 n = 77的个位数 .解： 我们有713， 721， 741 mod 10，因此，如77r mod 4，就7n = 7777mod 10.3现在 771713 mod 4，所以由式 3得到7n = 7 7733373 mod 10，即 n 的个位数是 3.注：一般地，如求ca b 对模 m 的同余，可分以下步骤进行： 求出整数 k，使 ak1 mod m；c 求出正整数 r， r < k，使得 b

8、cr mod k； a ba r mod m.例 6证明：如 n 是正整数，就1342n + 13 n + 2 .解： 由42n + 13 n + 2 = 4 42n9 3 n = 4 16n9 3 n4 3n9 3 n = 13 3 n0 mod 13得证.例 7证明：如 2 | a，n 是正整数，就na 21 mod 2n + 2.4解： 设 a = 2k1，当 n = 1 时，有a2 = 2k12 = 4kk111 mod 23，即式4成立.设式 4对于 n = k 成立，就有kka 21 mod 2k + 2a 2 = 1q2k + 2 ，其中 qz ，所以2k 1a= 1q2k +

9、22 = 1q 2k + 31 mod 2k + 3，其中 q 是某个整数 .这说明式 4当 n = k1 也成立 .由归纳法知式 4对全部正整数 n 成立.例 8设 p 是素数， a 是整数，就由 a21mod p可以推出a1 或 a1 mod p.解： 由a21 mod ppa21 = a1a1，所以必是pa1 或 pa1，即 a1 mod p或 a1 mod p.例 9设 n 的十进制表示是 13xy45z ，如 792n，求 x， y，z.解： 由于 792 = 8 9 11，故792n8n，9n 及 11n.我们有8n845zz = 6，以及9n913xy45z = 19xy9xy1，511n11z54yx31 = 3yx113yx. 6由于 0x, y9，所以由式