当前位置:首页 >> 学科竞赛 >> 竞赛专题--同余

竞赛专题--同余


第5讲

同余

【知识点】 1.设 m 是一个给定的正整数,如果两个整数 a 与 b 用 m 除所得的余数相同,则称 a 与 b 对模同余,记作 a ? b(mod m) ,否则,就说 a 与 b 对模 m 不同余,记作

a ? b(mod m) ,显然, a ? b(mod m) ? a ? km ? b, (k

? Z ) ? m | (a ? b) ;
每一个整数 a 恰与 1,2,……,m,这 m 个数中的某一个同余; 2.同余的性质: 1).反身性: a ? a(mod m) ; 2).对称性: a ? b(mod m) ? b ? a(mod m) ; 3).若 a ? b(mod m) , b ? c(mod m) 则 a ? c(mod m) ; 4).若 a1 ? b1 (mod m) , a2 ? b2 (mod m) ,则 a1 ? a2 ? b1 ? b2 (mod m) 特别是 a ? b(mod m) ? a ? k ? b ? k (mod m) ; 5).若 a1 ? b1 (mod m) , a2 ? b2 (mod m) ,则 a1a2 ? b1b2 (mod m) ; 特别是 a ? b(mod m), k ? Z ? 则ak ? bk(mod m)

a ? b(mod m), n ? N ? 则a n ? b n (mod m) ;
6). a(b ? c) ? ab ? ac(mod m) ; 7).若 ac ? bc(mod m), 则当(c, m) ? 1时,a ? b(mod m)

当(c, m) ? d时,a ? b(mod
8).若 a ? b(mod m1 ) ,

m ).特别地,ac ? bc( m o d ) ? a ? b( m o d ) ; mc m d

a ? b(mod m2 )
a ? b(mod m3 )
………………

a ? b( m o d n ) ,且 M ? [m1 , m2 ,??mn ],则a ? b(mod M ) m

【例 1】证明:完全平方数模 4 同余于 0 或 1; 证明: 设n是任一整数,则n ? 2k或者n ? 2k ? 1, k ? Z ;

当n ? 2k时,n 2 ? 4k 2 ? 0(mod 4); 当n ? 2k ? 1时,n 2 ? 2k ? 1) 2 ? 1(mod 4); (
所以原命题成立; 【例 2】证明对于任何整数 k ? 0 , 2
6 k ?1

? 36k ?1 ? 56k ? 1 能被 7 整除;

证:令M ? 2 6 k ?1 ? 36 k ?1 ? 5 6 k ? 1 ? M ? 2 ? 2 6 k ? 3 ? 36 k ? 5 6 k ? 1

? 2 ? 64 k ? 3 ? 729 k ? 15625 k ? 1 ? 2 ? (7 ? 9 ? 1) k ? 3 ? (7 ? 104 ? 1) k ? (7 ? 2232 ? 1) k ? 1 ? 2 ? 7 ? A ? 2 ? 3? 7 ? B ? 3 ? 7 ?C ?1?1 ? (2 ? 3 ? 1 ? 1)(mod 7) ? 0(mod 7)
? 对于?k ? 0, 且k ? Z , 2 6k ?1 ? 36k ?1 ? 56k ? 1 都能被 7 整除;
注: a ? 1(mod b) ? a ? 1(mod b), k ? Z
k ?

【例 3】试判断 1971

26

? 1972 27 ? 1973 28 能被 3 整除吗?

解: 1971 ? 0(mod 3),1972 ? 1(mod 3),1973 ? 2(mod 3) ? ?1971 26 ? 1972 27 ? 1973 28 ? (0 26 ? 127 ? 2 28 )(mod 3) 即: 26 ? 1972 27 ? 1973 28 ? (1 ? 2 28 )(mod 3) 1971 又 ? 2 28 ? 414 ? 1(mod 3),? (1 ? 2 28 ) ? 2(mod 3) ?1971 26 ? 1972 27 ? 1973 28 不能被3整除;

【例 4】 能否把 1, ……, 2, 1980 这 1980 个数分成四组, 令每组数之和为 S1,S 2,S 3,S 4 ,

10 10 10 且满足 S 2 ? S1,= ,S 3 ? S 2= ,S 4 ? S 3= ;

解:依题意可知:T ? S1 ? S 2 ? S 3 ? S 4=S1 ? S1 ? 10 ? S1 ? 20 ? S1 ? 30 ? T ? 4 S1 ? 60 ? 0(mod 4) 1980 ? 1981 ? 990 ? 1981 ? 2(mod 4) 2 ? 产生矛盾, 不能这样分组; ? 又 ?T ? 1 ? 2 ? 3 ? ? ? 1980 ?

【例 5】在已知数列 1,4,8,10,16,19,21,25,30,43 中,相邻若干数之和,能被 11

整除的数组共有多少组。

解:记数列各对应项为ai , i ? 1,2, ?10,并记S k ? a1 ? a 2 ? ? ? a k ? S1 , S 2 , ?, S10依次为1、13、 、 、 、 、 、 、 5, 23 39 58 79 104 134 177 它们被11除的余数依次为:5、、6、 2、 2、 1、 2 1、 3、 5、 1 由此可得:S1 ? S 4 (mod 11) ? S10 (mod 11), S 2 ? S 8 (mod 11), S 3 ? S 7 (mod 11) ? S 9 (mod 11) 由于S k ? S j 是数列{ai }相邻项之和,且当S k ? S j (mod 11)时, 11 | S k ? S j,则满足条件的数组有:? 1 ? 3 ? 7组 3
【例 6】设 f ( x) ? a0 x ? a1 x
n n ?1

? a 2 x n?2 ? ? ? an?1 x1 ? a n 是整系数多项式,

证明:若 f (0), f (1), ?, f (1992 )都不能被 1992 整除,则f ( x)没有整数根;

证:假设f ( x)有整数根m,且m ? r (mod 1992 ),0 ? r ? 1992 由题意f (r )不能被1992 整除, ? f (m) ? 0, 则f (r ) ? f (m) ? f (r ) 又 ? f (r ) ? f (m) ? a 0 (r n ? m n ) ? a1 (r n ?1 ? m n ?1 ) ? ? ? a n ?1 (r ? m) ? m ? r (mod 1992 ) ? m i ? r i (mod 1992 ), i ? 1、、 ?、n 2 3、 ? m i ? r i ? 0(mod 1992 ), i ? 1、、 ?、n 2 3、 ?1992 | f (r ) ? f (m) ? f (r ) ? 产生矛盾, f ( x)没有整数根 ?
【例 7】试求出一切可使 n ? 2 ? 1 被 3 整除的自然数 n ;
n

解:若3 | n ? 2 n ? 1,则n ? 2 n ? 2(mod 3) 考虑到n及2 n ,则 当n ? 6k ? 1时, ? 0、 2、 ) (k 1、 ? n ?2 n ? (6k ? 1) ? 2 6 k ?1 ? (12 k ? 2) ? (3 ? 1) k ? 2(mod 3) 当n ? 6k ? 2时, ? 0、 2、 ) (k 1、 ? n ?2 n ? (6k ? 2) ? 2 6 k ? 2 ? (24 k ? 8) ? (3 ? 1) k ? 2(mod 3) 当n ? 6k ? 3时, ? 0、 2、 ) (k 1、 ? n ?2 n ? (6k ? 3) ? 2 6 k ?3 ? 0(mod 3) 当n ? 6k ? 4时, ? 0、 2、 ) (k 1、 ? n ?2 n ? (6k ? 4) ? 2 6 k ? 4 ? (96 k ? 64 ) ? (3 ? 1) k ? 1(mod 3) 当n ? 6k ? 5时, ? 0、 2、 ) (k 1、 ? n ?2 n ? (6k ? 5) ? 2 6 k ? 5 ? (6 ? 32 k ? 160 ) ? (3 ? 1) k ? 1(mod 3) 当n ? 6k ? 6时, ? 0、 2、 ) (k 1、 ? n ?2 n ? (6k ? 6) ? 2 6 k ? 6 ? 0(mod 3) 由上可知当且仅当n ? 6k ? 1,k ? 2时,n ? 2 n 能被3整除; 6
【例 8】在每张卡片上各写出 11111 到 99999 的五位数,然后把这些卡片按任意顺序排成一 列,证明所得到的 444445 位数不可能是 2 的幂;

证:记由 11111、 11112 、 ?、 ? 99999 排成的数为A,则: A=a1 a 2 ?? a88889 , ai ? {11111、 11112 、 ?、 ? 99999 } ? A=a1 ? 10 444440 ? a 2 ? 10 444435 ? a3 ? 10 444430 ? ? ? a88888 ? 10 5 ? a88889 注意到10 5 ? 1(mod 11111 ) ?10 5 k ? 1(mod 11111 ), k ? Z ? A ? a1 ? a 2 ? ? ? a88888 ? a88889 (mod 11111 ) 又 ? a1 ? a 2 ? ? ? a88888 ? a88889 ? 11111 ? 11112 ? ? ? 99999 ? 即:a1 ? a 2 ? ? ? a88888 ? a88889 ? 11111 ? 5 ? 88889 ? A ? 0(mod 11111 ) ? A不可能是2的幂;
【例 9】设 a1 , a 2 ,? a n ,? 是任意一个具有性质 ak ? a k ?1 , (k ? 1) 的正整数的无穷数列,求 证可以把这个数列的无穷多个 a m 用适当的正整数 x, y表示为a m ? x ? a p ? y ? a q , ( p ? q)

11111 ? 99999 ? 88889 2

证:将{a n }按a 2为模的不同剩余类分成若干个子数列 ? {a n }为无限集,而子数列却是有限多个 ? 至少有一个子数列有无穷多项 现考虑这个无穷数列 又 ? {a n }为严格递增的 ? 该子数列中必有一个最小的a p , a p ? a 2,同时还有无限多个a m 属于该子数列,且a m ? a p ? a m ? a p (mod a 2 ) ? a m ? a p ? xa2 , x ? Z 令y=1,a q ? a 2 ? a m ? ya p ? xaq ? a m 是满足题意的要求,且a m 是无限多个

【练习】 1、证明:完全平方数模 3 同余于 0 或 1; 证明:完全平方数模 5 同余于 0、1 或 4; 证明:完全平方数模 8 同余于 0、1 或 4; 证明:完全立方数模 9 同余于-1、0 或 1; 证明:整数的四次幂模 16 同余于 0 或 1;

,求a (在十进制中)的末两位数码; 2、设 a ? Z,且(a,10) ? 1
20

解: (a,10) ? 1, a为奇数 ? ? ? a 20 ? a ? ( 25) ? 1(mod 25) 又 ? a 2 ? 1(mod 4) ? a 20 ? 1(mod 4) 又 ? (25,4) ? 1 ? a 20 ? 1(mod 100 ) ? a 20的末两位位01

3.有一个120 位的数,将它的 位数码以一切可能的方式重新排列,然后从按这种方法所 12 得到的120 位数中随意挑出 个数来,证明它们的和可以被120 整除; 120 证:设这120 个120 位数的前12个数码分别组成的数为:A1 , A2 , ? A120 而每一数的剩下的 个数码组成了数B,则这120 个数的和为: 108 S=( A1 ? A2 ? ? ? A120 ) ? 10 108 ? 120 B 考虑到40 | 10 108,且A1 , A2 , ? A120每个被3除时余数相同 ? 3 | A1 ? A2 ? ? ? A120 , 又 ? (3,40 ) ? 1 ? 120 | ( A1 ? A2 ? ? ? A120 ) ? 10 108 ?120 | S

4.连接写出 到80的两位数,问:所得到的数: 19 192021 ? 7980 能被1980 整除吗? 解:设A=192021 ? 7980,显然20 | A 又 ? 100 k ? (99 ? 1) k ? 99 M ? 1 ? 100 k ? 1(mod 99 ) ? A ? 19 ? 100 61 ? 20 ? 100 60 ? ? ? 79 ? 100 ? 80 ? (19 ? 20 ? 21 ? ? ? 79 ? 80 )(mod 99 ) ? A ? 31 ? 99 (mod 99 ) ? 0(mod 99 ) ? 99 | A 又 ? (20,99 ) ? 1 ?1980 | A


更多相关文档:

竞赛专题--同余

竞赛专题--同余_学科竞赛_高中教育_教育专区。第5讲 同余 【知识点】 1.设 m 是一个给定的正整数,如果两个整数 a 与 b 用 m 除所得的余数相同,则称 a...

第三讲 同余系列竞赛

第七讲:同余式与不定方程 4页 免费 一次同余方程的求解技巧 4页 免费 竞赛专题讲座-几个重要定理... 7页 免费 竞赛专题--欧拉定理、费马... 4页 免费 长...

竞赛专题--同余

竞赛专题--同余 相关搜索:海桂城中学高一上学期数学期末考试答案相关搜索:海桂城中学高一上学期数学期末考试答案隐藏>> 第5讲 同余 【知识点】 1.设 m 是一个给...

高中数学竞赛专题讲座---专题训练_(同余部分的例题与习题)

高中数学竞赛专题讲座---专题训练_(同余部分的例题与习题)_学科竞赛_高中教育_教育专区。同余的概念与应用概念与性质 1. 定义: 若整数 a,b 被整数 m(m≥1)...

高中数学竞赛专题讲座---同余理论及其应用(一)

高中数学竞赛专题讲座---同余理论及其应用(一)_学科竞赛_高中教育_教育专区。同余理论及其应用基础知识 一. 定义 定义 1. 设 m 为正整数, 整数 a 和 b 之差...

同余理论在数学竞赛中的运用

同余理论在数学竞赛中的运用卢军萍 杭州师范大学 数学与应用数学 043 班 摘要:...李胜宏,李名德.高中数学竞赛培优教程(专题讲座)[M].杭州:浙江大学出版社, 2003...

初中数学竞赛专题 同余式及其应用

初中数学竞赛专题 同余式及其应用_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档初中数学竞赛专题 同余式及其应用_学科竞赛_初中教育_教育专区。 ...

高中数学竞赛专题讲座---专题训练 (同余部分的例题与习题)

同余理论在数学竞赛中的应... 2页 免费 高中数学竞赛专题讲座---同... 11页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此...

小学奥数竞赛专题之同余问题

小学奥数竞赛专题同余问题_初一数学_数学_初中教育_教育专区。好资料 小学奥数竞赛专题同余问题 [专题介绍]:同余问题 生活中我会经常遇到与余数有关的问题,比如...

高中数学竞赛培训专题4---同余式与不定方程

高中数学竞赛培训专题4---同余式与不定方程_学科竞赛_高中教育_教育专区。竞赛培训专题 7---同余式与不定方程 同余式和不定方程是数论中古老而富有魅力的内容....
更多相关标签:
同余定理 | 同余方程 | 线性同余法 | 同余问题 | 线性同余法产生随机数 | 同余式 | 线性同余发生器 | 线性同余 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com