《同余及其基本性质》课件1.ppt

1、2.1 同余及其基本性质,人教B版数学选修4-6初等数论初步,同余是数论中一个基本概念, 它的基本概念与记号都是伟大的数学家高斯引进的.它的引人简化了数论中的许多问题. 本章着重讨论同余的概念及其基本性质，完全剩余系和简化剩余系，两个重要定理（欧拉定理和费马小定理）及其应用,定义1 给定一正整数m（模）, 若用m去除两个整数a和b所得余数相同, 则称a 与b对模m同余, 记作ab(mod m); 若余数不同, 则称 a 与b对模m不同余, 记作ab(mod m). 定义2若m|(a-b), 则称a与b对模m同余. 定义3若a= mq+b, 则称a与b对模m同余. 显然，a0(mod m) 等价

2、于 m| a.,由同余的定义, 可得下列性质: （1）自反性: aa (mod m). （2）对称性: 若ab(mod m), 则 ba(mod m). （3）传递性: 若ab(mod m), bc(mod m), 则ac(mod m).,同余的性质 若a1b1(mod m), a2b2(mod m), 则: （4） a1 + a2 b1+ b2(mod m). 推论：若a +bc(mod m), 则a c- b(mod m) （5） a1 a2 b1b2(mod m). 推论() 若ab(mod m)，则akbk(mod m)， 其中k为整数. 推论( )若ab(mod m)，则 an bn

3、(mod m), 其中 n为自然数.,（7）若 ac bc(mod m), (m,c)=d, 则 ab(mod m/d). 特别地，当(m,c)=1时，有ab(mod m). （8）若ab(mod m)，则akbk(mod mk)， 其中k为大于零的整数； 若ab(mod m)，d为a,b及 m的任一正公约数, 则 a /d b /d(mod(m/d) . （9） ab(mod mi), (1in), 则ab (mod m1,m2,mn). （10） 若ab(mod m), 且d|m, 则 ab(modd ).,思考题： 1、整数a是偶数的同余式为( ). 2、整数a是偶数但不能被4整除，则其

4、同余式为 ( ) . 3、已知a 5(mod6 ) ，则a被3除余( ). 4、已知a 3(mod4 ) ，那么2a+1被4除余( ).,例题 例1 有一个大于1的整数，它除300，262，205所得的余数相同，求这个数。 例2 有兵200余不足300，若1至3报数，最后一人报数为2，若1至5报数，最后一人报数为2，若1至7报数，最后一人报数也为2。问这一队士兵有多少人？ 例3 某天是星期一，从这天后第22012天是星期几？,例4 分别求3406的个位数字和72012的末两位数字. 例5 证明：641 | 225+1 （欧拉证明了费马数F5不是素数） 例6 （1）求使2n-1能被7整除的一切正

5、整数n； （2）证明：没有正整数n使2n+1能被7整除.,自主学习,特殊数的整除特征 定理 正整数a能被9整除的特征是 a的数字和能被 9整除. 指出：同理可得到被2（或5）、4（或25）、8（或125）、3（或9）、11等数整除的特征. 试证： （1）正整数a能被11整除特征是a的奇数位数字和与偶数位数字和的差能被11整除. （2）正整数a能被11整除特征是a 的末三位数与末三位数之前的数之差能被11整除.（同理可证7与13也有类似特征）,自主学习,定理 (弃九法) 若ab=c, 其中a0, b0, 并且, 则: . 可见, 若 , 则可判断乘积ab=c是错误的, 这即是弃九法之原则：“弃九

6、余不等，计算有问题”.,自主学习,例8 求证 199757113828. 证明 由于199719978 (mod 9) 57 57 3(mod 9) 113828 l+1+3+8+2+8 5(mod 9) 但是, 83=24, 而245(mod 9), 得证. 注意：使用弃九法时，若 也未必肯定原计算是无误的. 例如,：199757=113829, 但有人计算结果是113838，由弃九法可得 24 6(mod 9), 显然, 错误未验证出来.,费马数,当 时， 总是素数吗？ 这个问题是费马在1640年给梅森的信中宣布的一个猜想。很容易能证明，前5个费马数都是素数。到了1732年，数学家欧拉发现下一个费马数不是素数，从而否定了费马的猜想。,判断题： 1、若ab(mod m), k为自然数，