小学奥数数论例题

竞赛中的数论问题【知识点介绍】初等数论也叫做整数论，其研究对象是整数，由于其形式简单，所用知识不难理解，因而常常出现在数学竞赛中．数学竞赛中的数论问题主要涉及奇数和偶数，约数与倍数，素数与合数，平方数、整除、同余、不定方程、数论函数[x]和欧拉函数、数的非十进制等．处理竞赛中的数论问题要求熟悉基本知识，灵活地运用一些常用技巧．在本讲中，如没有特别说明，所用的字母均表示整数．1．整除设a、b是两个整数，b≠0，则一定有且仅有两个整数q和r，使得a=bq+r(0≤r<|b|)成立，其中q叫做商，r叫做余数．当r=0时，称b整除a(或a能被b整除)，记作b|a．此时a叫b的倍数，b叫a的约数(因数)．设是正整数，是不小于2的整数，则存在惟一的一组小于的非负整数，且，使得，这就是的进制表示．设a、b是两个不全为0的整数，若整数d既能整除a又能整除b，则称d是a、b的公约数，a、b的公约数中的最大者称为a、b的最大公约数，记为(a，b)．若(a，b)=1，则称a、b是互素(互质)的．设a、b是两个都不为0的整数，若m是a的倍数，同时又是b的倍数，则称m是a、b的公倍数，a、b的公倍数中最小的正数称为a、b的最小公倍数，记为[a，b]．对任意的正整数a、b有：(a，b)[a，b]=ab．对非零整数a、b、c、m、n，有以下性质：若，则;若，则;若，则;若，且，则;若，且，则.2．同余设是一个不小于2的正整数，且，则称对模同余，记作．设是整数，且，则(1)若，且，则；(2)若，且，则且；(3)若，且正整数满足，则．3．素数与合数若一个大于1的整数除了1和本身外再无其它的正约数，则称这个数为素数（质数）．每一个大于1的整数都可分解成素数的乘积，而且不计因数的顺序时，这种表示是惟一的，即．

正整数的素数分解式为，则的正约数的个数为，的所有正约数的和为每连续个整数中，与互质的整数的个数是.4．不定方程若是方程的一个正整数解，则方程的一切整数解可以表示为方程满足且是偶数的一切正整数解为（这里，一奇一偶，且）．[典型例题]例1(2007年广西预赛试题)已知三个正整数x，y，z的最小公倍数是300，并且则方程组的解(x，y，z)=.解记方程组中的两个方程为（1），（2），消去x得，即，所以，或．若，则由(1)得，不合题意．由和（1）得，即，于是，令，有，，从而(x，y，z)=(20，60，100)．例2（2008年全国高中数学联赛试题）方程组的有理数解的个数为（B）A.1B.2C.3D.4[解]若，则解得或若，则由得．①由得．②将②代入得．③由①得，代入③化简得.易知无有理数根，故，由①得，由②得，与矛盾，故该方程组共有两组有理数解或说明：上述两个例题都是求不定方程组的整数解，这类问题通常是想办法将其转化成不定方程来进行求解。例3(2007年安徽省预赛试题)设A=100000000003…499500是一个1203位正整数，由100到500的全体三位数按顺序排列而成，那么A被126除的余数是()（A）78．（B）36．（C）6．（D）0．分析，因此只要求出A被2，7，9除的余数，就可求出A被126除的余数．解注意到,,又所以综上，．故选（C）.例4(2007年浙江省预赛试题)已知a=重，则a的末两位数字是()（A）01．（B）07．（C）43．（D）49．分析求a的末两位数字，即求a被100除的余数，因此考虑用同余性质解题．解记Nk=重．则.又，.所以.因此，a的末两位数字是43．故选（C）．说明一般地，对于正整数a、m，数列是周期数列．例5(2007年安徽省预赛试题)在正整数构成的等差数列1，3，5，7，…中删去所有和55不互质的项之后，把余下的各项按从小到大的顺序排成一个数列．易见，…….那么等于()（A）9597．（B）5519．（C）2381．（D）2759．分析考虑正整数列1，2，3，4，5，6，7，…其中每连续110个数与2，5，11都互质的数的个数都一样多，可以求出，不与2，3，5都互质的数也可以求出，这样把这个正整数列进行分段，能计算出余下的数的个数．解法1可以看作是在正整数列1，2，3，4，5，6，7…中删去所有可能被2，5或11整除的项之后，把余下的各项按从小到大的顺序排成的数列，于是余下的项是所有与互质的项．而每连续110个整数中，与110互质的数有个．又，而正整数列中第7个与110互质的数是19，所以．故选（B）．解法2可以看作是在正整数列1，2，3，4，5，6，7…中删去所有可能被2，5或11整除的项之后，把余下的各项按从小到大的顺序排成的数列．由容斥原理，从1到正整数中，不能被2，5或11整除的项的个数是(其中表示不超过的最大整数．由，得．而，且5519与110互质，从而．故选（B）．例6（2008年全国数学高中联赛试题）求满足下列关系式组的正整数解组的个数．分析：此问题是二次不定方程，且有约束条件，因此要进行适当的转化求解。[解]令，由条件知，方程化为，即．（1）因，故，从而．设．因此（1）化为．（2）下分为奇偶讨论，（ⅰ）当为奇数时，由（2）知为奇数．令，，代入（2）得．（3）（3）式明显无整数解．故当为奇数时，原方程无正整数解．（ⅱ）当为偶数时，设，由方程（2）知也为偶数．从而可设，代入（2）化简得．（4）由（4）式有，故，从而可设，则（4）可化为，．（5）因为整数，故．又，因此，得，．因此，对给定的，解的个数恰是满足条件的的正因数的个数．因不是完全平方数，从而为的正因数的个数的一半．即．由题设条件，．而25以内有质数9个：2，3，5，7，11，13，17，19，23．将25以内的数分为以下八组：：，，，，，，，，从而易知，，(，(，，，，，将以上数相加，共131个．因此解的个数共131．例7(2007年天津预赛试题)方程的所有正整数解为.分析本方程不能通过分解求出其正整数解，我们用同余方法．解方程两边模3得，．设，代入方程，约去3，再两边模3得，．设，则原方程化为，于是，即．因为或1,或1，，所以为偶数，于是．经验证，，所以．说明：该问题就是运用一个数的平方关于模4的余数而求出该不定方程的解。例8试求方程的正整数解。分析：这是一个二阶不定方程，通常用因式分解方法，将其转化成一阶不定方程组求解。解若方程有正整数解，则由于，且与有相同的奇偶性，故从知原方程的正整数解必是且仅是下列方程组的正整数解故解得原方程的正整数解为或。例9(2005年北京市中学生数学竞赛试题)设个质数构成公差为()的等差数列，且，求证:(1)当是质数时，；(2)当=15时，.分析对问题(1)，我们注意到一个数被除的余数有个，而题中所给出的数有个，所以应从这个数被除的余数考虑．对问题(2)，应注意运用问题(1)的结论．解(1)因为都是大于的质数，所以不整除，于是被除的余数只能取个不同的余数.由抽屉原理，必有两个数被除的余数相同，设为，则有，即，又，所以.(2)当时，对任意一个小于的质数，有也是公差为()的等差数列，且，于是由(1)的结论，有，从而，即，从而.例10(2006年女子数学奥林匹克试题)求证:对，均有无穷多个正整数，使得中恰有个可表示为3个正整数的立方和.分析首先，本题实际上是要证明3个命题.其次，我们对整数被3除的余数进行分析，从而对任一整数的立方被9除的余数就有一个定论，再就每一命题构造出使命题成立的.解每一整数可表示为的形式，而或，于上任一整数的立方模9为0或±1，从而三个整数的立方和被9除的余数不能为4或5.当时，令.显然，这样的正整数有无穷多个，，，于是均不能表示成三个整数的立方和，而是三个相同正整数的立方和.当时，，显然，这样的正整数有无穷多个，不是三个整数的立方和，且.当时，，显然，这样的正整数有无穷多个，且，，.例10：求方程的所有非负整数解解：由于为偶数，所以。情形1：若，此时原方程变为若则由此可得，（事实上因此这与矛盾。（不能被3整除）若则当时，直接计算可得（两组解）当时，有，直接计算知不可能（因为）所以当时，全部的非负整数解为两组解。情形2：若则因此因为则知为奇数，则所以计算知）当时，有则因此得此与矛盾，所以于是当时，当时故因此（5（**））因此，而，则，这与矛盾。故此种情况的整数解为情形3：若此时则有又，则则有所以都是奇数，从而所以，原方程变为（其中都是奇数）由此知从而，（直接计算得）设（）于是因为又与互质，所以于是，若则有（类似于情形2中（**）式得矛盾）即不可能，则，即故此时有解综上所述原方程有4组整数解例：试确定具有下述性质的所有正整数，集合能分成两个不相交的非空子集，使得一个子集中所有元素的积等于另一个子集的所有元素的积。解：在中加上数，则是模7的一个完全剩余系。假设满足条件的存在，下面分两中情况讨论：若则中必有，由于分成两个子集的元素的积相等，积为，则，因为7为素数，则中必有另一个，使得，这是不可能的；若，则令分成两个子集的积为，则有但是（事实上综上所述，满足题中条件的不存在。设是一个大于1的固定整数，数列定义如下求的最大值，使得数列中有连续的项均能被整除。解：最大值为。设是关于模的余数，在数列中按照连续的项分块，则余数最多有种情况出现，则超过项时就会出现相同余数的情形，又结合数列的递推关系知，数列是周期数列。由已知条件可得，及其中的项的余数分别为按上公式可求出这项前面的项模的余数分别为结合周期性得另一方面，若在余数数列中有连续项为0，则由递推公式得所有的项，这与矛盾。所以的最大值为2.每一个正整数遵循下面的过程得到数（1）将的最后一位数字移到第一位得到数；（2）将平方得到数；（3）将的首位数字移到最后一位得到数。求所有的正整数，使得。解：设正整数满足，且有位数字，,又设的最后一位数为，的第一位数为。则有（其中表示数位上的数字）所以既是末尾数字为的一个数的平方的最后一位，同时又是首位为的一个数的平方的第一位数字。完全平方数，要么是位数，要么是位数，若，则，则最多为位数，从而其平方最多为位，所以最多有位，则不可能是的平方。所以，因此的最后一位数字不为0。若，则由知而由，则只能为1或2，矛盾，所以不能为4。同样分析可只不能为5，6，7，8，9也就是只可能为1，2，3当时位且首位为的数的平方是位数；当时位且首位为的数的平方要么是首位数字为9的位数，要么是首位是数字1的位数。由已知条件可知，且是位数字。设，其中是位数（，设）则（其中是数的位数等于）故由得于是，由于其平方为位数，则对于前面两种情况，后面情况综上所述，满足条件的为3，2，和3．设是大于5的整数，对于每一个正整数，考虑进制的数（个1，个2），证明：存在一个正数使得对于大于的正整数，数是一个完全平方数的充分必要条件是。证明：对于6，7，8，9将任何数按模进行分类，直接计算知无解由于，所以此时不是完全平方数。当，直接计算得显然是完全平方数（只要）对于设假设存在一个正整数，当时，是完全平方数，则对于，也是完全平方数。由及所以另一方面因此，对于任意整数，存在一个整数，使得，且有将，代入（1），可得当足够大时，一定有即或将，及代入（1），当时，适当大时（1）不成立，所以，于是由（1）可得上式左边能被整除，从而可得，由，所以此时可得，由前面结论知不可能为一个完全平方数。综上所述，得证本题结论。4．一个整数，若满足不是一个完全平方数，则称这个数是“好”数。求满足下列性质的所有整数，整数可以用无穷多种方式表示成三个不同的“好”数的和，且这三个“好”数的积是一个奇数的平方。解：假设可以表示为且是一个奇数的平方，于是均为奇数，则，所以中要么有两个数模4余3，要么都模4余1。所以总有下面证明是满足条件的所有整数。为此我们来进行验证考虑的表示形式，在这样的表示中三个被加数的积是一个完全平方数。设，则推得于是有，，由上可知，，均为奇数，且其积是一个奇数的平方，同时易知，除有限个外，，，是互不相同的，下面证明有无穷多个，，，不是完全平方数。当，不是完全平方数选取两个不同的质数，使得，选取，使得满足，，由孙子定理知，如上的有无穷多解。可以证明对于这样的，，，不是完全平方数。结论得证。5．数列定义如下：对所有的，证明：如果奇数，则证明：由数学归纳法可以证明若有整数解，可设满足。由条件，即从而因为及故于是因为由费尔马小定理有，所以有，由于是奇质数，因此若没有整数解，同样有即存在整数，使得两边乘得，因此，存在整数使得由定义知，且，不妨设于是有[（1+所以存在整数，使得（*）设集合，下面证明对每个，不存在一个满足。事实上，若，因为，且，不妨设，于是存在整数，使得（由互质）因此有，与没有整数解矛盾。因此若则，故，（因为）所以推出或矛盾。所以对每个，不存在一个满足。因为，定义影射，满足显然，该影射是双射，于是有所以所以由（*）知从而。结论得证6．设是一个质数，是一个正整数的集合，且满足下列条件：（1）集合中的元素的质因数的集合包含个元素（2）对于的非空子集百年，其元素之积不是一个整数的次幂求：中元素个数的最大值。解：最大值为设，假设互不相同的质数分别为，定义，设，则中有个元素，且满足条件（1），（2）。假设，且满足条件（1），下面证明不存在这样的集合满足条件（2）。设是个不同的质数，使的每一个，均可以表示为，从中可以看出对每一个，相应有一个向量与其对应。下面证明，只要，则一定可以找到这些数中一些的积为某个整数的次幂。（事实上，若有若干个上述向量的和关于模是零向量则结论得证）为此，我们只要证明下列同余方程组有非零解实际上，如果是上述同余方程组的非零解，因为，所以一定有若干个向量满足和模是零向量。为了证明上面的同余方程组有非零解，只要证明同余方程（*）有非零解即可（因为每一个或，所以上述方程等价于，由于为质数，所以等价于。下面证明同余方程（*）的接的个数可以被整除，为此只要证明（这里表示对所有可能的的取值的求和）实际上，由于模有种取值方法，因此共有项。因为或，所以，的项能被整除。从而的项也能被整除。因为是质数，平凡解只有一个，因此，一定有非零解。考虑的每一个单项式，由于的单项式中最多有个变量，因此的每一个单项式最多有个变量，所以每个单项最少缺一个变量。假设单项式形如：，其中当其他个变量变化时，形如的单项式出现次，所以的每一个单项式均能被整除。因此，综上所述，所求的最大值是7．试求所有互质的正整数对，使满足：，解：对正整数对有，，（则从而，存在某个正整数，适合（。由（，则所以。若，易知若，则，注意到211是质数，故或1，若，则（事实上，如果，由于，故或13。如果，则，又331是质数，故，从而，矛盾。如果，同样导出矛盾）当时，将方程转化为设该方程的另一个根为，则有易知，由于，故，即由于，从而得，即所以，即是“更小”的一组解，且值不变。这就说明，每一组（）都可由（1，1）或（1，211）导出，且，所以可以构造如下：原方程的所有正整数解对为和。8.（1）试求所有的正整数，使得方程有正整数解（2）证明：对上述每个，方程有无穷多个这样的正整数解使得中任意两数之积皆可表示为两个正整数的平方和。解：（1）先证明一个引理：引理1：不存在不全为零的整数使得，其中是某个偶数。事实上，假设不然，设是使达到最小的不全为零的整数组，注意到是某个偶数，故中必有偶数，从而由于整数的平方关于模4的余数为0或1，故只能都为偶数。设，，，其中是整数，将代如方程得但与假设是达到最小的不全为零的整数组，矛盾。即引理得证。回到原题。固定，设是使得达到最小的正整数，不妨设原方程可写为设该关于的方程另一根为，则有，，由于均为正整数，所以也为正整数，由条件知，得。则，即从而由于时，，时。结合引理知或3。（2）先考虑定义数列如下：引理2：特别地特别地。证明：定义：，则所以。类似可以证明由引理2中知是方程时的解，显然有无穷多组，且，即满足（2）的要求。对于，由于有无穷多个这样的正整数解使得此时即是方程时的解，同样满足（2）的要求。9．求所有的正整数，使得为合数，并且可以将的所有大于1的正约数排成一圈，其中任意相邻的数不互质。解：只要合数不是两个不同质数的乘积，就符合要求。事实上，当（为不同的质数），大于1的约数只有，任何排列相邻，它们互质，故此时不符合要求。对其余的合数，我们分别进行讨论。若，为质数，为正整数，则对于的所有大于1的正约数任意排成一圈，其中任意相邻的数不互质。若（为质数，）这里或者而记且先将排成一圈放置在与之间，将放置在与，依此类推最后将放在与之间。这样的放置满足题目要求。10．证明方程组没有整数解。证明：（1）将两式相加两边都加1得（*）对比费马小定理，我们对上式关于19作模可知，故对任意，有从而因此可知（*）式左边满足但是所以（*）式左、右不相等，从而原方程组没有整数解。（2）也可以利用13作模类似可证结论。11．今有10个互不相同的非零数，现知它们之中任意两数的和或积是有理数，证明：每个数的平方都是有理数。证明：（1）如果各个数都是有理数则结论成立。现假设10个数中有无理数，于是其他各数都具有形式或，其中为有理数。事实上，形如的数不会多余两个，如果三个不同的数都具有这种形式，不妨设，那么，不是有理数，因而就应该是有理数。同理和也要为有理数。则，，也是有理数，从而也是有理数，只有矛盾。这表明形如的数多余两个。设，，，显然仅当时才可能是有理数。而互不相等，所以，，中至少一个不为0，不妨设，则为无理数，则为有理数，因此为有理数，从而结论得证。（2）考察其中任意6个数，作一个图，如果某两个数的和为有理数，就在相应的两个数之间连蓝边，如果两个数的积有有理数就在相应的两个数之间连红边，则在这样的图中存在一个三边同色的三角形1*如果存在蓝色三角形，则表明存在三个数使得，，都是有理数，从而为有理数，即为有理数，则也为有理数。对此三个数之外的10个数中的某个数，则或为有理数，则为有理数，从而这10个数都为有理数。2*如果存在红色边的三角形，这表明存在，使得都是有理数，因而为有理数，同理知也都是有理数。如果三者中至少有一个有理数，则可导出这10个数全为有理数，结论成立。如果这三个数中没有有理数，设，其中为有理数，或由于为有理数，所以，其中为有理数，我们观察其余的任意一个数，如果中有一个为有理数，则可得，其中为有理数。因而为有理数。结论成立。而如果与都是有理数，则应该为有理数，但是为无理数，则矛盾。综上所述，证明了题目结论。13．设是正整数，，证明：对，数有一个质因子大于。证明：先证一个引理：设是的任一个质因子，则具有形式，是正整数。事实上，设是的任一个质因子，则，设2模的阶是，由得，故，所以是2的幂，设其中若，则将两边反复平方可得矛盾，所以即阶由费马小定理，所以，故引理得证。回到原问题，设，由引理知从而即有另一方面，由二项式展开知由于时，则即，故故从而必有某个使得得，从而，故14．求方程的所有非负整数解解：由为偶数知情形1：若此时若则由此得则，与矛盾若则当1，2，3时直接计算得是两组解。当时，有直接计算知，这是不可能的。所以当时只有解（1，0，0，0）和（3，0，0，1）两组解。情形2：若，，则因此，即，从而为奇数，故，由此知当时，有，因此有与矛盾，所以于是当是，直接计算的，此时得原方程解（1，1，1，0）当时，有，则得，因此，故，这与矛盾。情形3：若，，此时，即，因此和均为奇数，从而所以，原方程变为（其中为奇数）因此得，从上式解得，设，于是因为，又则得，于是若，则得，由情形2知，这是不可能的。所以，则。故此种情况的解综上的原方程的四个解。15．求所有正整数组满足：，且的质因子集合与的质因子的集合相同。解：记为正整数的不同质因子构成的集合。先证一个引理引理：若正整数，为质数，且，则，是2的方幂。引理的证明：假设为奇质数，由于若不整除，则从而矛盾！则，设不整除，则，因为，所以，矛盾。所以若为偶数，则，故，矛盾。所以为奇数，则因，故没有奇质因子，所以是2的方幂。回到原问题，设，可设，由知且由于于是我们有令，则，且任取的质因子，则，故，由引理知，，是2的方幂，所以，若，则仍由引理知是2的方幂，这与是2的方幂矛盾。所以设且为奇数。若为偶数，则，不可能。故为奇数，如果，由于为大于1的奇数，这与矛盾。所以，，由知，反之，当，，，有的质因子集合与的质因子的集合相同。综上所述，所求的，，16.试求满足：，且的所有三元整数组解：由于任何奇数的平方被4除余1，偶数的平方是4的倍数，即又故由知中必有两个偶数，一个奇数。设为：（为正整数），则原方程化为：又现讨论：（1）若，则，于是均为3的倍数，设为则得，于是设，则，显然，则则可取3，7，12，16，21代入分别可得，，，，计算可知，16（4，5），（2，5）这时的原方程的解为：（23，24，30）和（12，30，31）。（2）若不整除3，由于任何3个连续的数中必有一个能被3整除，则是3的倍数。故，因此只能取2，5，8，11，1