数学竞赛知识点整理

（内部资料）第1页，共24页1/24上海市初中数学竞赛知识点整理*1.3组合恒等式（内部资料）第2页，共24页2/24（内部资料）第3页，共24页3/24*6．图论（内部资料）第4页，共24页4/24（内部资料）第5页，共24页5/24一．正整数A的p进制表示：012211apapapaAmmmm，其中1,,2,1},1,,2,1,0{mipai且01ma。而m仍然为十进制数字，简记为pmmaaaA)(021。二．整除在数学竞赛中如果不加特殊说明，我们所涉及的数都是整数，所采用的字母也表示整数。定义：设ba,是给定的数，0b，若存在整数c，使得bca则称b整除a，记作ab|，并称b是a的一个约数(因子)，称a是b的一个倍数，如果不存在上述c，则称b不能整除a记作ba。由整除的定义，容易推出以下性质：(1)若cb|且ac|，则ab|(传递性质)；(2)若ab|且cb|，则)(|cab即为某一整数倍数的整数之集关于加、减运算封闭。若反复运用这一性质，易知ab|及cb|，则对于任意的整数vu,有)(|cvaub。更一般，若naaa,,,21都是b的倍数，则)(|21naaab。或着iba|，则niiibca1|其中niZci,,2,1,；(3)若ab|，则或者0a，或者||||ba，因此若ab|且ba|，则ba；(4)ba,互质，若cbca|,|，则cab|；(5)p是质数，若naaap21|，则p能整除naaa,,,21中的某一个；特别地，若p是质数，若nap|，则ap|；(6)(带余除法)设ba,为整数，0b，则存在整数q和r，使得rbqa，其中br0，并且q和r由上述条件唯一确定；整数q被称为a被b除得的(不完全)商，数r称为a被b除得的余数。注意：r共有b种可能的取值：0,1，……，1b。若0r，即为a被b整除的情形；易知，带余除法中的商实际上为ba（不超过ba的最大整数），而带余除法的核心是关（内部资料）第6页，共24页6/24于余数r的不等式：br0。证明ab|的基本手法是将a分解为b与一个整数之积，在较为初级的问题中，这种数的分解常通过在一些代数式的分解中取特殊值而产生，下面两个分解式在这类论证中应用很多。若n是正整数，则))((1221nnnnnnyxyyxxyxyx；若n是正奇数，则))((1221nnnnnnyxyyxxyxyx；（在上式中用y代y）(7)如果在等式mkkniiba11中取去某一项外，其余各项均为c的倍数，则这一项也是c的倍数；(8)n个连续整数中，有且只有一个是n的倍数；(9)任何n个连续的整数之积一定是n!的倍数，特别地，三个连续的正整数之积能被6整除；三．数的性质1．奇数、偶数有如下性质：(1)奇数奇数=偶数，偶数偶数＝偶数，奇数偶数＝奇数，偶数偶数＝偶数，奇数偶数＝偶数，奇数奇数＝奇数；即任意多个偶数的和、差、积仍为偶数，奇数个奇数的和、差仍为奇数，偶数个奇数的和、差为偶数，奇数与偶数的和为奇数，和为偶数；（2）奇数的平方都可以表示成18m的形式，偶数的平方可以表示为m8或48m的形式；（3）任何一个正整数n，都可以写成lnm2的形式，其中m为负整数，l为奇数。（4）若有限个整数之积为奇数，则其中每个整数都是奇数；若有限个整数之积为偶数，则这些整数中至少有一个是偶数；两个整数的和与差具有相同的奇偶性；偶数的平方根若是整数，它必为偶数。2．完全平方数及其性质能表示为某整数的平方的数称为完全平方数，简称平方数。平方数有以下性质与结论：（1）平方数的个位数字只可能是0,1，4,5，6,9；（2）偶数的平方数是4的倍数，奇数的平方数被8除余1，即任何平方数被4除的余数只有可能是0或1；（3）奇数平方的十位数字是偶数；（4）十位数字是奇数的平方数的个位数一定是6；（5）不能被3整除的数的平方被3除余1，能被3整数的数的平方能被3整除。因而，平方数被9也合乎的余数为0,1，4,7，且此平方数的各位数字的和被9除的余数也只能是0,1，4,7；（6）平方数的约数的个数为奇数；（7）任何四个连续整数的乘积加1，必定是一个平方数。（8）设正整数ba,之积是一个正整数的k次方幂（2k），若（ba,）＝1，则ba,都是整数的k次方幂。3.整数整除性的一些数码特征（即常见结论）（1）若一个整数的未位数字能被2（或5）整除，则这个数能被2（或5）整除，否则不能；（内部资料）第7页，共24页7/24（2）一个整数的数码之和能被3（或9）整除，则这个数能被3（或9）整除，否则不能；（3）若一个整数的未两位数字能被4（或25）整除，则这个数能被4（或25）整除，否则不能；（4）若一个整数的未三位数字能被8（或125）整除，则这个数能被8（或125）整除，否则不能；（5）若一个整数的奇位上的数码之和与偶位上的数码之和的差是11的倍数，则这个数能被11整除，否则不能。4.质数与合数及其性质1．正整数分为三类：（1）单位数1；（2）质数（素数）：一个大于1的正整数，如果它的因数只有1和它本身，则称为质（素）数；（3）如果一个自然数包含有大于1而小于其本身的因子，则称这个自然数为合数。2．有关质（素）数的一些性质（1）若1,aZa，则a的除1以外的最小正因数q是一个质（素）数。如果aq，则aq；（2）若p是质（素）数，a为任一整数，则必有ap|或（pa,）＝1；（3）设naaa,,,21为n个整数，p为质（素）数，且naaap21|，则p必整除某个ia（ni1）；（4）（算术基本定理）任何一个大于1的正整数a，能唯一地表示成质（素）因数的乘积（不计较因数的排列顺序）；（5）任何大于1的整数a能唯一地写成kipppakakaa,,,2,1,2121①的形式，其中ip为质（素）数（)(jippji）。上式叫做整数a的标准分解式；（6）若a的标准分解式为①，a的正因数的个数记为)(af，则)1()1)(1()(21kaaaaf推论1.若a的标准分解式是（1）式，则d是a的正因数的充要条件是：kiapppdiikk,,,2,1,0,2121（2）应说明（2）不能称为是d的标准分解式，，其原因是其中的某些i可能取零值（d也有可能不含有某个素因数ip，因而0i）推论2.设bca，且1),(cb，若a是整数的k次方，则cb,也是整数的k次方。特别地，若a是整数的平方，则cb,也是整数的平方。四．最大公约数与最小公倍数最大公约数与最小公倍数是数论中的一个重要的概念，这里我们主要讨论两个整数互素、最大公约数、最小公倍数等基本概念与性质。定义1.（最大公约数）设ba,不全为零，同时整除ba,的整数（如1）称为它们的公约数。（内部资料）第8页，共24页8/24因为ba,不全为零，故ba,只有有限多个，我们将其中最大一个称为ba,的最大公约数，用符号（ba,）表示。显然，最大公约数是一个正整数。当（ba,）＝1（即ba,的公约数只有1）时，我们称a与b互素（互质）。这是数论中的非常重要的一个概念。同样，如果对于多个（不全为零）的整数cba,,,，可类似地定义它们的最大公约数（cba,,,）。若（cba,,,）＝1，则称cba,,,互素。请注意，此时不能推出cba,,,两两互素；但反过来，若（cba,,,）两两互素，则显然有（cba,,,）＝1。由最大公约数的定义，我们不难得出最大公约数的一些简单性质：例如任意改变ba,的符号，不改变（ba,）的值，即),(),(baba；（ba,）可以交换，（ba,）＝（ab,）；（ba,）作为b的函数，以a为周期，即对于任意的实数x，有（axba,）＝（ba,）等等。为了更详细地介绍最大公约数，我们给出一些常用的一些性质：（1）设ba,是不全为0的整数，则存在整数yx,，使得),(babyax；（2）（裴蜀定理）两个整数ba,互素的充要条件是存在整数yx,，使得1byax；事实上，条件的必要性是性质（1）的一个特例。反过来，若有yx,使等式成立，不妨设dba),(，则bdad|,|，故axd|及byd|，于是)(|byaxd，即1|d，从而1d。（不作要求）（3）若bmam|,|，则),(|bam，即ba,的任何一个公约数都是它们的最大公约数的约数；（4）若0m，则),(),(bammbma；（5）若dba),(，则1,dbda，因此两个不互素的整数，可以自然地产生一对互素的整数；（6）若1),(,1),(mbma，则1),(mab，也就是说，与一个固定整数互素的整数集关于乘法封闭。并由此可以推出：若1),(ba，对于0k有1),(bak，进而有对0l有1),(lkba。（内部资料）第9页，共24页9/24（7）设acb|，若1),(cb，则ab|；（8）设正整数ba,之积是一个正整数的k次方幂（2k），若（ba,）＝1，则ba,都是整数的k次方幂。一般地，设正整数cba,,,之积是一个正整数的k次方幂（2k），若cba,,,两两互素，则cba,,,都是正整数的k次方幂。定义2.设ba,是两个非零整数，一个同时为ba,倍数的数称为它们的公倍数，ba,的公倍数有无穷多个，这其中最小的一个称为ba,的最小公倍数，记作ba,，对于多个非零实数cba,,,，可类似地定义它们的最小公倍数［cba,,,］。最小公倍数主要有以下几条性质：（1）a与b的任一公倍数都是ba,的倍数，对于多于两个数的情形，类似结论也成立；（2）两个整数ba,的最大公约数与最小公倍满足：||,),(abbaba（但请注意，这只限于两个整数的情形，对于多于两个整数的情形，类似结论不成立）；（3）若cba,,,两两互素，则［cba,,,］＝｜cba,,,｜；（4）若dcdbda|,,|,|，且cba,,,两两互素，则cba,,,｜d。五．高斯函数数论函数][xy，称为高斯函数，又称取整函数.它是数学竞赛热点之一.定义一：对任意实数][,xx是不超过x的最大整数，称][x为x的整数部分.与它相伴随的是小数部分函数].[}{},{xxxxy由][x、}{x的定义不难得到如下性质：（1）][xy的定义域为R，值域为Z；}{xy的定义域为R，值域为)1,0[（2）对任意实数x，都有1}{0},{][xxxx且.（3）对任意实数x，都有xxxxxx][1,1][][.（4）][xy是不减函数，即若21xx则][][21xx}{xy是以1为周期的周期函数（内部资料）第10页，共24页10/24（5）}{}{];[][xnxxnnx.其中NnRx,.（6）11[][][];{}{}{};[][],nniiiiixyxyxyxyxxxR；特别地，].[][banbna（7）][][][yxxy，其中Ryx,；一般有11[][],nniiiiixxxR；特别地，NnRxxxnn,],[][.（8）]][[][nxnx，其中NnRx,.(9)若!pn，则][][][32pnpnpn请注意，此式虽然被写成了无限的形式，但实际上对于固定的n，必存在正整数k，使得npk，因而10kp，故0][kpn，而且对于km时，都有0][mpn。因此，上式实际上是有限项的和。另外，此式也指出了乘数!n的标准分解式中，素因数p的指数的计算方法。（10）对正实数,xy有：yyxx（11）对整数x，xx，对于x，1xx六．同余定义1.（同余）设0m，若)(|bam，则称a和b对模m同余，记作)(m