初等数论1整除性

《初等数论1整除性》由会员分享，可在线阅读，更多相关《初等数论1整除性（23页珍藏版）》请在装配图网上搜索。

1、第四讲 初等数论 1 整除性本讲概述 数论是数学中极其重要又非常迷人的一个分支，目前我们仅学习初等数论中较浅的内容 . 初等数论是数学竞赛四大模块中较难以掌握的模块之一， 在数学竞赛中占据极其重要的位置 .特别是联 赛改制以后，二试必考一道 50 分的数论大题，一试也会有一到两道数论方面的问题.数论与组合水平如何是大家能否获得联赛一等奖甚至更好成绩的关键 .初等数论这块的竞赛问题涉及到的知识点极少，甚至可以说绝大部分同学在小学初中的培训中基本都接触过 .但是限于初中的知识面和同学的年龄，考试中一般不出现较为深入、难度较高的数论问题.到了高中， 大家将复习小学初中阶段的数论知识， 并将其中的很多

2、知识更为理论化、系统化 .高中的数论问题难度 也会明显增高 . 但是在数论这一模块中，我们并不提倡大家过多地掌握很多高深的数论知识，而是提倡大 家真正去灵活熟练地运用最基本、最重要的数论基础知识和重要定理来解决问题 .由于同学们在小学、初中都已经学过不少关于初等数论的初步知识，所以这里我们把大家比较熟悉的 知识都罗列在下面，对其中大部分定理将不给出证明，直接给出结论 .如果不特别说明，本讲中所有字母均代表正整数 .一、整除1整除的定义两个整数 a 和 b(b 0) ，若存在整数 k，使得 a=bk ，我们称 a 能被 b 整除，记作 b|a 此时把 a 叫做 b 的倍数，b 叫做 a 的约数如

3、果 a 除以 b 的余数不为零， 则称 a不能被 b 整除，或 b 不整除 a，记作 b?a 2数的整除特征( 1)1 与 0 的特性：1 是任何整数的约数，即对于任何整数a，总有 1|a 0 是任何非零整数的倍数， a0，a 为整数，则 a|0 （2）能被 2，5；4，25；8，125 ；3，9；11，7，13 整除的数的特征：能被 2 整除的数的特征：个位为 0， 2，4， 6，8 的整数能被 2 整除，我们记为 2k（k 为整数 ）能被 5 整除的数的特征：个位数为 0 或 5 的整数必被 5 整除，我们记为 5k（k 为整数 ） 能被 4、25 整除的数的特征： 末两位数字组成的两位数

4、能被 4（ 25 ）整除的整数必能被 4（25 ）整除能被 8，125 整除的数的特征：末三位数字组成的三位数能被8（125 ）整除的整数必能被 8（125 ）整除能被 3，9 整除的数的特征：各个数位上数字之和能被3 或 9 整除的整数必能被 3 或 9 整除能被 11 整除的数的特征： 一个整数的奇数位数字之和与偶数位数字之和的差如果是 11 的倍数， 则这 个数就能被 11 整除能被 7，11，13 整除的数的特征：一个三位以上的整数能否被7（11 或 13 ）整除，只须看这个数的末三位数字表示的三位数与末三位以前的数字组成的数的差（以大减小）能否被7（11 或 13 ）整除3整除的几条

5、性质（ 1 ）自反性： a|a（a 0）（2）对称性：若 a|b, b|a ，则 a=b（3）传递性：若 a|b, b|c ，则 a|c（4）若 a|b, a|c ，则 a|（b, c）（ 5 ）若 a|b, m 0 ，则 am|bm（ 6 ）若 am|bm, m 0 ，则 a|b（7）若 a|b, c|b, （a, c）=1 ，则 ac|b、带余除法对于任一整数 a 及大于 1 的整数 m ，存在唯一的一对整数 q, r （0 rm） ，使得 a=qm+r 成立，这个 式子称为带余除法式。 q 就是 a 除以 m 的不完全商， r 就是 a 除以 m 的余数。证明：取由所有 m 的整数倍排成

6、一列数高一联赛班第 4 讲学生版, km, , 2m, m, 0, m, 2m, , km, （kN）a 必介于该数列中的某两个相邻数之间，即存在整数q ，使 qm a（q+1）m 。令 r=a qm ，则 0 rm ，于是有 a=qm+r如还有整数 q1,r1 满足 a=q 1m+r 1 （0 r1m） ，则q 1m+r 1=qm+r m（q 1 q）=r r 1若 q1q ，则 |m（q 1 q）| m ，而 |r r1|m ，这是不可能的 .这说明 q1=q, 于是 r1=r 。三、基本定义：奇数、偶数、素数、合数、最大公约数、最小公倍数、完全平方数、阶乘1、将全体整数分为两类， 凡是

7、2 的倍数的数称为偶数， 否则称为奇数 .因此，任一偶数可表为 2m（m Z）， 任一奇数可表为 2m+ 1 或 2m 1 的形式 .奇、偶数具有如下性质：（ 1）奇数奇数 =偶数；偶数偶数 = 偶数；奇数偶数 = 奇数；偶数偶数 = 偶数；奇数偶数 = 偶数；奇数奇数 = 奇数；（ 2）任何一个正整数 n，都可以写成 n 2 m l的形式，其中 m 为非负整数， l 为奇数.2 、一个大于 1 的整数 n 如果没有真因子（大于 1 而小于 n 的约数），则称 n 为素数；否则称它为合数 . 素数的性质 1 ：若 p 为素数， a,b 为整数 ,如 p|ab, 那么 p 必整除 a,b 之一

8、.素数的性质 2：素数有无穷多个 .（欧几里得在公元 3 世纪给出了一个经典的利用反证法的证明 ）3、设 a,b, ,c 是有限个不全为零的整数，同时整除它们的整数叫做它们的公约数（或公因子）.这些数中必有一个最大的，称为 a,b, ,c的最大公约数，记作（ a,b, ,c）.如果（ a,b, ,c）=1 ，则称 a,b, ,c 是 互素的；同时为它们的倍数的整数叫做它们的公倍数，其中正的公倍数中最小的那个称为最小公倍数， 记作 a,b, ,c4、 一个数如果是另一个整数的完全平方，那么我们就称这个数为完全平方数，也叫做平方数.性质 1 ：完全平方数的末位数只能是 0,1,4,5,6,9.性质

9、 2 ：奇数的平方的个位数字为奇数，十位数字为偶数 .性质 3 奇数的平方是 8n+1 型；偶数的平方为 8n 或 8n+4 型 .性质 4不能被 5整除的数的平方为 5k 1型，能被 5整除的数的平方为 5k 型.性质 5 ：平方数的形式具有下列形式之一： 16m,16m+1, 16m+4,16m+9. 上述性质比较简单，同学们可自行证明之 .5、对任一正整数 n，定义 n 的阶乘为 n! n （n 1） （n 2） 3 2 1 四、自然数唯一分解定理、约数个数公式每个大于 1 的自然数 n 均可分解为有限个素数之积， 如不计素数在乘积中的顺序， 那么这种分解方式 是唯一的（证明略） .将相

10、同的素因子写在一起，那么 n 可以唯一地写成：1 2 kn p11 p22 pkk其中 p1, p2,., pk 为互不相同的素数，而1, 2,., k 是正整数，上式称为 n 的标准分解 .自然数 n 的正约数个数公式为 （n） （ 1 1）（ 2 1）.（ k 1）例题精讲【例 1】 （热身问题）证明以上理论部分给出的一些性质：（1 ）、一个三位以上的整数能否被 7（11 或 13 ）整除，只须看这个数的末三位数字表示的三位数 与末三位以前的数字组成的数的差（以大减小）能否被7（11 或 13 ）整除（2 ）奇数的平方都可表为 8m+1 形式，偶数的平方都可表为 8m 或 8m+4 的形式

11、（ m Z）（3 ）素数的性质 1：若 p 为素数， a,b 为整数 ,如 p|ab, 那么 p 必整除 a,b 之一 .（4 ）证明约数个数公式 .高一联赛班第 4 讲学生版n 为平方数 .例 2】 （ 1）如自然数 n 的正约数个数为奇数，证明（2） ab （a,b） a,b例 3】 （ 1）证明 n2 n 1不是平方数；（ 2）证明连续三个自然数之积非平方数.（ 3）证明十进制表示中有 3 个数位为 1，其它数位均为 0 的数 n 非平方数例4】 记 f （n） n2 n 41 ，证明：（ 1 ）有无穷多个正整数 n 使得 f（n） 为合数； （ 2）有无穷多个正整数 n 使得 43|f

12、（n）高一联赛班第 4 讲学生版例 5】 试求所有这样的质数 p, 使得 p2 11恰有 6 个不同的正约数例 6 】 三角形三边长均为质数，证明：其面积不可能为整数例 7】 证明： 1992 | 997995 995997高一联赛班第 4 讲学生版888.111318 1319试找出最小的自然数 n ，使它的立方的十进制表示中末三位数字恰为p,q 均为正整数 ,使得 p 1 1 1 1 Lq 2 3 4 试证 :1979 p1990例10】以 d(n) 表示 n 的正因子的个数，试确定 S= d(k) 的奇偶性 k1且 dd4 1(d1 d2 d4)d8 ，求 n.例 11】 自 然数 n

13、恰有 12 个正因数，将它们由小到大排列： 1 d1 d2 . d12 n高一联赛班第 4 讲学生版大显身手1 可以对写在黑板上的四位数进行如下形式的操作：或者将它的某两个相邻数字同时加1 ，如果它们都不等于 9 ；或者将它的某两个相邻数字同时减1 ，如果它们都不等于 0 ，试问能否通过这样的操作将 1234 变为 2002 ？2 可以将 1-16 写成一行，使得每两个相邻数之和均为完全平方数；但不能写成一圈仍满足此条件3 设 n 为正整数，若 2n 1,3n 1 均为完全平方数，试确定 5n+3 是否为合数？如可能为素数，试给出 n 的一个可能值34 试求所有满足 p q (p q )3的质

14、数对 (p,q) .高一联赛班第 4 讲学生版(a, b) a bb 1 a 15 设 a,b 为正整数，且 为整数，证明： ab学习之外1. 化圆为方求作一正方形使其面积等於一已知圆；2. 三等分任意角；3. 倍立方求作一立方体使其体积是一已知立方体的二倍；4. 做正十七边形 .但後来他的墓碑上并没有刻高一联赛班第 4 讲学生版14获奖理由：这里所说的“几何尺规作图问题”是指做图限制只能用直尺、圆规，而这 里的直尺是指没有刻度只能画直线的尺 . “几何尺规作图问题”包括以下四个问题几何尺规作图问题”蜂窝猜想”世界最迷人的数学难题”评选揭晓以上四个问题一直困扰数学家二千多年都不得其解， 而实际

15、上这前三大问题都已证明 不可能用直尺圆规经有限步骤可解决的 . 第四个问题是高斯用代数的方法解决的，他也视 此为生平得意之作， 还交待要把正十七边形刻在他的墓碑上， 上十七边形，而是十七角星，因为负责刻碑的雕刻家认为，正十七边形和圆太像了，大家 一定分辨不出来 .编者注：另一类有趣的作图问题是：仅用直尺或仅用圆规作图； “生锈圆规问题” （圆 规仅能按照规定大小作圆） . 上世纪 80 年代张景中院士成功解决了美国数学家匹多教授 （著名的匹多不等式的提出者）给出的若干生锈圆规作图问题 .获奖理由： 四世纪古希腊数学家佩波斯提出 ,蜂窝的优美形状 ,是自然界最有效劳动的 代表. 他猜想 , 人们

16、所见到的、截面呈六边形的蜂窝 ,是蜜蜂采用最少量的蜂蜡建造成的 . 他的这一猜想称为 蜂窝猜想 , 但这一猜想一直没有人能证明 .1943 年, 匈牙利数学家陶斯 巧妙地证明 ,在所有首尾相连的正多边形中 , 正多边形的周长是最小的 .1943 年, 匈牙利数 学家陶斯巧妙地证明 , 在所有首尾相连的正多边形中 , 正多边形的周长是最小的 . 但如果多 边形的边是曲线时 , 会发生什么情况呢 ?陶斯认为 , 正六边形与其他任何形状的图形相比,它的周长最小 , 但他不能证明这一点 . 而黑尔在考虑了周边是曲线时 , 无论是曲线向外凸 , 还是向内凹 ,都证明了由许多正六边形组成的图形周长最小.

17、他已将 19 页的证明过程放在因特网上 , 许多专家都已看到了这一证明 , 认为黑尔的证明是正确的。附录：高一秋季、寒假 联赛班讲义目录 （初定）编排思想： 尽量跟教材进度走，为此在秋季第四、五讲插入了数论的初步知识，以此来调控函数部分的进度 寒假班则完整地讲授组合部分，目标是达到能够轻松解决高考、联赛一试、自主招生级别的组合问题 并能够解决二试及冬令营中中下等难度的组合问题 .秋季班第一讲 集合第二讲 一元二次函数第三讲 函数的三性第四讲 数论初步（ 1 ）第五讲 数论初步（ 2 ）第六讲 基本初等函数：幂、指数、对数第七讲 含绝对值函数与函数最值第八讲 函数综合与总结第九讲 函数迭代与函数方程初步第 10 讲 三角函数入门第 11 讲 三角恒等变换第 12 讲 正弦定理与余弦定理第 13 讲 几何题的三角证法初步第 14 讲 三角不等式第 15 讲 向量与几何寒假班第一讲 计数（ 1）简单的排列第二讲计数（ 2 ）复杂一些的排列第三讲组合恒等式第四讲抽屉原理第五讲稍复杂的组合题第六讲概率初步（侧重应用组合来解决的）第七讲数学思想（1 ）极端性原则高一联赛班第 4 讲学生版