初等数论1——整除性

高一·联赛班·第4讲·学生版1第四讲初等数论1——整除性本讲概述数论是数学中极其重要又非常迷人的一个分支，目前我们仅学习初等数论中较浅的内容.初等数论是数学竞赛四大模块中较难以掌握的模块之一，在数学竞赛中占据极其重要的位置.特别是联赛改制以后，二试必考一道50分的数论大题，一试也会有一到两道数论方面的问题.数论与组合水平如何是大家能否获得联赛一等奖甚至更好成绩的关键.初等数论这块的竞赛问题涉及到的知识点极少，甚至可以说绝大部分同学在小学初中的培训中基本都接触过.但是限于初中的知识面和同学的年龄，考试中一般不出现较为深入、难度较高的数论问题.到了高中，大家将复习小学初中阶段的数论知识，并将其中的很多知识更为理论化、系统化.高中的数论问题难度也会明显增高.但是在数论这一模块中，我们并不提倡大家过多地掌握很多高深的数论知识，而是提倡大家真正去灵活熟练地运用最基本、最重要的数论基础知识和重要定理来解决问题.由于同学们在小学、初中都已经学过不少关于初等数论的初步知识，所以这里我们把大家比较熟悉的知识都罗列在下面，对其中大部分定理将不给出证明，直接给出结论.如果不特别说明，本讲中所有字母均代表正整数.一、整除1．整除的定义两个整数a和b(b≠0)，若存在整数k，使得a=bk，我们称a能被b整除，记作b|a．此时把a叫做b的倍数，b叫做a的约数．如果a除以b的余数不为零，则称a不能被b整除，或b不整除a，记作baŒ．2．数的整除特征（1）1与0的特性：1是任何整数的约数，即对于任何整数a，总有1|a．0是任何非零整数的倍数，a≠0，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（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．整除的几条性质（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高一·联赛班·第4讲·学生版2二、带余除法对于任一整数a及大于1的整数m，存在唯一的一对整数q,r(0≤rm)，使得a=qm+r成立，这个式子称为带余除法式。q就是a除以m的不完全商，r就是a除以m的余数。证明：取由所有m的整数倍排成一列数…,－km,…,－2m,－m,0,m,2m,…,km,…(k∈N)a必介于该数列中的某两个相邻数之间，即存在整数q，使qm≤a(q+1)m。令r=a－qm，则0≤rm，于是有a=qm+r如还有整数q1,r1满足a=q1m+r1(0≤r1m)，则q1m+r1=qm+rm(q1－q)=r－r1若q1≠q，则|m(q1－q)|≥m，而|r－r1|m，这是不可能的.这说明q1=q,于是r1=r。三、基本定义：奇数、偶数、素数、合数、最大公约数、最小公倍数、完全平方数、阶乘1、将全体整数分为两类，凡是2的倍数的数称为偶数，否则称为奇数.因此，任一偶数可表为2m（m∈Z），任一奇数可表为2m+1或2m－1的形式.奇、偶数具有如下性质：（1）奇数±奇数=偶数；偶数±偶数=偶数；奇数±偶数=奇数；偶数×偶数=偶数；奇数×偶数=偶数；奇数×奇数=奇数；（2）任何一个正整数n，都可以写成lnm2的形式，其中m为非负整数，l为奇数.2、一个大于1的整数n如果没有真因子（大于1而小于n的约数），则称n为素数；否则称它为合数.素数的性质1：若p为素数，a,b为整数,如p|ab,那么p必整除a,b之一.素数的性质2：素数有无穷多个.(欧几里得在公元3世纪给出了一个经典的利用反证法的证明)3、设a,b,…,c是有限个不全为零的整数，同时整除它们的整数叫做它们的公约数（或公因子）.这些数中必有一个最大的，称为a,b,…,c的最大公约数，记作（a,b,…,c）.如果（a,b,…,c）=1，则称a,b,…,c是互素的；同时为它们的倍数的整数叫做它们的公倍数，其中正的公倍数中最小的那个称为最小公倍数，记作[a,b,…,c]4、一个数如果是另一个整数的完全平方，那么我们就称这个数为完全平方数，也叫做平方数.性质1：完全平方数的末位数只能是0,1,4,5,6,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的阶乘为!(1)(2)321nnnn四、自然数唯一分解定理、约数个数公式每个大于1的自然数n均可分解为有限个素数之积，如不计素数在乘积中的顺序，那么这种分解方式是唯一的（证明略）.将相同的素因子写在一起，那么n可以唯一地写成：1212kknppp其中12,,...,kppp为互不相同的素数，而12,,...,k是正整数，上式称为n的标准分解.自然数n的正约数个数公式为12()(1)(1)...(1)kn高一·联赛班·第4讲·学生版3例题精讲【例1】（热身问题）证明以上理论部分给出的一些性质：（1）、一个三位以上的整数能否被7（11或13）整除，只须看这个数的末三位数字表示的三位数与末三位以前的数字组成的数的差（以大减小）能否被7（11或13）整除．（2）奇数的平方都可表为8m+1形式，偶数的平方都可表为8m或8m+4的形式（m∈Z）（3）素数的性质1：若p为素数，a,b为整数,如p|ab,那么p必整除a,b之一.（4）证明约数个数公式.【例2】（1）如自然数n的正约数个数为奇数，证明n为平方数.（2）(,)[,]ababab高一·联赛班·第4讲·学生版4【例3】（1）证明21nn不是平方数；（2）证明连续三个自然数之积非平方数.（3）证明十进制表示中有3个数位为1，其它数位均为0的数n非平方数【例4】记2()41fnnn，证明：（1）有无穷多个正整数n使得f(n)为合数；（2）有无穷多个正整数n使得43|f(n)高一·联赛班·第4讲·学生版5【例5】试求所有这样的质数p,使得211p恰有6个不同的正约数.【例6】三角形三边长均为质数，证明：其面积不可能为整数.高一·联赛班·第4讲·学生版6【例7】证明：9959971992|997995【例8】试找出最小的自然数n，使它的立方的十进制表示中末三位数字恰为888.高一·联赛班·第4讲·学生版7【例9】p,q均为正整数,使得11111123413181319pq试证:1979︱p【例10】以d(n)表示n的正因子的个数，试确定S=19901()kdk的奇偶性【例11】自然数n恰有12个正因数，将它们由小到大排列：12121...dddn且411248()dddddd，求n.高一·联赛班·第4讲·学生版8大显身手1．可以对写在黑板上的四位数进行如下形式的操作：或者将它的某两个相邻数字同时加1，如果它们都不等于9；或者将它的某两个相邻数字同时减1，如果它们都不等于0，试问能否通过这样的操作将1234变为2002？2．可以将1-16写成一行，使得每两个相邻数之和均为完全平方数；但不能写成一圈仍满足此条件.3．设n为正整数，若21,31nn均为完全平方数，试确定5n+3是否为合数？如可能为素数，试给出n的一个可能值.高一·联赛班·第4讲·学生版94．试求所有满足3()pqpq的质数对(,)pq.5．设a,b为正整数，且11baab为整数，证明：(,)abab高一·联赛班·第4讲·学生版10学习之外“世界最迷人的数学难题”评选揭晓“几何尺规作图问题”获奖理由：这里所说的“几何尺规作图问题”是指做图限制只能用直尺、圆规，而这里的直尺是指没有刻度只能画直线的尺.“几何尺规作图问题”包括以下四个问题1.化圆为方－求作一正方形使其面积等於一已知圆；2.三等分任意角；3.倍立方－求作一立方体使其体积是一已知立方体的二倍；4.做正十七边形.以上四个问题一直困扰数学家二千多年都不得其解，而实际上这前三大问题都已证明不可能用直尺圆规经有限步骤可解决的.第四个问题是高斯用代数的方法解决的，他也视此为生平得意之作，还交待要把正十七边形刻在他的墓碑上，但後来他的墓碑上并没有刻上十七边形，而是十七角星，因为负责刻碑的雕刻家认为，正十七边形和圆太像了，大家一定分辨不出来.编者注：另一类有趣的作图问题是：仅用直尺或仅用圆规作图；“生锈圆规问题”（圆规仅能按照规定大小作圆）.上世纪80年代张景中院士成功解决了美国数学家匹多教授（著名的匹多不等式的提出者）给出的若干生锈圆规作图问题.“蜂窝猜想”获奖理由：四世纪古希腊数学家佩波斯提出,蜂窝的优美形状,是自然界最有效劳动的代表.他猜想,人们所见到的、截面呈六边形的蜂窝,是蜜蜂采用最少量的蜂蜡建造成的.他的这一猜想称为蜂窝猜想,但这一猜想一直没有人能证明.1943年,匈牙利数学家陶斯巧妙地证明,在所有首尾相连的正多边形中,正多边形的周长是最小的.1943年,匈牙利数学家陶斯巧妙地证明,在所有首尾相连的正多边形中,正多边形的周长是最小的.但如果多边形的边是曲线时,会发生什么情况呢?陶斯认为,正六边形与其他任何形状的图形相比,它的周长最小,但他不能证明这一点.而黑尔在考虑了周边是曲线时,无论是曲线向外凸,还是向内凹,都证明了由许多正六边形组成的图形周长最小.他已将19页的证明过程放在因特网上,许多专家都已看到了这一证明,认为黑尔的证明是正确的。高一·联赛班·第4讲·学生版11附录：高一秋季、寒假联赛班讲义目录（初定）编排思想：尽量跟教材进度走，为此在秋季第四、五讲插入了数论的初步知识，以此来调控函数部分的进度.寒假班则完整地讲授组合部分，目标是达到能够轻松解决高考、联赛一试、自主招生级别的组合问题并能够解决二试及冬令营中中下等难度的组合问题.秋季班第一讲集合第二讲一元二次函数第三讲函数的三性第四讲数论初步（1）第五讲数论初步（2）第六讲基本初等函数：幂、指数、对数第七讲含绝对值函数与函数最值第八讲函数综合与总结第九讲函数迭代与函数方程初步第10讲三角函数入门第11讲三角恒等变换第12讲正弦定理与余弦定理第13讲几何题的三角证法初步第14讲三角不等式第15讲向量与几何寒假班第一讲计数（1）简单的排列第二讲计数（2）复杂一些的排列第三讲组合恒等式第四讲抽屉原理第五讲稍复杂的组合题第六讲概率初步（侧重应用组合来解决的）第七讲数学思想（1）极端性原则