《初等数论三夏子厚课件》由会员分享，可在线阅读，更多相关《初等数论三夏子厚课件（82页珍藏版）》请在金锄头文库上搜索。
1、初等数论(三) Number Theory （Chap3）,信阳职业技术学院 夏子厚,第三章 同余性质,教学目的和要求 （1）熟练掌握同余的基本概念及性质。 （2）熟练掌握剩余类、完全剩余系、简化剩余系和欧拉函数的概念及其性质。 （3）熟练掌握欧拉定理、费马定理和解某些同余问题。 本章是初等数论的核心内容，是学生应必须掌握的基础知识。,第一节 同余的概念及其基本性质,定义1 给定正整数m，如果用m去除任意的两个整数a与b所得的余数相同，则称a与b对于模m同余。记为 a b (mod m)， 如果余数不同，则称a与b对于模m不同余。记为a b (mod m)。,第一节 同余的概念及其基本性质,定
2、理1 下面的三个叙述是等价的： () a b (mod m)； ()存在整数q，使得a = b qm； ()存在整数q1，q2，使得 a = q1m r， b = q2m r，0 r m。,第一节 同余的概念及其基本性质,证明：如果()成立，ma b，a b = mq，a = b mq，知()成立； 如果()成立，写a = q1m r1, b = q2m r2， 0 r1, r2 m 1，则q1m r1 = q2mr2mq，由此得r1 = r2，知()成立； 如果()成立，a = q1m r, b = q2m r， 0 r m 1，则a b = m(q1 q2)， ma b，知()成立。,第一
3、节 同余的概念及其基本性质,由同余的定义容易得到： 定理2 同余具有下面的性质： (1) a a (mod m)； (2) a b (mod m) b a (mod m)； (3) a b，b c (mod m) a c (mod m)。,第一节 同余的概念及其基本性质,定理3 设a，b，c，d是整数，并且 a b (mod m)，c d (mod m)，则 (4) a c b d (mod m)； (5) ac bd (mod m)。 证明： (4) 由定义1可知 ma b，mc d， 因此 m(a c) (b d)， 此即结论(4)；,第一节 同余的概念及其基本性质,（5）由定理1可知，存
4、在整数q1与q2使得a = b q1m，c = d q2m， 因此 ac = bd (q1q2m q1d q2b)m， 再利用定理1，推出结论(5)。,第一节 同余的概念及其基本性质,推论3.1 若a b c (mod m)， 则a cb (mod m) 推论3.2 若a b (mod m)， 则an b n(mod m),第一节 同余的概念及其基本性质,推论3.3 设ai，bi（0 i n）以及x，y都是整数，并且 x y (mod m)，ai bi (mod m)，0 i n， 则 (mod m)。,第一节 同余的概念及其基本性质,定理4 下面的结论成立： (6) ac bc (mod m
5、)，(c, m) = 1 a b (mod m)； a b (mod m)，k 0，kN ak bk (mod mk)； a b (mod mi )，1 i k a b (mod m1, m2, , mk)； (9) a b (mod m)，dm，d 0 a b (mod d)； (10) a b (mod m) (a, m) = (b, m),第一节 同余的概念及其基本性质,例1 设N =是整数N的十进制表示，即 N = an10n an 110n 1 a110 a0 ， 则 (1) 3N 3 (2) 9N 9 (3) 7、11、13N 7、11、13 ,第一节 同余的概念及其基本性质,证
6、由100 1，101 1，102 1， (mod 3) 及推论3.3可知 N = (mod 3)， 由上式可得到结论(1)。同理可得（2）。 为了证明结论(3)，把N写成 N = 同理可得（3）。,第一节 同余的概念及其基本性质,例2 求N = 被7整除的条件，并说明1123456789能否被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
7、641)， 即641,第一节 同余的概念及其基本性质,例4 求(25733 46)26被50除的余数。 解 利用定理4有 (25733 46)26 (733 4)26 = 7(72)16 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 = 74m+r (74)m7r 7r (mod 10)。 现在 77 (1)7 1 3
8、 (mod 4)，所以 n = 73 (3)3 7 3 (mod 10)， 即n的个位数是3。,第一节 同余的概念及其基本性质,注：一般地，若求 对模m的同余，可分以下步骤进行： () 求出整数k，使ak 1 (mod m)； () 求出正整数r，r k，使得 bc r (mod k)； () a r (mod m)。,第一节 同余的概念及其基本性质,例6 证明：若2 a，n是正整数，则 1 (mod 2n + 2)。 (1) 证明： 设a = 2m 1，当n = 1时，有 a2 = (2m 1)2 = 4m(m 1) 1 1 (mod 23) 即式(1)成立。,第一节 同余的概念及其基本性质
9、,假设式(1)对于n = k成立，则有 1 (mod 2k + 2) = 1 q2k + 2， 其中qZ，所以 = (1 q2k + 2)2 = 1 q 2k + 3 1 (mod 2k + 3) 其中q 是某个整数。这说明式(1)当n = k 1也成立 由归纳法知式(1)对所有正整数n成立。,第一节 同余的概念及其基本性质,思考与练习3.1 1、证明定理4。 2、设n的十进制表示是 ， 若792n，求x，y，z。 3、已知ab-1(mod 24)，证明：24 a+b。 4、求 的个位数字，这里共有k （k1）个47。,第二节 完全剩余系,由带余数除法我们知道，对于给定的正整数m，可以将所有的
10、整数按照被m除的余数分成m类。本节将对此作进一步的研究。,第二节 完全剩余系,如：模 5的五个剩余类是 K0(5) = , 10, 5, 0 , 5, 10, K1(5) = , 9 , 4 , 1 , 6 , 11, K2(5) = , 8 , 3 , 2 , 7 , 12, K3(5) = , 7 , 2 , 3 , 8 , 13, K4(5) = , 6 , 1 , 4 , 9 , 14, ,第二节 完全剩余系,K0(5) = nn 0 (mod 5)，nZ K1(5) = nn 1 (mod 5)，nZ K2(5) = nn 2(mod 5)，nZ K3(5) = nn 3 (mod
11、5)，nZ K4(5) = nn 4(mod 5)，nZ ,第二节 完全剩余系,显然，每个整数必定属于且仅属于某一个Ki(5)（0 i 4），而且，属于同一剩余类的任何两个整数对模5是同余的，不同剩余类中的任何两个整数对模5是不同余的。,于是我们可以容易得到如下结论： 定理1 设m是正整数，则全部整数可分成m个集合，记作K0,K1,.,Km-1 ,这些集合具有下列性质： （1）每个整数必定属于且仅属于上述的一个集合里； （2）两个整数在同一集合的充要条件是这两个整数对模m同余。,第二节 完全剩余系,第二节 完全剩余系,定义1 给定正整数m，对于每个整数i，0 i m 1，称集合 Ki(m) =
12、 nn i (mod m)，nZ 是模m的一个剩余类。,第二节 完全剩余系,定义2 设m是正整数，从模m的每一个剩余类中任取一个数xi（0 i m 1），称集合x0, x1, ,xm 1是模m的一个完全剩余系（或简称为完全系）。,第二节 完全剩余系,推论1.1 整数集合A是模m的完全剩余系的充要条件是 (1) A中含有m个整数； (2) A中任何两个整数对模m不同余。,第二节 完全剩余系,通常称() 0, 1, 2, , m 1是模m的最小非负完全剩余系； () 或 是模m的绝对最小完全剩余系。,第二节 完全剩余系,如集合0, 6, 7, 13, 24是模5的一个完全剩余系， 集合0, 1,
13、2, 3, 4是模5的最小非负完全剩余系。 集合-2, -1, 0, -1, -2是模5的绝对最小完全剩余系。,第二节 完全剩余系,注：若x1, x2, , xm是模m的一个完全剩余系，则m是奇数时， x1+ x2+ + xm 0（mod m）； m是偶数时， x1+ x2+ + xm m/2（mod m）。,第二节 完全剩余系,定理2 设m 1，a，b是整数，(a, m) = 1，若x通过模m的一个完全剩余系，则ax b 也通过模m的一个完全剩余系。即若x1, x2, , xm是模m的一个完全剩余系，则ax1 b, ax2 b, , axm b也是模m的一个完全剩余系。,第二节 完全剩余系,
14、证明 由定理1，只需证明：若xi xj，则 axi baxj b (mod m)。 (1) 事实上，若axi b axj b (mod m)， 则axi axj (mod m)， xi xj (mod m)， 因此xi = xj。这与题设相矛盾，故式(1)必定成立。,第二节 完全剩余系,推论2.1 若(a, m) = d1，若x通过模 的一个完全剩余系，则 x b 也通过模 的一个完全剩余系。 留做练习。,第二节 完全剩余系,定理3 若m1, m2N，(m1, m2) = 1，则当x1与x2分别通过模m1与模m2的完全剩余系时，m2x1 m1x2通过模m1m2的完全剩余系。,第二节 完全剩余系,证明：由题设知x1, x2分别通过m1, m2个整数，因此， m2 x1 m1 x2通过了m1m2整数。由定理1推论知，只须
