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

∴ ∴ ∴


推荐相关:

整数的整除性与同余(教案)

第21讲 整数的整除性 7页 2下载券 竞赛讲座:第2节--整数的... 8页 免费...整数的整除性与同余(教案) 整数的整除性与同余(教案)教学内容 教学目标 整除与...


数学竞赛教学计划-张大林

数列不等式(2) 不等式测试(包含不等式解法)(2) 竞赛期中测试(3) 三、初等数论(3 周) 第 18 讲 整数及整除性(2) 第 19 讲 同余理论应用(4) 第 ...


密码习题及部分参考答案

二、数论和有限域的基本概念: 1、整除性和除法 2...模运算和同余 4、模运算的性质 5、剩余类集合 6...五、数论入门: 任意整数的分解方式 费马定理 欧拉...


竞赛数学数论专题

1. 基本内容 竞赛数学中的数论问题主要有: (1) 整除性问题; (2) 数性的...m o d m ) 同余具有反身性: a ? a(mod m) 、 对称性:若 a ? b(...


初等数论与中学数学

的整除理论有如下结论:连续 n 个整数中必然存在唯一的一个 数属于模 n 同余...总结:竞赛中关于数论的论证题,基本上都是讨论整数性和整数解,证明方法 通常有:...


密码学复习题

修改和拒绝服务,判断题) 我们生活中存在哪些安全威胁,请举例说明 数论和有限域的基本概念: 整除性和除法 用欧几里德算法求两个整数的最大公因子 模运算和同余 ...


毕业论文Fermat定理与Euler定理

而且初等数论是其中不需要其他学科的帮助,只依靠初等的 方法来研究整数性质的分支.初等数论最主要的工具有整数的整除性和同余.Fermat定理 与Euler定理都是初等数论中...


数学与应用数学专业人才培养方案

竞赛数学 数学实验 数学分析选讲 高等代数选讲 泛函分析 拓扑学 专业任选课小计...初等数论内容提要:整数的整除性,同余式,不定方程,连分数,代数数超越数。 ...


数论浅谈

整数同余 关键字 摘要:数论是一门古老而基础的...──整除性问题就有系统的研究,关于质数、和数、...浅析中学竞赛数学中的数... 7页 免费 浅谈初等数论...


嘉应学院数学系

专业任选课 数学史 数学教育技术 竞赛数学 数学实验 数学分析选讲 高等代数选讲...初等数论 内容提要:整数的整除性,同余式,不定方程,连分数,代数数超越数。 ...

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