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

1 数学竞赛中的数论问题第二部分数论题的范例讲解主要讲几个重要类型：奇数与偶数，约数与倍数（素数与合数），平方数，整除，同余，不定方程，数论函数等 重点是通过典型范例来分析解题思路、提炼解题方法和巩固基本内容一、奇数与偶数整数按照能否被2 整除可以分为两类，一类余数为0，称为偶数，一类余数为1，称为奇数偶数可以表示为2n，奇数可以表示为21n或21n一般地，整数被正整数m去除，按照余数可以分为m类，称为模m的剩余类modiCx xim，从每类中各取出一个元素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）两数和与两数差有相同的奇偶性，mod 2abab（9）乘积为奇数的充分必要条件是各个因数为奇数（10）n个偶数的积是2n的倍数（11）11k的充分必要条件是k为偶数，11k的充分必要条件是k为奇数（12）22220 mod 4,211 mod 4,211 mod8nnn（13）任何整数都可以表示为221mnk,例 1（1906，匈牙利）假设12,na aa是1,2,n的某种排列，证明：如果n是奇数，则乘积1212naaan2 是偶数类似题：例 1-1（1986，英国）设127,a aa是整数，127,b bb是它们的一个排列，证明112277ababab是偶数（127,a aa中奇数与偶数个数不等）例 1-2的前 24 位数字为3.14159265358979323846264，记1224,a aa为该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 例 3 有一大筐苹果和梨分成若干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数，问最少要把这些苹果和梨分成几堆？例4有n个 数121,nnx xxx，它 们 中 的 每 一 个 要 么 是1，要 么 是1 若1223110nnnx xx xxxx x，求证4|n例 5 n个整数121,nna aaa，其积为n，其和为0，试证4|n例 6 在数轴上给定两点1 和2，在区间(1,2)内任取n个点，在此2n个点中，每相邻两点连一线段，可得1n条互不重叠的线段，证明在此1n条线段中，以一个有理点和一个无理点为端点的线段恰有奇数条4 二、约数与倍数最大公约数与最小公倍数的求法（1）短除法（2）分解质因数法设1212,0,1,2,kkiapppik，1212,0,1,2,kkibpppik记min,max,iiiiii，则1212,kka bppp，1212,kka bppp（3）辗转相除法121,0nnnna bb rr rrrrr例 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 升油来？5 例10 对 每 一 个2n，求 证 存 在n个 互 不 相 同 的 正 整 数12,na aa，使ijijaaaa，对任意的,1,2,i jnij成立例 11 1 11959,IMO证明对任意正整数n，分数214143nn不可约例 12 不存在这样的多项式1110mmmmf na nana na，使得对任意的正整数n，f n都是素数6 三、平方数若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）2220 mod 4,211 mod 4nn（）2211 mod 8n（6）凡是不能被3 整除的数，平方后被3 除余 1（7）在两个相邻整数的平方数之间，不能再有平方数（8）非零平方数的约数有奇数个（9）直角三角形的三边均为整数时，我们把满足222abc的整数,a b c叫做勾股数勾股数的公式为2222,2,amnbmncmn其中,m n为正整数，,1m n且,m n一奇一偶这个公式可给出全部素勾股数2平方数的证明方法（1）反证法（2）恒等变形法（3）分解法设a为平方数，且abc，,1b c，则,b c均为平方数（4）约数法证明该数有奇数个约数3非平方数的判别方法（1）若221nxn，则x不是平方数（2）约数有偶数个的数不是平方数（3）个位数为2，3，7，8 的数不是平方数（4）同余法：满足下式的数n都不是平方数2 mod3n，23 mod4n或，23 mod5n或，23567 mod8n或 或 或 或，7 2378 mod10n或 或 或（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已知直角三角形的两条直角边分别为正整数,a b，斜边为正整数c，若a为素数，求证21ab为平方数例 15 求证，任意3 个连续正整数的积不是平方数8 例 16 23 11986,IMO设d是异于 2，5，13 的任一整数求证在集合2,5,13,d中可以找到两个不同元素,a b，使得1ab不是完全平方数例 17 (29 6IMO)设,a b为正整数，1ab整除22ab证明221abab是完全平方数四整除整除的判别方法主要有7 大类1定义法证b aabq，有三种方式（1）假设aqbr，然后证明0r（定理 4）（2）具体找出q，满足abq（3）论证q的存在例 18任意一个正整数m与它的十进制表示中的所有数码之差能被9 整除9 2数的整除判别法（1）任何整数都能被1 整除（2）如果一个整数的末位能被2 或整除，那么这个数就能被2 或整除（3）如果一个整数的末两位能被或25 整除，那么这个数就能被4 或 25 整除（4）如果一个整数的末三位能被8 或 125 整除，那么这个数就能被8 或 125 整除（5）如果一个整数各数位上的数字之和能被3 或 9 整除，那么这个数就能被3 或 9 整除证明由101 mod3,101 mod9，有1110110101010mod3nnnnnnaaaaaaaa，1110110101010mod9nnnnnnaaaaaaaa（6）如果一个整数的末三位数与末三位数以前的数字所组成的数的差能被7 或 11 或 13整除，那么这个数就能被7 或 11 或 13 整除证明由1210nnma aa a a13132101001nnnna aaa aaa a a，知132101321010011001nnnna aa a a aa aaa a a，又由10017 11 13，而7,11,13均为素数知，m能被 7 或 11 或 13 整除（7）如果一个整数的奇位数字之和与偶位数字之和的差能被11 整除，则这个数能被11 整除证明由101 mod11，有11101110101010111mod11.nnnnnnnnaaaaaaaa3分解法主要用乘法公式如123221nnnnnnnababaabababb212122232422322nnnnnnnababaabababb10 2221222322221nnnnnnnababaabababb例 19 试证555129129例 2021 11979,IMO设p与q为正整数，满足111112313181319pq，求证p可被 1979 整除（1979p）例 20-1 2009 年 9 月 9日的年、月、日组成“长长久久、永不分离”的吉祥数字20090909，而它也恰好是一个不能再分解的素数若规定含素因子20090909的数为吉祥数，请证明最简分数111220090908mn的分子m是吉祥数4 余数分类法例 21 试证3121n nn11 例 22 k个连续整数中必有一个能被k整除例 23 k个连续整数之积必能被!k整除例 24 有男孩、女孩共n个围坐在一个圆周上（3n），若顺序相邻的3 人中恰有一个男孩的有a组，顺序相邻的3 人中恰有一个女孩的有b组，求证3 ab12 例 25（1956，中国北京）证明3231122nnn对任何正整数n都是整数，并且用3除时余 2五、同余根据定义，同余问题可以转化为整除问题来解决；同时，同余本身有很多性质，可以直接用来解题例 26 正方体的顶点标上1或1，面上标上一个数，它等于这个面四个顶点处的数的乘积，求证，这样得出的14 个数之和不能为0例 27 设多项式nnnnaxaxaxaxf1110的系数都是整数，并且有一个奇数及一个偶数使得f及f都是奇数，求证方程0 xf没有整数根13 六、不定方程未知数的个数多于方程个数的整系数代数方程，称为不定方程求不定方程的整数解，叫做解不定方程解不定方程通常要解决3 个问题，方程是否有解？有解时，有几个解，解数是有限还是无穷？求出全部解例 28 解方程719213xy例 29 求方程3222009xx y的整数解例 30甲乙两队各出7 名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1 号队员比赛，负者被淘汰，胜者再与负方2 号队员比赛，,直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数为（1988，高中联赛）14 例 31（1989，高中）如果从数1，2，,，14 中按由小到大的顺序取出123,a aa，使同时满足21323,3aaaa，那么，所有符合上述要求的不同取法有多少种？七数论函数主要是x高斯函数，n欧拉函数例 32 某学校要召开学生代表大会，规定各班每10 人推选一名代表，当各班人数除以10 的余数大于6时再增选一名代表那么，各班可推选代表人数y与该班人数x之间的函数关系用取整函数yx（x表示不大于x的最大整数）可以表示为(A)10 xy(B)310 xy (C)410 xy(D)510 xy（2010 年全国高考数学陕西卷理科第10 题）例 33用x表示不大于x的最大整数，求12200436636636636615 例 34 50!的标准分解式中2 的指数 八、综合练习例 35 整数勾股形中，证明（1）必有一条直角边长是3 的倍数；（2）必有一条直角边长是4 的倍数；（3）必有一条边长是5 的倍数；（4）三角形的面积是6 的倍数例 36 已知ABC内有n个点，连同,A B C共有3n个点，以这些点为顶点，把ABC分割为若干个互不重叠的小三角形，现把,A B C分别染上红色、蓝色、黄色，而其余n个点，每点任意染上红、蓝、黄三色之一，证明三顶点都不同色的小三角形的总数必是奇数（斯潘纳定理）例 37 对整点 25 边形的顶点作三染色，求证，存在一个三顶点同色的三角形，它的重心也是整点