tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

竞赛讲座 整数的整除性和同余


竞赛讲座-整数的整除性和同余
一、整数的整除性 1. 整数的整除性的有关概念、性质 (1)整除的定义:对于两个整数 a、d (d≠0) 若存在一个整数 p,使得 , 成立,则称 d 整除 a,或 a 被 d 整除,记作 d|a。若 d 不能整除 a,则记作 d a, 如 2|6,4 6。 (2)性质 1)若 b|a,则 b|(-a),且对任意的非零整数 m 有 bm|a

m 2)若 a|b,b|a,则|a|=|b|; 3)若 b|a,c|b,则 c|a 4)若 b|ac,而(a,b)=1((a,b)=1 表示 a、b 互质,则 b|c; 5)若 b|ac,而 b 为质数,则 b|a,或 b|c; 6)若 c|a,c|b,则 c|(ma+nb),其中 m、n 为任意整数(这一性质还可以推广 到更多项的和) 7) 任意两个连续整数之积必定是一个奇数与一个偶数之一积,因此一定可被 2 整除。 8) 任意三个连续整数之中至少有一个偶数且至少有一个是 3 的倍数, 所以它们之 积一定可以被 2 整除,也可被 3 整除,所以也可以被 2×3=6 整除。 这个性质可以推广到任意个整数连续之积。 2.整除性问题的证明方法 例 1 证明: 证明 ∵ ∴ ∵ 又∵ , 2n、2n+1、2n+2 为三个连续整数,其积必是 3 的倍数,而 2 与 3 互质, 为连续二整数的积,必可被 2 整除. 对任何整数 n 均为整数, 为整数,即原式为整数. 对任何整数 n 都为整数,且用 3 除时余 2。



是能被 3 整除的整数.

故 被 3 除时余 2. 2 例 2 一整数 a 若不能被 2 和 3 整除,则 a +23 必能被 24 整除. 2 2 2 证明 ∵a +23=(a -1)+24,只需证 a -1 可以被 24 整除即可. ∵2 .∴a 为奇数.设 a=2k+1(k 为整数), 2 2 2 则 a -1=(2k+1) -1=4k +4k=4k(k+1). ∵k、k+1 为二个连续整数,故 k(k+1)必能被 2 整除, 2 ∴8|4k(k+1),即 8|(a -1). 又∵(a-1),a, (a+1)为三个连续整数,其积必被 3 整除,即 3|a(a-1) (a+1) 2 =a(a -1), 2 2 2 ∵3 a,∴3|(a -1).3 与 8 互质, ∴24|(a -1),即 a +23 能被 24 整除. 例3 设有 n 个实数 x1,x2,…,xn,其中每一个不是+1 就是-1, 且 证明 设 试证 n 是 4 的倍数. (i=1,2,…,n-1),

则 yi 不是+1 就是-1,但 y1+y2+…+yn=0,故其中+1 与-1 的个数相同,设为 k,于 k 是 n=2k.又 y1y2y3…yn=1,即(-1) =1,故 k 为偶数, ∴n 是 4 的倍数. 其他方法: 整数 a 整除整数 b,即 b 含有因子 a.这样,要证明 a 整除 b,采用各种公式和变形 手段从 b 中分解出因子 a 就成了一条极自然的思路. 3 例 4 使 n +100 能被 n+10 整除的正整数 n 的最大值是多少? 3 2 解 n +100=(n+10)(n -10n+100)-900. 若 n+100 能被 n+10 整除,则 900 也能被 n+10 整除.而且,当 n+10 的值为最大时, 相应地 n 的值为最大.因为 900 的最大因子是 900.所以,n+10=900,n=890. 例 5 设 a、b、c 为满足不等式 1<a<b<c 的整数,且(ab-1)(bc-1)(ca-1) 能被 abc 整除,求所有可能数组(a,b,c). 解 ∵(ab-1)(bc-1)(ca-1) 2 2 2 =a b c -abc(a+b+c)+ab+ac+bc-1,① ∵abc|(ab-1)(bc-1)(ca-1). ∴存在正整数 k,使 ab+ac+bc-1=kabc, ②

k=









∴k=1. 矛盾. 已知 a>1. ∴只

若 a≥3,此时 1= < 有 a=2. 当 a=2 时,代入②中得 2b+2c-1=bc,

即 1= < ∴0<b<4,知 b=3,从而易得 c=5. 说明:在此例中通过对因数 k 的范围讨论,从而逐步确定 a、b、c 是一项重要解 题技巧. 二、同余 1. 同余式及其应用 定义:设 a、b、m 为整数(m>0),若 a 和 b 被 m 除得的余数相同,则称 a 和 b 对模 m 同余.记为 或 一切整数 n 可以按照某个自然数 m 作为除数的余数进行分类,即 n=pm+r(r=0, 1,…,m-1),恰好 m 个数类.于是同余的概念可理解为,若对 n1、n2,有 n1=q1m+r, n2=q2m+r,那么 n1、n2 对模 m 的同余,即它们用 m 除所得的余数相等. 利用整数的剩余类表示,可以证明同余式的下述简单性质: (1) (2) (3) (4) ① ② ③ ① 若 ,则 m|(b-a).反过来,若 m|(b-a),则 ; 如果 a=km+b(k 为整数),则 ; 每个整数恰与 0,1,…,m-1,这 m 个整数中的某一个对模 m 同余; 同余关系是一种等价关系: 反身性 对称性 传递性 , ; , ; ,则 ,则 ,反之亦然. ,则 ;

(5)如果

② 特别地 应用同余式的上述性质,可以解决许多有关整数的问题. n 例 1 求使 2 +1 能被 3 整除的一切自然数 n. 解∵ 则 2 +1
n



∴当 n 为奇数时,2 +1 能被 3 整除; n 当 n 为偶数时,2 +1 不能被 3 整除. 999 例 2 求 2 最后两位数码. 999 解 考虑用 100 除 2 所得的余数. ∵ ∴ 又 ∴ ∴ ∴2 的最后两位数字为 88. 1980 1981 例 3 求证 3 +4 能被 5 整除. 证明 ∵
999

n

∴ ∴ ∴


推荐相关:

竞赛讲座 02整数的整除性

竞赛讲座 03同余式与不定方... 10页 免费 竞赛讲座 01奇数和偶数 9页 免费...竞赛讲座 02 -整数的整除性 1. (1) 整数的整除性的有关概念、性质 整除的...


竞赛讲座 01奇数和偶数

竞赛讲座 02整数的整除性 竞赛讲座 03同余式与不定方... 竞赛讲座 04平面几何...竞赛讲座 01 -奇数和偶数整数中,能被 2 整除的数是偶数,反之是奇数,偶数可用...


竞赛讲座01-奇数和偶数

竞赛讲座02-整数的整除性 竞赛讲座03-同余式与不定方... 竞赛讲座15-函数方程...是偶数,反之是奇数,偶数可用 2k 表示 ,奇数可用 2k+1 表示,这里 k 是整数...


竞赛讲座20-排列、组合、二项式定理

竞赛讲座01-奇数和偶数 竞赛讲座02-整数的整除性 竞赛讲座03-同余式与不定方... 竞赛讲座15-函数方程 竞赛讲座16-不等式 竞赛讲座18-数学归纳法1...


竞赛讲座 07面积问题和面积方法

竞赛讲座 07面积问题和面积方法_数学_初中教育_教育专区。竞赛讲座今日...竞赛讲座 02整数的整除性... 竞赛讲座 03同余式与不定... 竞赛讲座 04平面...


竞赛讲座 03同余式与不定方程

竞赛讲座 03 --同余式与不定方程同余式和不定方程是数论中古老而富有魅力的内容...说明:用整数的整除性来判定方程有无整数解,是我们解答这类问题的常用方法. 例...


整除和同余

同余问题 14页 免费 整除问题 9页 免费 数学竞赛辅导讲座:同余 12页 免费 信息...整除和同余 一、整除 1、整除的定义:一般地,如 a,b,c 为整数,b 不为零,...


高中数学竞赛讲座 03同余式与不定方程

高中数学竞赛讲座 03同余式与不定方程_学科竞赛_高中教育_教育专区。竞赛讲座 03...说明:用整数的整除性来判定方程有无整数解,是我们解答这类问题的常用方法. 例...


人教版高中数学竞赛讲座:整数的整除性

竞赛讲座 02 -整数的整除性 1. (1) 使得 整数的整除性的有关概念、性质 整除的定义:对于两个整数 a、d(d≠0),若存在一个整数 p, 成立,则称 d 整除 ...


ko数学竞赛辅导讲座:同余

ko数学竞赛辅导讲座:同余_学科竞赛_初中教育_教育...剩余类和完全剩余系,同余方程,整数模的阶和中国剩余...1, 则a 模 m 的阶整除欧拉函数 ? (m). 特别...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com