搜索
数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用刘刘刘娟娟娟新疆师范大学数数数学学学科科科学学学学学学院院院,2015.6刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一章整数的可除性1.1.整整整除除除的的的概概概念念念带带带余余余数数数除除除法法法定定定义义义.设a,b是任意两个整数,其中b̸=0,则存在一个整数q使得等式a=bq(1)成立,我们就说b整除a或a被b整除,记作b|a,此时把b叫做a的因数,把a叫做b的倍数.如果(1)里的整数q不存在,我们就说b不能整除a或a不被b整除,记作-a.定定定理理理1(传传传递递递性性性)若a是b的倍数,b是c的倍数,则a是c的倍数,也就是说b|a,c|b=⇒c|a.定定定理理理2若a,b都是m的倍数,则a±b也是m的倍数.定定定理理理3若a1,a2,······,an都是m的倍数,q1,q2,···,qn是任意n个整数.则q1a1+q2a2+···+qnan是m的倍数.定定定理理理4若a,b是两个整数,其中b0,则存在两个整数q及r,使得a=bq+r,(0≤rb)成立,而且q及r是唯一的.例例例.设m,n为正整数,m2,证明:(2m−1)-(2n+1).证证证明明明：：：(1)nm时(m2),显然有2m−12n+1,故此时(2m−1)-(2n+1).(2)当n=m时,由于2n+12m+1−2,故12n+12m−12,所以此时(2m−1)-(2n+1).(3)当nm时,可以用带余除法转换到上述特殊情形.设n=mq+r,(0≤rm),而q≥0,由于2n+1=(2mq−1)2r+2r+1,而(2m−1)|(2mq−1),(2m−1)-(2r+1)(因0≤rm),从而,当nm时有(2m−1)-(2n+1).综合(1),(2),(3)得(2m−1)-(2n+1).刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一部分数的整除性1.1.奇奇奇数数数与与与偶偶偶数数数整数中能被2整除的整数称为偶数,不能被2整除的整数称为奇数,即偶数集为{0,±2,±4,±6,···};奇数集为{±1,±3,±5,···}因此,有奇数与偶数的基本性质:性性性质质质1.1.(1)偶数±偶数=偶数;(2)奇数±奇数=奇数;(3)偶数±奇数=奇数.反复利用(1),(2),(3)得到一般结论:奇数个奇数的和是奇数;偶数个奇数的和是偶数;任意正整数个偶数的和是偶数.刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一部分数的整除性性性性质质质1.2.(1)偶数×偶数=偶数;(2)奇数×奇数=奇数;(3)偶数×奇数=偶数.同样地，有:任意多个奇数的积是奇数,至少有一个乘数是偶数的积是偶数.性性性质质质1.3.(1)如果一个偶数能被奇数整除,那么商必是偶数;(2)两个连续整数的积n(n+1)是偶数.刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一部分数的整除性例例例1.在一条线段的内部任取n个点,将这些点及线段端点依次记为A0,A1,···,An+1,并且将端点A0染上红色,An+1染上蓝色,其余各点染上红色或蓝色,称两端颜色不同的线段AiAi+1(0≤i≤n)为“好线段”.证明:好线段的条数为奇数.解解解.将红色的点记为+1,蓝色的点记为−1.考虑每条线段AiAi+1的两端的数的乘积,当且仅当AiAi+1是好线段时,乘积是−1.将上述n+1个乘积(i=0,1,2,···,n)乘起来,这时A0,An+1各出现，中间的点Ai(1≤i≤n),各出现两次,于是n+1个乘积的积为1×(−1)=−1.这表明n+1个乘积中，乘积为−1的个数是奇数,即好线段的条数为奇数.刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一部分数的整除性例例例2.证明:从1,2,···,100中任意取51个数，其中必有一个数是另一个数的倍数.证证证明明明：：：将1,2,···,100表示成2k·j的形式,其中k为非负整数,j为正奇数.显然j只有50种可能,即1,3,5···,99.将j相同的数放在同一组,这样就得到50个组.{1,2,4,8,16,32,64},{3,6,12,24,48,96},···{99}.同一组中的两个数字2k·j与2h·j(kh),由于j相同,一个是另一个的倍数.现在任取51个数,由抽屉原理,这51个数中必有两个在同一组,所以必有一个是另一个的倍数.刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一部分数的整除性1.2.带带带余余余除除除法法法1.2.1.带带带余余余除除除法法法定定定理理理.若a,b是两个整数,其中b0,则存在两个整数q及r,使得a=bq+r,(0≤rb)成立,而且q及r是唯一的.例例例.设m,n为正整数,m2,证明:(2m−1)-(2n+1).证证证明明明：：：(1)nm时(m2),显然有2m−12n+1,故此时(2m−1)-(2n+1).(2)当n=m时,由于2n+12m+1−2,故12n+12m−12,所以此时(2m−1)-(2n+1).(3)当nm时,可以用带余除法转换到上述特殊情形.设n=mq+r,(0≤rm),而q≥0,由于2n+1=(2mq−1)2r+2r+1,而(2m−1)|(2mq−1),(2m−1)-(2r+1)(因0≤rm),从而,当nm时有(2m−1)-(2n+1).综合(1),(2),(3)得(2m−1)-(2n+1).刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一部分数的整除性1.2.2.最最最小小小公公公倍倍倍数数数与与与最最最大大大公公公约约约数数数定定定义义义1.2.如果a是bi(i=1,2,···,n)的倍数，那么a称为b1,b2,···,bn的公倍数.公倍数中最小的一个称为最小公倍数,记为[b1,b2,···,bn].定定定义义义1.3.如果b是ai(i=1,2,···,n)的约数，那么b称为a1,a2,···,an的公约数.公约数中最大的一个称为最大公约数,记为(a1,a2,···,an).如果两个数的最大公约数是1,那么这两个数称为互质.特别地，根据定义得到:(a,1)=1.即1与任意一个自然数互质.刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一部分数的整除性例例例1.数列1001,1004,1009的通项是an=n2+1000,其中n∈N+.对于每一个n,用dn表示an与an+1的最大公约数,求dn的最大值,其中n取一切正整数.解解解：：：设dn=(1000+n2,1000+(n+1)2),则dn|(1000+n2),dn|(1000+(n+1)2).所以dn|(1000+(n+1)2−1000−n2),即dn|(2n+1).又因为2(1000+n2)=n(2n+1)+2000−n,所以dn|((2n+1)+2(2000−n)),即dn|4001.所以1≤dn≤4001.又当n=2000时,有1000+n2=1000+20002=1000·4001,1000+(n+1)2=1000+(2000+1)2=1001·4001.所以dn能得到4001,即(dn)max=4001.刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一部分数的整除性例例例2.正整数a和b互素,证明:a+b与a2+b2的最大公约数等于1或2.证证证明明明：：：设d是a+b与a2+b2的最大公约数,则有d|(a+b),d|(a2+b2),于是由(a+b)2−(a2+b2)=2ab,得d|2ab.又因为2a(a+b)−2ab=2a2,2b(a+b)−2ab=2b2.所以,d|2a2,d|2b2,因此,d是2a2,2b2的公约数.由题设,(a,b)=1,则有,(a2,b2)=1.所以,2a2和2b2不可能被大于2的数整除.因而,d≤2.即a+b与a2+b2的最大公约数等于1或2.刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一部分数的整除性1.2.3.裴裴裴蜀蜀蜀恒恒恒等等等式式式带余除法不仅可以实际求出(a,b),而且还可以导出一个在理论上极为重要的裴蜀恒等式:(a,b)=ua+vb其中u,v是两个整数.裴蜀恒等式还可以推广到多个数的最大公约数:对于任意的正整数a1,a2,···,an存在整数k1,k2,···,kn,使得k1a1+k2a2+···+knan=(a1,a2,···,an)刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一部分数的整除性例例例.两个容器,一个容量为27L,另一个为15L,如何利用它们从一桶油中倒出6L的油来？解解解：：：因为(27,15)=3,且27=1×15+1215=1×12+13从而3=15−1×12=15−1×(27−1×15)即3=2×15−27于是6=4×15−2×27这表明需往小容器例里倒4次油,每次倒满就向大容器里倒，大容器满了就往桶里倒.这样在大容器第2次倒满时,小容器里剩下的就是6L.刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一部分数的整除性1.3.质质质因因因数数数分分分解解解定定定理理理质质质因因因数数数分分分解解解定定定理理理.每一个大于1的整数n都能分解成质因数的乘积,并且若不考虑因数的次序,则分解的方式是唯一的,即n可以唯一地表成n=p𝛼11p𝛼22···p𝛼kk其中p1,p2,···,pk为不同的质数,𝛼1,𝛼2,···,𝛼k∈N.证证证明明明.首先用数学归纳法证明n可分解为质因数的乘积.n为质数时无需分解.假设n为合数并且小于n的数均可以分解为质因数的积.由于n为合数,存在真因数n1及n2(nn1),满足n=n1n2,且n1n,n2n.由归纳假设,n1,n2都可以分解为质因数的积,因而n可分解为质因数的积.其次,证明n的分解式是唯一的.若有n=p1p2···ps=q1q2···qt(1)这里pi,qj(1≤i≤s,1≤j≤t)均为质数(允许其中有相同的),则p1|q1q2···qt,则p1必整除q1,q2,···,qt中某一个,不失一般性,可假设p1|q1,但q1是质数,所以p1=q1.在式(1)两边约去p1(=q1)得p2···ps=q2···qt仿照上面讨论可得p2=q2,···,ps=qs,并且s=t于是n的分解式是唯一的.刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一部分数的整除性推推推论论论1.1.如果c|ab,(c,a)=1,那么c|b.推推推论论论1.2.如果a|n,b|n,(a,b)=1,那么ab|n.推推推论论论1.3.如果a,b是正整数,那么ab=(a,b)[a,b].例例例1.证明:4个连续自然数的乘积加上1一定是平方数.证证证明明明.设这4个数为n,n+1,n+2,n+3,则n(n+1)(n+2)(n+3)+1=(n2+3n)(n2+3n+2)+1=(n2+3n+1)2是平方数.这说明连续4个正整数的积一定不是平方数.思思思考考考:3个连续自然数的乘积是否是平方数？刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一部分数的整除性例例例2.证明:当2n+1为质数时,n一定是2的整数幂.证证证明明明.设n=2k·j,k为非负整数,j为正奇数.若j1,则2n+1=(22k)j+1j=(22k+1)((22k)j−1)−((22k)j−2)+···+1j−122k+1是2n+1的真因数,因而2n+1是合数.所以2n+1为质数时必有j=1,即有n=2k.思思思考考考:2n−1为质数时,n是什么数？刘刘刘娟娟娟数数数论论论在在在竞竞竞赛赛赛中中中的的的应应应用用用第一部分数的整除性1.4.质质质数数数基基基本本本结结结论论论1.4.质数的个数是无限的.定定定理理理1.1.当a与b互质时,算数级数(即等差数列)a,a+b,a+2b,a+3b,·