初等数论高中数学联赛加试大纲对的要求

高中数赛(加试)大纲对初等数论的要求同余,得辗转相除法,裴蜀定理,完全剩余类,二次剩余,不定方程和方程组,函数[x],费马小定理,格点及其性质,无穷递降法,欧带*号的内容加试中暂不考,但冬令营中可能考引初等数论是研究整数最基本的性质的一门重要数学课程,它在国内外数学竞赛,特别是中IMO所扮演的角色也是举足轻重的.整除性理论是初等数论中最基础的部分,它建立在带余除法的基础上.整除理论的中心是算术基本定理和最大公约数理论,而这些理论的不同建立方式还反映出近代数学中十分重要的数学思想,概念和方法.回到,我们这里讲的是竞赛数学中用到的整除知识,在联赛中纯粹的整除题目很少出现,但是一些整除中常用的方法技巧有时会用到;在比联赛更高级别的CMO中,数论问题经常出现,有时就是证明整除问题;在IMO中,整除方面的试题就了,在早期的IMO中关于整除方面的试题十分简单,随着数学竞赛活动的发展和数学竞赛体制的日趋完善,近几年这方面的试题难度加深.总而言之,竞赛数学中涉及到的整除知识都十分简单,但是有的竞赛试题并不简单.因此作为竞赛班的学生,我们还需要一定量的练习来巩固所掌握的知识,做到融汇贯通,运用自如.１知识扫一、整数的基本整数集关于加,减,乘运算的封整数的和,差,积仍为整数(两个整数的商不一定是整数能被2整除的整数称为偶数,可表示为2n(nZ)的形式,不能被2整除的整数称为奇数,可表示为2n1(nZ)的形式.对于奇数和偶数有一下性任意多个偶数的和,差,积仍为偶数奇数个奇数的和,差仍为奇数偶数个奇数的和,差仍为偶数奇数与偶数的和为奇数,积为偶数若有限个整数之积为奇数,则其中每个整数都是奇数;若有限个整奇数的平方都可以表示为8n1(nZ)的形式,表示为4n(nZ的形式整数集的离任何两个连续整数之间不再有其他任何两个xy之间的距离至少为1,即xyx1y任何一个整数有限集中必有最大数和最小数２二、整除的定义和基本性整除的设a,b(b0是整数,若存在整数q,使得abq,则称b整除a,或a能b整除,记为ba.这时b叫做a的因数或约数a叫做b的倍数整除的基本若ba,则b(a),ba,(baba若ab,bc,则acnn若a,bixiZi1,2,3,⋯n且abi,则abixii若a,bZ,且ab,则对于任何非零整数m,都有ambm;反之亦成立ab,ba,则a0若a,b互素,且abc,则acnp是素数,pai,则至少有一个ai(i1,2,⋯n使得paiin个连续整数中有且仅有一个是n的倍数 个连续整数的乘积一定能被n!整除.设a,b是整数(b0),则存在q和r,使得abqr,其中0rb并且整数q和r由上述条件唯一确定证明:(存在性)取bq是不超过a的b的最大倍数,则有bqab(q1)rabq,则0rb.于是我们证qr的存在性.(唯一性)如果还qr,abqr,且0rb,则b(qqrr.故 brr,但0rrb,因此rr0即rr.于是qq ３例题分证明6n(n1)(2n1),其中n求整数a,b,c,使它们满足不等式a2b2c23ab3b2c试求方程2x2y23x2y的正整数解４设n,f(nn(n21)(n25n26,求证

f(n)设n是正偶数,证明:(2n1)不能整除(3n设mn为正整数,m2.证明:(2m1)不能整除(2n+1)５1n为奇数,证明:n 1

n1)[(n1)!] 设1111 p,p,qN.证明:1979p F22k1k0.证明:若mnmnN*,F|F2) ６n为正整数,求证512|32n32n224n1)设ax0by0是形如axbya,bxy且不全为零)的数中最小的正数.证明:对于任意的x,y恒有:(ax0by0)|(ax证明:对于任何正整数n和k,f(nk成若干个连续自然数的乘积

4nk10都不能７证明:存在无穷多个正整数n,使得n|2n2),(n1)|2n1求最大的正整x,使得对于任意正整数y都有:x|(7y12y1p是质数,xyz满足0xyz余数相等.证明:xyz|x2y2z2

p,x3,y3,z3p８n对于任何正整数n和k,F(nkr2k1求证F(n,1)|F(nkfx是周期函数,T和1f(x的周期且0T1.证明1若T为有理数,则存在p,fx的周期p若T 为无理数.证明:存在各项均为无理数的数列{an}满足如下条件1anan10且每个an(n1,2,)都是f(x)的周期.９练习题证明对于任意的正整数n3804(n3n)(58n434n2a,b,cd为整数,(ac|abcd,则(ac|adbca,b都是正整数,(a2ab1)|b2ab1),则ab整数a,b,cd满足n2abcdn1)2,其中n1n.证明adamn都是正整数a1,且(am1)|an1),证明m|n证明4003|1232001200220034002正整数a,b,c,d都可以被正整数abcd整除.证明:abcd证明对于每个正整数n,n2 整除设

,

,,

是正整数,30

n

,证明30

5ai5求最大的正整数n,使(n10)|n3100)设a11,a23除的n的值

n3)an1n2)an.求所有使an可被11已知n个互不相等的正整数a,aa,a都能整除10k(kN 求证:

E123,200Ga1a2a3a100GE,且G具有以性质:(1)对任何1ij100恒有aia

10080证明:G中所有元素的平方和为一定值且G中奇数的个数是4的倍数给定n1个正整数,其中每个都不大于2n求证:其中必有两个数a与b,使ab设a,bN,且nN都有(annbnn),则ab知识扫四、最大公约数和最小公倍数的定义和性质1:a1a2,⋯an(n2)n个整数若d是这n个整数中每个数的约数,则称 为这n个整数的公约数由于1 是任意整数的约数,且任何非零,数的约数只有有限多个,因此我们有:定义2:不全为零的n个整数a1,a2,⋯,an(n2)的一切公约数中最数d叫做这n个整数的最大公约数,记作(a1a2,⋯an定义3:如果(a1a2,⋯an1,则称aa,⋯an互质,a1a2,⋯an中 意两个整数都互质,则称a1a2,⋯an两两互质.显然a1a2,⋯an两两互质,这n个数必互质,反之则不真.4:设a1a2,⋯an(n2是n个非零整数,若整数m是这n个整数每一个数的倍数,则称m 为这n 最小的一个叫做这n个整数的最小公倍数,记作a,a,⋯,a.

不同时为零的整数 和b的任一公约数是它们最大公约数的约数(0,b)b(b0)设a,b是不同时为零的整数,则对任意整数k有(ab)(abaka,b是不全为零的整数,则对任意非零整数k有(kakbk(a,b若(ab1ac不全为零,则(abcac若abc,(ab)1,则ac设a1a2,⋯,an(n2是n个不全为零的整数,则(a1,a2,,an)(|a1|,|a2|,,|an|)由此可见,对于最大公约数问题,只需对非负整数讨论就行了若a1a2,⋯an(n2)是n个正整数,且(a1a2d2d2a3d3n ad.则aa,⋯adn a,a,⋯,

a,a,⋯,a, ,

,⋯,

k

k a1a2,⋯an(n2)n个不全为零的整数则存在n个整x,x,⋯,x,使得axax⋯a a,a,⋯,a 1 2 n (a1a2,⋯,an1的充要条件是nxx,⋯,xn使得 axax⋯ax1 2 n对任意的正整数有mama,⋯mamaa,⋯

a a,a,⋯,a若m是a,a,⋯,a的公约数,则 1 2 n n m a和b均与m互素,ab也与m互素,即与m互素的整数关于乘法封闭.一般地,如果a1a2,⋯an均与m互素,则a1a2⋯an与m互素.(ab)[abab,特别地,若(ab1,则[abab设bb,⋯b是两两互素的正整数a是整数,若ba(1in, b1b2⋯bna,特别地,两两互素的正整数的最小公倍数等于它们的积n[a1a2m,[d2a3m,⋯,[dn1anm.则[a1a2,⋯,anmn2a,a,⋯,

a,a,⋯,a ,

,⋯,aa,a,⋯,

k

k 1若k是a1a2,⋯an的公倍数,则[a1a2,⋯an 设M是aa,⋯,an(n2)的任一正公倍数, [M,M,,M] ,(M,M,,M) (a1,a2,,an 五、得辗转相除设a,b为整数(b0),用带余除法可得一系列等式 abqr,0rb;brq0r0,0r0r 0 rrqr,0rr 1 qr,0r n1 r , n n则(a,b)(b,r)(r,r)⋯(r, )r 0实际上,因为brrr⋯,所以经过有限次(至多b次)带余除法后0 n总可以得到一个余数是零的等式,即r 0.我们称这种算法为n六、裴蜀定n1设a,b是整数,且d(ab则(abd的充要条件是存在整数uv,使得uavbd(1)欧氏算法不仅能在有限步内求出(ab,还能证明方程uavb(ab)有一组解uv,并能具体地求出这组解.将n1法倒回去:rn

rn1qnrn(a,b)rn

rq,这样就将(ab)示为"

整数+ 整数"的形式;再将

代入上式,n

nn n去 ,就能将(a,b)表示为" 整数+ 整数"的形式;如此进行n n n去,最终便求得(1)中一组解u,v例题分若r是1059,1417与2312被d除后的余数,且d1,求drn为小于50的正整数,求使代数式4n5和7n6有大于1的公约数的所有n的值.14n设n是正整数,证明: 不可约分证明:(n!1,n1)!1)若3nn(2n

可以写成有限的十进制小数的形式,求自然数 设k为正奇数,证明

(1k2knk)2数列an的通项是dn的最大值

n22008,nN.n记 nnn

,

,正整数a1a2,a49999,da1a2,a49,求d的最大值设T是由60100的所有正因数组成的集合,S是T的一个子集,中的元素,没有一个数是另一个数的倍数.求Card(S)的最大值正整数a,b互素,求(ab)和(a2b2)的最大公约数已知a,bN*ab667,[ab120(ab,求a,b的值在各项都是正整数的数列an中,对于 j,有(ai,aj)=(i,j) 明:对于一切iN*,都有

ina1a2,an,满足a1a2an2n,其中任意两个aa(ji)的最小公倍数都大于2n.求证a2n. 练习题

a

b设a,b是两个给定的正整数,使 是一个正整数 a证明:a和b的最大公约数不an求出使 5n

是非零可约分式的最小正整数n已知m是正整数.证明:m(m1)不是任何整数的幂已知正整数a1a2,a10满足不等式a1a2a10证明:[a1a2,a10]10a1 个正整数的和为101101,求它们最大公约数的最大可能值确定所有的三元正整数组(abc,使abcab

,

,,

是正整数n的全部正约数,1

n, 出使k4且d2d2d2d2n的所 k为大于1的整数,证明不能在kk的方格表内添入数字1,2,3,,k2,使得各行,各列的数字之和都是2的把8个不相等的正整数分别标在正方体的八个顶点,再在棱上标出两个顶点上数字的最大公约数,试问:能否使得所有棱上数字之和等于顶点上所有数字之和?,. k个正整数a,a,,a满足:1aa 时,[ai,aj]n.证明: P为大于3的素数,则可以选取不超过p1个互不相同 t正整数a1a2,at,使得

pai2的正整数次幂知识扫一、素数的定义及一些基本1一个大于1的正整数n,如果仅有1,n这两个正约数,那么n叫做2如果n有大于1而小于n的约数,那么n叫做合数3如果一个正整数n的一个p是质数,p叫n的质因数.大于1的整数必有质因数既为偶数又为素数的正整数只有p为素数,p整除n或者p与n互素设p为素数,如果pab,则a,b中至少有一个被p整除素数有无穷多个.(用反证法,假设素数有有限多个,记为p1,p2,,pn构造Np1p2pn二、算术基本定理(唯一分解定理设正n1那么必有np1p2ps,其中pj(1js是素数,且不计较,序的意义下分解式唯一.将分解式中相同的素数合并,np1p2pk,ppp为素数,并称之n的标准素 数分解式设ap1p2pk,bp1p2pk这里,为非负整数,那么 (a,b)p1p2pk,min(,),1jk [a,b]p1p2pk max(,),1jk 三、n的约数的标准分n的标准np1p2pk(p是互不相等的素数,N 整数d|n的充要条件是dp1p2pk,0,i1,2, 四、n的正约数的个数及正约数

记r(n)是n的正约数的个数,(n)是n的正约数之和,且n的标准为(1)式,则有

p11 p21 pk1r(n)(11)(21)(k1),(n) p1 p2 pk五、n为完全平方数的充要条n为完全平方数r(n)为奇六、数的一个判别设n1,且n不被不超过n的素数整除,则n是素数.七、n!的标准分解k为非负整数,记号akb表示b恰好被a的k次方整除,即akb不能bn是正整数p是素数pnp||n那(p,n)

n],[x]

表示不超过

的最大整数.且有

n!pp八、函数与费尔若n的标准分解为np1p2pk(p是互不相等的素数,N), 1,2,⋯n1n中与n互素的数的个数叫做n的欧拉函数,记为(n).k(n)

1).(可以用容斥原理证明费尔马小定理:p为素数a为整数,p(apa可以用数学归纳p,p10,p14都是素数,p求所有的素数p,使得4p21,6p21也是素数求三个素数,使它们的积是和的５倍已知方程x4px3q0有一整数根,pqaa求最小的自然数a和b(b1),使 aa求出所有不超过1000的素数p,这些p使2p1是自然数的已知方程x2pxq0的根均为整数,pq198,试求其根证明对于无穷多个素数p,方程x2x1py有整数解(xy数20!设f(x)axn xn1axa是整系数多项式.证明:若存 p能整除a(i0,1,2,⋯n1)但不能整除a,p2不能整除 (x)不能分解为两个整系数非零次多项式的乘积数列a1a2,满足a12而对于每个n2an等于a1a2⋯an11的最大素因数.证明该数列中任何一项都不等于5正整数n不小于3,正整xxx2x,pxxx 1 p证明:若r是素数,k为正整数,并且 p,则 证明对每个素p,有无穷多个n,p(2nn求证对于任何正整数n,都存在n个相继的正整数,它们都不是素数求证恰好存在唯一的一个整数列a1a2,a11a21a 1a n证明:通项为 4n1的数列an中含有无穷多个素数练习题正整数N(N1)的正约数的个数是奇数,N是完全平方数示正整数n的不同的正因数的个数.证明正整数 的正约数的个数不超过 用Sn表示数列1,2,3,2n中各项的最大奇因子之和,求Sn的值n:使nn1n2n3n4n5可以分成两个不相交的非空子集合,并且一个子集中所有元素的积与对给定的一个正整数n,设p(n)表示n的各位上的非零的数字的乘积,若Sp(1)p(2)p(999),则S的最大素因子是多少？如果pq是两个素数,并且qp2证明pq)pqqp若n是大于1的自然数,它恰好有r个不同的素因数,则(nn((n)是其欧拉函数);若n恰好有r个不同的奇素因数,则2r(n)证明:对于任意六个连续正整数,存在一个素数,使得这个素数能且只能整除这六个数之一.pp, 是不小于5的素数,p2p2p2可被24整除 对于怎样的k,可以找到这样的自然数,使其等于自己的k个互不相同知识扫定义:设m是一个给定的正整数,如果两个整数a,b用m除所得的余数相等,则称a,b对模m同余,记为:ab(modm).同余的基本性质a0(modm)m|若ab(modmbc(modm),则ac(mod若ab(modmcd(modm),则acbd(modmacbd(mod若acbc(modmc0,则ab(modm若mc1，则ab(mod(m,若ab(modmd|m,(d0)则ab(mod若ab(modmc0则acbc(mod若ab(modm1ab(modm2则ab(mod[m1m2若ab(modm),则(am)(bab(modmi12,n则

axibxi(xZ.特别地,对于整系

n多项式f(xaxi(aZ),若ab(modm),则f(a)f(b)(modi0 说明:在同余中还有如下知识点完简剩余题试证明:对于任xZ1x51x37x的值是整数 求所有的正整数n,使得1n2n3n4n0(mod5)证明对于任何非负整数k,26k136k156k10(mod7求 2005的末三位数字数列a定义如下:a1,a2, aa2 则a2007 (mod7)p是大于5的质数,p230的余数若存在正整数n使55na32n0(mod2001).求最小的正整数a8.(1)确定所有的正整数n,使得2n10(mod7).(2)证明对于所有的正整数n2n1不能被7整除 设整系数多项式fxaxnaxn1 f(0),f(1,f(2006)都不2007整除,fx0没有整数根已知aiZ(i1,2,,10证明:x1x2,x10,使所有的xi1,0,1,并且ai

0(mod1001)对于自然数n,只要n|an1,就有n2|an1,那么称n具有性质p证明:(1)每个质数n都具有性质p存在无穷多个非素数n具有性质p已知a

29,求a除以100的余数

k个整数x1x2,⋯xk.证明:k个数中一定可以找到连续若干个(可以是一个)数,使得它们的和为k的整数倍.知识扫不定方程(组),是指未知数的个数多于方程(组)的个数,并且未知数受到某些条件限制(如整数解,正整数解等等)的方程(组).对于一个一般的不定方程(组),通常没有统一的解法,必须对不定方程(组)的具体形式今天我们探讨一下几种不定方程的解题模式一次不定方最简单的不定方程是整系数方程axbyc(ab0)上述方程通常称为二元一次不定方程定理１二元一次不定方程(1)的系数都是整数,其有整数解的充要条件是(a,b)c.定理２若(a,b)1,且x0,y0为(1)的一组解,则方程(1)的全部解为xx0btyy0at.如何证明这两个定理勾股方程x2y2z2这是一个相当特殊的三元二次不定方程,几何意义鲜明,应用比较广泛.由方程的构成方式可知我们只用讨论其正整数解即可.定理３方程(2)满足xy1,2y的全部正整数解xyz可以xa2b2,y2abza2b2,a,b是满ab0a,b一奇一偶且(ab＝１的任意整数.思考:如何证明这个定理Pell二元二次不定方程本质上归结为（双曲型）方程 c的究,其中d,cZ,且非完全平方数,而c0.此种方程的一个特殊形式是x2dy21――(3)最为重要,也最为基础,方程(3)Pell方程.能够证明方程(3)有无穷多组正整数解,设x1,y1)是(3)中的正整数解x,中使xy最小的解,称x1,y1)为最小解.则(3)的全部正整数解由 x1[(x

)n(x

d)ndd 2d

―－(4)给出n1,2,3).y [(x d)n(x d)nd d

Pell方程在竞赛中主要用于证明问题有无穷多个解,实际上可以对于d用尝试发求出一组正整数解x1,y1),无论x1,y1)是否为最小解,由(4)给出方程的无穷多组解.同余分解不定方程虽然没有固定套路,但是大致思想方法还是有的,对于方程的解是整数的这类不定方程运用同余分析法是一种很好的思考方法.我们在选取适当的模后,往往能找到方程的解应满足的某些必要条件,甚至可以推出方程无整数解,这样的论证灵活多变,在数学竞赛中尤为常见.无穷递此外还可以用因式分解,配方,根与系数的关系等方法处理不定程题求下列不定方程的整数解(1)143x77y187;(2)14x16y82;(3)7x19y213求证:单位圆上有无穷多个有理点求不定x23y2z2xy1的正整数解的通式求在直角坐标平面上以(199,0)为圆心,以199为半径的圆周上整点的求出方程x27y21的所有正整数解证明方程x3y3z3w31999有无穷多组整数解求下列方程的正整数解(1)1

14

111aaNxyz互不相等 x,yzx2y2z2的正整数解.证明:(1)x,y中至少有一个3的倍数;(2)x,yz中至少有一个5的倍数证明有无穷多个正整数n,使得 2n]是完全平方数求不定方程(1x2y28z36;(2)3y2x4x的正整数解是否存在非负整数a,b,使得3a2b若n4(mod9),证明不定方程x3y3z3n,没有整数解求所有正整数a,b,c满足(a!)(b!)a!b!知识扫(一 定设x是实数,不超过x的最大整数记为[x],称[x]为函数.将[x的整数部分,x[x]x的小数部分,记为(二 基本性x[x]x,0xx1[x]x[x][nx]n[x],{nx}{x},nxy,则xx时,[xx],x时,[xx若nNxR,则x[x] [x][y][x(三)函数的图对于函数y[x],其定义域是全体实数,值域是整数集.对于任意整数n,y[x]在[nn1)x轴的线段(不