2.1 同余式定义和基本性质
• 由同余的定义, 可得下列性质: （1）自反性: aa (mod m). （2）对称性: 若ab(mod m), 则 ba(mod m). （3）传递性: 若ab(mod m), bc(mod m), 则ac(mod m).
2.1 同余式定义和基本性质
• 同余的性质 若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(mod m), 其中 n为自然数.
（1）正整数a能被11整除特征是a的奇数位数字和与偶数 位数字和的差能被11整除. （2）正整数a能被11整除特征是a 的末三位数与末三位 数之前的数之差能被11整除.（同理可证7与13也有类 似特征）
自主学习
定理 (弃九法) 若ab=c, 其中a>0, b>0, 并且, p m n i j 则: c ck 10k a ai 10 , b b j 10 ,
2.1 同余式定义和基本性质
• 定义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) 等价于 m| a.
2.1 同余式定义和基本性质
（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), (1≤i≤n), 则ab (mod [m1,m2,…,mn]). （10） 若ab(mod m), 且d|m, 则 ab(modd ).
费马数
当 n 0,1,2,3, 时， Fn 2 2 1 总是素数吗？
n
这个问题是费马在1640年给 梅森的信中宣布的一个猜想。 很容易能证明，前5个费马数都 是素数。到了1732年，数学家 欧拉发现下一个费马数不是素 数，从而否定了费马的猜想。
判断题： 1、若ab(mod m), k为自然数， 则kakb(mod m), kakb(mod km). 反之呢？ 2、若ab(mod m),则a2 b2(mod m). 反之，若a2 b2(mod m)，则ab(mod m)源自专业基础课程初等数论
（二）
Number Theory
第二章 同 余
• 同余是数论中一个基本概念, 它的基本 概念与记号都是伟大的数学家高斯引进 的.它的引人简化了数论中的许多问题. • 本章着重讨论同余的概念及其基本性质， 完全剩余系和简化剩余系，两个重要定 理（欧拉定理和费马小定理）及其应 用．
i 0
j 0
k 0
( a )( b j ) ( Ck )(mod9)
i i 0
m
n
p
.
j 0
k 0
• 可见, 若 ( ai )( b ) ( C )(mod9) j k
m n p i 0 j 0 k 0
,
则可判断乘积ab=c是错误的, 这即是弃九法之 原则：“弃九余不等，计算有问题”.
2.1 同余式定义和基本性质
思考题： 1、整数a是偶数的同余式为( ). 2、整数a是偶数但不能被4整除，则其同余式 为( ). 3、已知a 5(mod6 ) ，则a被3除余( ). 4、已知a 3(mod4 ) ，那么2a+1被4除余( ).
2.1 同余式定义和基本性质
• 例题 例1 有一个大于1的整数，它除300，262，205 所得的余数相同，求这个数。 例2 有兵200余不足300，若1至3报数，最后一 人报数为2，若1至5报数，最后一人报数为2， 若1至7报数，最后一人报数也为2。问这一队 士兵有多少人？ 例3 某天是星期一，从这天后第22012天是星期 几？
2.1 同余式定义和基本性质
例4 分别求3406的个位数字和72012的末两位数字.
例5 证明：641 | 225+1
（欧拉证明了费马数F5不是素数）
例6 （1）求使2n-1能被7整除的一切正整数n； （2）证明：没有正整数n使2n+1能被7整除.
自主学习
特殊数的整除特征 定理 正整数a能被9整除的特征是 a的数字和能 被 9整除. 指出：同理可得到被2（或5）、4（或25）、8 （或125）、3（或9）、11等数整除的特征. 试证：
自主学习
例8 求证 1997×57≠113828. 证明 由于19971＋9＋9＋78 (mod 9) 57 5＋7 3(mod 9) 113828 l+1+3+8+2+8 5(mod 9) • 但是, 8×3=24, 而24≠5(modm 9), 得证. p n i • 注意：使用弃九法时，若 ( a )( b j ) ( Ck )(mod9) i 0 j 0 k 0 也未必肯定原计算是无误的. 例如,：1997×57=113829, 但有人计算结果是 113838，由弃九法可得 24 6(mod 9), 显然, 错误未验证出来.