同余 数论基础.pptVIP

3.1 同余的概念和基本性质 3.1 同余的概念和基本性质 定理 1 整数a,b对模m同余 iff m|(a-b), 即: a?b(mod m), iff m|(a-b). 证明 设a?b(mod m), 则a=mq1+r, b=mq2+r, 0≤rm. 故(a-b)=m(q1-q2), m|(a-b). 反之, 设a=mq1+r1, b=mq2+r2, 0r1≤m, 0r2≤m, m|(a-b).于是, m|(a-b)=m(ql-q2)+(rl-r2), 故: m|(r1-r2). 又因|r1-r2|m, 得r1=r2. 3.1 同余的概念和基本性质 同余与等号类似的性质： 定理2 若a?b(mod m), c?d(mod m), 则: ① ax+cy ? bx+dy(mod m), 其中x和y为任给整数. ②若a+b?c(mod m),则a?c-b(mod m) ③ ac ? bd(mod m). ④ an ? bn(mod m), 其中 n＞0. ⑤ f(a) ?f(b)(mod m), 其中f(x)为任给的一个整系数多项式. 3.1 同余的概念和基本性质 与等号不相同的性质 定理3 ①若a?b(mod m), k0,则ak?bk(mod mk) 若a?b(mod m), d是a,b,m的任一公因数,则 a/d?b/d(mod m/d) ②若a?b(mod mi), i=1,2, …,k,则 a?b(mod [m1, m2, …, mk]) ③若a?b(mod m), d|m,d0,则a?b(mod d) ④若a?b(mod m), 则(a,m)=(b,m),因此若d能整除m及a,b,二 数之一，则d必能整除a,b中的另一个 提示：a=b+mt 3.1 同余的概念和基本性质 例： 1、正整数模m在什么条件下满足下列同余式？ 1+2+…(m-1)+m ?0(mod m) 2、证明641|(225 +1) 3、对那些模m，同余式32?11(mod m)及1000?-1(mod m) 同时成立？ 4、证明： 70！?61！(mod 71), 3.1 同余的概念和基本性质 1、检查因数的一些方法 定理 正整数a能被9(3)整除 iff 9(3)整除a的十进制表示各数 字的和． 定理 正整数 能被7(11或13)整除 iff 7(11或13)整除 3.1 同余的概念和基本性质 例： 判断下列数值能否被3整除？ 5874192 435693 例判断下列数值能否被13整除？ 637 693 3.1 同余的概念和基本性质 定理 (弃九法) 若ab=c, 其中a0, b0, 并且, 则: 若 , 则可判断乘积ab=c是错误的, 这即是弃九法之原则． 例：a=28997,b=39495 若计算得ab=1145236415,正确否？ 3.1 同余的概念和基本性质 3.1 同余的概念和基本性质 3.2 剩余类和完全剩余系 3.2 剩余类和完全剩余系 3.2 剩余类和完全剩余系 3.2 剩余类和完全剩余系 3.2 剩余类和完全剩余系 例： 1、求模1990的完全剩余系 2、利用模5,6的完全剩余系去 构造模30的完全剩余系 3、证明 4、思考剩余系和剩余类的概念及性质？ 3.3 简化剩余系和欧拉函数 在模m的完全剩余系中，与m互素的整数所成的集合 有一些特殊的性质，我们要在这一节中对它们做些研究。 定义1 设R是模m的一个剩余类，若有a?R，使得(a, m) = 1，则称R是模m的一个简化剩余类。 显然，若R是模的简化剩余类，则R中的每个整数都 与m互素。例如，模4的简化剩余类有两个： R1(4) = { ?, ?7 , ?3, 1 , 5 , 9 , ? }， R3(4) = { ?, ?5 , ?1 , 3 , 7 , 11 , ? } 定义2 对于正整数k，令函数?(k)的值等于模k的 所有简化剩余类的个数，称?(k)为