数学竞赛中的数论问题-(习题部分)

数学竞赛中的数论问题第二部分数论题的范例讲解主要讲几个重要类型：奇数与偶数，约数与倍数（素数与合数），平方数，整除，同余，不定方程，数论函数等．重点是通过典型范例来分析解题思路、提炼解题方法和巩固基本内容．一、奇数与偶数整数按照能否被2整除可以分为两类，一类余数为0，称为偶数，一类余数为1，称为奇数．偶数可以表示为2n，奇数可以表示为21n或21n．一般地，整数被正整数m去除，按照余数可以分为m类，称为模m的剩余类modiCxxim，从每类中各取出一个元素iiaC，可得模m的完全剩余系（剩余类派出的一个代表团），0,1,2,,1m称为模m的非负最小完全剩余系.通过数字奇偶性质的分析而获得解题重大进展的技巧，常称作奇偶分析，这种技巧与分类、染色、数字化都有联系，在数学竞赛中有广泛的应用．关于奇数和偶数，有下面的简单性质：（1）奇数偶数．（2）偶数的个位上是0、2、4、6、8；奇数的个位上是1、3、5、7、9．（3）奇数与偶数是相间排列的；两个连续整数中必是一个奇数一个偶数；．（4）奇数个奇数的和是奇数；偶数个奇数的和是偶数；偶数跟奇数的和是奇数；任意多个偶数的和是偶数．（5）除2外所有的正偶数均为合数；（6）相邻偶数的最大公约数为2，最小公倍数为它们乘积的一半．（7）偶数乘以任何整数的积为偶数．（8）两数和与两数差有相同的奇偶性，mod2abab．（9）乘积为奇数的充分必要条件是各个因数为奇数．（10）n个偶数的积是2n的倍数．（11）11k的充分必要条件是k为偶数，11k的充分必要条件是k为奇数．（12）22220mod4,211mod4,211mod8nnn．（13）任何整数都可以表示为221mnk．……例1（1906，匈牙利）假设12,,,naaa是1,2,,n的某种排列，证明：如果n是奇数，则乘积1212naaan是偶数．类似题：例1-1（1986，英国）设127,,,aaa是整数，127,,,bbb是它们的一个排列，证明112277ababab是偶数．（127,,,aaa中奇数与偶数个数不等）例1-2的前24位数字为3.14159265358979323846264，记1224,,,aaa为该24个数字的任一排列，求证12342324aaaaaa必为偶数．（暗藏3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4中奇数与偶数个数不等）例2能否从1,2,,15中选出10个数填入图的圆圈中，使得每两个有线相连的圈中的数相减（大数减小数），所得的14个差恰好为1,2,,14？例3有一大筐苹果和梨分成若干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数，问最少要把这些苹果和梨分成几堆？例4有n个数121,,,,nnxxxx，它们中的每一个要么是1，要么是1．若1223110nnnxxxxxxxx，求证4|n．例5n个整数121,,,,nnaaaa，其积为n，其和为0，试证4|n．例6在数轴上给定两点1和2，在区间(1,2)内任取n个点，在此2n个点中，每相邻两点连一线段，可得1n条互不重叠的线段，证明在此1n条线段中，以一个有理点和一个无理点为端点的线段恰有奇数条．二、约数与倍数最大公约数与最小公倍数的求法．（1）短除法．（2）分解质因数法．设1212,0,1,2,,kkiapppik，1212,0,1,2,,kkibpppik．记min,,max,iiiiii，则1212,kkabppp，1212,kkabppp．（3）辗转相除法121,,,,,0nnnnabbrrrrrrr．例7（1）求8381,1015，8381,1015；（2）144,180,108，144,180,108．例8正整数n分别除以2,3,4,5,6,7,8,9,10得到的余数依次为1,2,3,4,5,6,7,8,9，则n的最小值为．．例9有两个容器，一个容量为27升，一个容量为15升，如何利用它们从一桶油中倒出6升油来？例10对每一个2n，求证存在n个互不相同的正整数12,,,naaa，使ijijaaaa，对任意的,1,2,,,ijnij成立．例11111959,IMO证明对任意正整数n，分数214143nn不可约．例12不存在这样的多项式1110mmmmfnananana，使得对任意的正整数n，fn都是素数．．三、平方数若a是整数，则2a就叫做a的完全平方数，简称平方数．1．平方数的简单性质（1）平方数的个位数只有6个：0,1,4,5.6.9．（2）平方数的末两位数只有22个：00，01，21，41，61，81，04，24，44，64，84，25，16，36，56，76，96，09，29，49，69，89．（3）2220mod4,211mod4nn．（４）2211mod8n．（6）凡是不能被3整除的数，平方后被3除余1．（7）在两个相邻整数的平方数之间，不能再有平方数．（8）非零平方数的约数有奇数个．（9）直角三角形的三边均为整数时，我们把满足222abc的整数,,abc叫做勾股数．勾股数的公式为2222,2,,amnbmncmn其中,mn为正整数，,1mn且,mn一奇一偶．这个公式可给出全部素勾股数．2．平方数的证明方法（1）反证法．（2）恒等变形法．（3）分解法．设a为平方数，且abc，,1bc，则,bc均为平方数．（4）约数法．证明该数有奇数个约数．3．非平方数的判别方法（1）若221nxn，则x不是平方数．（2）约数有偶数个的数不是平方数．（3）个位数为2，3，7，8的数不是平方数．（4）同余法：满足下式的数n都不是平方数．2mod3n，23mod4n或，23mod5n或，23567mod8n或或或或，2378mod10n或或或．（5）末两位数不是：00，01，21，41，61，81，04，24，44，64，84，25，16，36，56，76，96，09，29，49，69，89．如个位数与十位数都是都是奇数的数，个位数是6、而十位数是偶数的数．例13有100盏电灯，排成一横行，从左到右，我们给电灯编上号码1，2，…，99，100．每盏灯由一个拉线开关控制着．最初，电灯全是关着的．另外有100个学生，第一个学生走过来，把凡是号码为1的倍数的电灯的开关拉了一下；接着第2个学生走过来，把凡是号码为2的倍数的电灯的开关拉了一下；第3个学生走过来，把凡是号码为3的倍数的电灯的开关拉了一下，如此等等，最后那个学生走过来，把编号能被100整除的电灯的开关拉了一下，这样过去之后，问哪些灯是亮的？例14已知直角三角形的两条直角边分别为正整数,ab，斜边为正整数c，若a为素数，求证21ab为平方数．例15求证，任意3个连续正整数的积不是平方数．例162311986,IMO设d是异于2，5，13的任一整数．求证在集合2,5,13,d中可以找到两个不同元素,ab，使得1ab不是完全平方数．例17(296IMO)设,ab为正整数，1ab整除22ab．证明221abab是完全平方数．四．整除整除的判别方法主要有7大类．1．定义法．证baabq，有三种方式．（1）假设aqbr，然后证明0r．（定理4）（2）具体找出q，满足abq．（3）论证q的存在．例18任意一个正整数m与它的十进制表示中的所有数码之差能被9整除．2．数的整除判别法．（1）任何整数都能被1整除．（2）如果一个整数的末位能被2或５整除，那么这个数就能被2或５整除．（3）如果一个整数的末两位能被４或25整除，那么这个数就能被4或25整除．（4）如果一个整数的末三位能被8或125整除，那么这个数就能被8或125整除．（5）如果一个整数各数位上的数字之和能被3或9整除，那么这个数就能被3或9整除．证明由101mod3,101mod9，有1110110101010mod3nnnnnnaaaaaaaa，1110110101010mod9nnnnnnaaaaaaaa（6）如果一个整数的末三位数与末三位数以前的数字所组成的数的差能被7或11或13整除，那么这个数就能被7或11或13整除．证明由1210nnmaaaaa13132101001nnnnaaaaaaaaa，知132101321010011001nnnnaaaaaaaaaaaa，又由100171113，而7,11,13均为素数知，m能被7或11或13整除．（7）如果一个整数的奇位数字之和与偶位数字之和的差能被11整除，则这个数能被11整除．证明由101mod11，有11101110101010111mod11.nnnnnnnnaaaaaaaa3．分解法．主要用乘法公式．如123221nnnnnnnababaabababb．212122232422322nnnnnnnababaabababb．2221222322221nnnnnnnababaabababb．例19试证555129129．例202111979,IMO设p与q为正整数，满足111112313181319pq，求证p可被1979整除（1979p）例20-12009年9月9日的年、月、日组成“长长久久、永不分离”的吉祥数字20090909，而它也恰好是一个不能再分解的素数．若规定含素因子20090909的数为吉祥数，请证明最简分数111220090908mn的分子m是吉祥数．4．余数分类法．例21试证3121nnn．例22k个连续整数中必有一个能被k整除．例23k个连续整数之积必能被!k整除．例24有男孩、女孩共n个围坐在一个圆周上（3n），若顺序相邻的3人中恰有一个男孩的有a组，顺序相邻的3人中恰有一个女孩的有b组，求证3ab．例25（1956，中国北京）证明3231122nnn对任何正整数n都是整数，并且用3除时余2．五、同余根据定义，同余问题可以转化为整除问题来解决；同时，同余本身有很多性质，可以直接用来解题．例26正方体的顶点标上1或1，面上标上一个数，它等于这个面四个顶点处的数的乘积，求证，这样得出的14个数之和不能为0．．例27设多项式nnnnaxaxaxaxf1110的系数都是整数，并且有一个奇数及一个偶数使得f及f都是奇数，求证方程0xf没有整数根．六、不定方程未知数的个数多于方程个数的整系数代数方程，称为不定方程．求不定方程的整数解，叫做解不定方程．解不定方程通常要解决3个问题，方程是否有解？有解时，有几个解，解数是有限还是无穷？求出全部解．例28解方程719213xy．例29求方程3222009xxy的整数解．例30甲乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，…直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数为．（1988，高中联赛）例31（1989，高中）如果从数1，2，…，14中按由小到大的顺序取出123,,aaa，使同时满足21323,3aaaa，那么，所有符合上述要求的不同取法有多少