数学竞赛中的数论问题题型全.pdf

《数学竞赛中的数论问题题型全.pdf》由会员分享，可在线阅读，更多相关《数学竞赛中的数论问题题型全.pdf（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 数学竞赛中的数论问题定理 4 ,a b是两个不同时为0 的整数，若00axby是形如axby（,x y是任意整数）的数中的最小正数，则（1）00axby|axby；（2）00axby,a b证明（1）由带余除法有00axbyaxbyqr，000raxby，得0000ra xqxxb yqyaxby，知r也是形如axby的非负数，但00axby是形如axby的数中的最小正数，故0r，即00axby|axby（2）由（1）有00axby|10aba，00axby|01abb，得00axby是,a b的公约数另一方面，,a b的每一个公约数都可以整除00axby，所以00axby是,a b的最大

2、公约数，00axby,a b推论若,1a b，则存在整数,s t，使1asbt（很有用）定理 5互素的简单性质：（1）1,1a（2）,11n n（3）21,211nn（4）若p是一个素数，a是任意一个整数，且a不能被p整除，则,1a p推论若p是一个素数，a是任意一个整数，则,1a p或,a pp（6）若,1,1a ba c，则,1a bc证明由,1a b知存在整数,s t，使1asbt有a csbctc，得,1a bca c（7）若,1a b，则,1ab a，,1ab b，,1ab ab证明,1ab ab ab a，,1ab ba b，由（6）,1ab ab（8）若,1a b，则,1mnab

3、，其中,m n为正整数证明据（6），由,1a b可得,1mab同样，由,1mab可得,1mnab定理 7素数有无穷多个，2 是唯一的偶素数证明假设素数只有有限多个，记为12,nppp，作一个新数1211npp pp若p为素数，则与素数只有n个12,nppp矛盾若p为合数，则必有12,inpp pp，使|ipp，从而|1ip，又与1ip矛盾综上所述，素数不能只有有限多个，所以素数有无穷多个2 是素数，而大于2 的偶数都是合数，所以2是唯一的偶素数2 注：这个证明中，包含着数学归纳法的早期因素：若假设有n个素数，便有1n个素数（构造法、反证法）定理 8（整除的性质）整数,a b c通常指非零整数（

4、1）1 a，1|a；当0a时，|a a，|0a（2）若b a，0a，则ba;若b a，ba，则0a;若0ab，且,b a a b，则ab证明由b a，0a，有abq，得ab qb逆反命题成立“若b a，ba，则0a”;由ba且ba得ab，又0ab，得ab（7）若,1a b，且a bc，则a c证明由,1a b知存在整数,s t，使1asbt，有a csbc tc，因为a a，a bc，所以a整除等式的左边，进而整除等式的右边，即a c（8）若,1a b，且,a c b c，则ab c证明由,1a b知存在整数,s t，使1asbt，有acsbctc，又由,a c b c有12,caq cbq代

5、入得21ab q sab q tc，所以ab c注意不能由a c且b c得出ab c如不能由6 30且10|30得出60|30（9）若a为素数，且a bc，则a b或a c证明若不然，则|ab且|ac，由a为素数得,1,1a ba c，由互素的性质（6）得,1a bc，再由a为素数得|abc，与a bc矛盾定义 6对于整数,a b c，且0c，若()c ab，则称,a b关于模c同余，记作(mod)abc；若|ca b，则称,a b关于模c不同余，记作a(mod)bc定理 9（同余的性质）设,a b c d m为整数，0,m若(mod)abm且(mod)cdm，则(mod)acbdm且(mod

6、)acbdm证明由(mod)abm且(mod)cdm，有12,abmq cdmq，对直接相加，有12acbdm qq，得(mod)acbdm.对分别乘以,c b后相加，有12acbdacbcbcbdm cqbq，得(mod)acbdm（3）若(mod)abm，则对任意的正整数n有(mod)nnabm且(mod)anbnmn.3（4）若(mod)abm，且对非零整数k有(,)k a b m，则modabmkkk证明由(mod)abm、，有abmq，又(,)k a b m，有,a b mk kk均为整数，且abmqkkk，得modabmkkk定理 10 设,a b为整数，n为正整数，（1）若ab，

7、则nnabab123221nnnnnnnababaabababb（2）若ab，则2121nnabab212122232422322nnnnnnnababaabababb（3）若ab，则22nnabab2221222322221nnnnnnnababaabababb定义 7设n为正整数，k为大于 2 的正整数,12,ma aa是小于k的非负整数，且10a若12121mmmmna ka kaka，则称数12ma aa为n的k进制表示定理 11给定整数2k，对任意的正整数n，都有唯一的k进制表示如12121101010mmmmnaaaa，109,0iaa（10 进制）12121222mmmmnaaa

8、a101,0iaa（进制）定理 12（算术基本定理）每个大于1 的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的1212kknppp，其中12kppp为素数，12,k为正整数（分解唯一性）定 理13若 正 整 数n的 素 数 分 解 式 为1212kknppp则n的 正 约 数 的 个 数 为12111kd naaa，n的一切正约数之和为121111212111111kkkpppS nppp证明对于正整数1212kknppp，它的任意一个正约数可以表示为1212kkmppp，0ii，由于i有0,1,2,i共1i种取值，据乘法原理得n的约数的个数为12111kd naaa4

9、考虑乘积12010101111222kkkkppppppppp，展开式的每一项都是n的某一个约数（参见），反之，n的每一个约数都是展开式的某一项，于是，n的一切约数之和为110101111kkkS npppppp121111212111111kkkpppppp注构造法定义 8（高斯函数）对任意实数x，x是不超过x的最大整数 亦称x为x的整数部分，1xxx定理 14在正整数!n的素因子分解式中，素数p作为因子出现的次数是23nnnppp证明由于p为素数，故在!n中p的次方数是1,2,n各数中p的次方数的总和（注意，若p不为素数，这句话不成立）在1,2,n中，有np个p的倍数；在np个p的倍数的因

10、式中，有2np个2p的倍数；在2np个2p的倍数的因式中，有3np个3p的倍数；，如此下去，在正整数!n的素因子分解式中，素数p作为因子出现的次数就为23nnnppp注省略号其实是有限项之和定理 15（费玛小定理）如果素数p不能整除整数a，则11pp a证明 2改证等价命题：如果素数p不能整除整数a，则modpaap只需对1,2,1ap证明成立，用数学归纳法（1）1a，命题显然成立（2）假设命题对11akkp成立，则当1ak时，由于|1,2,1ipp Cip，故有11111ppppppkkC kCk11 modpkkp（用了归纳假设）这表明，命题对1ak是成立由数学归纳法得modpaap又素数

11、p不能整除整数a，有,1a p，得11pp a定义 9 （欧拉函数）用n表示不大于n且与n互素的正整数个数定理 16设正整数1212kknppp，则12111111knnppp推论对素数p有11,ppppp5 第二讲数论题的范例讲解（12）22220 mod4,211 mod4,211 mod8nnn（13）任何整数都可以表示为221mnk例 1-1（1986，英国）设127,a aa是整数，127,b bb是它们的一个排列，证明112277ababab是偶数（127,a aa中奇数与偶数个数不等）例 1-2的前 24 位数字为3.14159265358979323846264，记1224,a

12、 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？解考虑 14 个差的和S，一方面1214105S为奇数另一方面，每两个数,a b的差与其和有相同的奇偶性(mod2)abab，因此，14 个差的和S的奇偶性与 14 个相应数之和的和/S的奇偶性相同，由于图中的每一个数a与 2 个或 4 个圈中的数相加，对/S的

13、贡献为2a或4a，从而/S为偶数，这与S为奇数矛盾，所以不能按要求给图中的圆圈填数评析：用了计算两次的技巧对同一数学对象，当用两种不同的方式将整体分为部分时，则按两种不同方式所求得的总和应是相等的，这叫计算两次原理成富比尼原理计算两次可以建立左右两边关系不太明显的恒等式在反证法中，计算两次又可用来构成矛盾例 3 有一大筐苹果和梨分成若干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数，问最少要把这些苹果和梨分成几堆？解（1）4 堆是不能保证的如4 堆的奇偶性为：（反例）（奇奇），（偶偶），（奇偶），（偶奇）（2）5堆是可以保证因为苹果和梨数的奇偶性有且只有上述4 种可能，当把这

14、些苹果和梨分成5 堆时，必有 2 堆属于同一奇偶性，其和苹果数与梨数都是偶数例4有n个 数121,nnxxxx，它们 中 的每 一 个要 么 是1，要么 是1 若1223110nnnxxxxxxxx，求证4|n证明由1,1ix，有11,1iix x，再由1223110nnnx xx xxxx x，知n个1iix x中有一半是1，有一半是1，n必为偶数，设2nk现把n个1iix x相乘，有2222122311121(1)(1)1kknnnnnx xx xxxx xx xxx，6 可见，k为偶数，设2km，有4nm，得证4|n例 6 在数轴上给定两点1 和2，在区间(1,2)内任取n个点，在此2n

15、个点中，每相邻两点连一线段，可得1n条互不重叠的线段，证明在此1n条线段中，以一个有理点和一个无理点为端点的线段恰有奇数条证明将2n个点按从小到大的顺序记为122,nAAA，并在每一点赋予数值ia，使 1,1,iiiAaA当为有理数点时，当为无理数点时.与此同时，每条线段1iiA A也可数字化为1iia a（乘法）1111,1,iiiiiiA Aa aA A当一为有理数点，另一为无理数时，当同为有理数点或无理数点时,记11iiaa的线段有k条，一方面112233412()()()()(1)(1)(1)kn kknna aa aa aaa另一方面12233412()()()()nna aa aa

16、 aaa21231212()1nnna a aaaa a，得11k，故k为奇数 评析用了数字化、奇偶分析的技巧二、约数与倍数最大公约数与最小公倍数的求法（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解（1）方法 1 分解质因数法由283811729,10155729,得8381

17、,101529，28381,10155 7 1729293335方法 2 辗转相除法或8381,1015261,1015261,23229,23229,0298381 10158381 10158381,10158381352933358381,101529（2）方法 1 短除法由22144,180,1082336，得2144 180 108272 90 54336 30 27312 10 94 5 37 43144,180,1082352160方法 2 分解质因数法由42222314423,180235,10823,，得22144,180,1082336，43144,180,10823521

18、60例 8正整数n分别除以2,3,4,5,6,7,8,9,10得到的余数依次为1,2,3,4,5,6,7,8,9，则n的最小值为解 依题意，对最小的n，则1n是2,3,4,5,6,7,8,9,10的公倍数321235 7n，得2519n例 9 有两个容器，一个容量为27 升，一个容量为15 升，如何利用它们从一桶油中倒出6 升油来？解相当于求不定方程15276xy的整数解由15,273知，存在整数,u v，使15273uv，可得一个解2,1uv，从而方程1542726即往小容器里倒2 次油，每次倒满之后就向大容器里倒，大容器倒满时，小容器里剩有3 升油；再重复一次，可得 6 升例10 对 每

19、一 个2n，求 证 存 在n个 互 不 相 同 的 正 整 数12,na aa，使ijijaaaa，对 任 意 的,1,2,i jnij成立证明用数学归纳法当2n时，取121,2aa，命题显然成立假设nk时，命题成立，即存在12,ka aa，使ijijaa aa，对任意的,1,2,i jkij成立现取b为12,ka aa及它们每两个数之差的最小公倍数，则1k个数12,kb ab abab满足,ttijijabb abbabababab即命题对1nk时成立由数学归纳法知命题对2n成立例 11 1 11959,IMO证明对任意正整数n，分数214143nn不可约证明 1（反证法）假若214143n

20、n可约，则存在1d，使214,143nnd，从而存在,1p qp q，使214,143,ndpndq消去n，3322，得132dqp，8 的1d由（1）、（5）矛盾，得1d解题分析：（1）去掉反证法的假设与矛盾就是一个正面证法（2）式是实质性的进展，表明13 1432 214nn，可见214,1431nn由此获得2 个解法证明 2设214,143nnd存在,1p qp q，使214,143,ndpndq消去n，3-2，得132dqp得1d证明 3 由13 1432 214nn得214,1431nn证明 4 214,143nn71,143nn71,1n1解题分析：第相当于-；第 相当于-2（-）

21、=3-2；所以式与式的效果是一样的例 12 不存在这样的多项式1110mmmmfna nana na，使得对任意的正整数n，f n都是素数证明假设存在这样的多项式,对任意的正整数n，fn都是素数，则取正整数nb，有素数p使1110mmmmf ba bababap，进而对任意的整数,k有1110mmmmfbkpabkpabkpabkpa1110mmmma baba baMp（二项式定理展开）1PM，其中M为整数，这表明f bkp为合数这一矛盾说明，不存在这样的多项式,对任意的正整数n，fn都是素数三、平方数若a是整数，则2a就叫做a的完全平方数，简称平方数1平方数的简单性质（1）平方数的个位数只

22、有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，9 96，09，29，49，69，89（3）2220 mod4,211 mod4nn（）2211 mod 8n（6）凡是不能被3 整除的数，平方后被3 除余 1（7）在两个相邻整数的平方数之间，不能再有平方数（8）非零平方数的约数有奇数个（9）直角三角形的三边均为整数时，我们把满足222abc的整数,a b c叫做勾股数勾股数的公式为2222,2,amnbmncmn其中,m n为正整数，,1m n且,m n一奇一偶这个公式可给出全部

23、素勾股数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或 或 或 或，2378 mod10n或 或 或（5）末两位数不是：00，01，21，41，61，81，04，24，44，64，84，25，16，36，56，76，96，09，29，49，69，8

24、9如个位数与十位数都是都是奇数的数，个位数是6、而十位数是偶数的数例 13有 100 盏电灯，排成一横行，从左到右，我们给电灯编上号码1，2，99，100每盏灯由一个拉线开关控制着最初，电灯全是关着的另外有100 个学生，第一个学生走过来，把凡是号码为1 的倍数的电灯的开关拉了一下；接着第2 个学生走过来，把凡是号码为2 的倍数的电灯的开关拉了一下；第3 个学生走过来，把凡是号码为 3 的倍数的电灯的开关拉了一下，如此等等，最后那个学生走过来，把编号能被100 整除的电灯的开关拉了一下，这样过去之后，问哪些灯是亮的？讲解（1）直接统计100 次拉线记录，会眼花缭乱（2）拉电灯的开关有什么规律：

25、电灯编号包含的正约数（学生）才能拉、不是正约数（学生）不能拉，有几个正约数就被拉几次（3）灯被拉的次数与亮不亮（开、关）有什么关系：0 1 2 3 4 5 6 7 8 9 关开关开关开关开关开灯被拉奇数次的亮！（4）哪些数有奇数个约数：平方数（5）1 100 中有哪些平方数：共10 个：1，4，9，16，25，36，49，64，81，100答案：编号为1，4，9，16，25，36，49，64，81，100 共 10 个灯还亮10 例 14已知直角三角形的两条直角边分别为正整数,a b，斜边为正整数c，若a为素数，求证21ab为平方数 证明由勾股定理222cab，有2cbcba，但a为素数，必有

26、2,1,cbacb解得2112ba，从而22212121abaaa，为平方数例 15 求证，任意3 个连续正整数的积不是平方数证明设存在 3 个连续正整数1,1nn n（1n）的积为平方数，即存在整数m，使211nn nm，即221nnm，但21,1nn，故21,nn均为平方数，有2221,nanbmab得222211211nannn，（注意1n）这一矛盾说明，3 个连续正整数的积不是平方数四整除整除的判别方法主要有7 大类1定义法证b aabq，有三种方式（1）假设aqbr，然后证明0r（定理 4）（2）具体找出q，满足abq（3）论证q的存在例 18任意一个正整数m与它的十进制表示中的所有

27、数码之差能被9 整除证明设1110101010nnnnmaaaa，其中09,0inaa，则110111121111101101101911111111,nnnnnnnnnnmaaaaaaaaaaa个个按定义1109nnmaaaa2数的整除判别法（1）任何整数都能被1 整除（2）如果一个整数的末位能被2 或整除，那么这个数就能被2 或整除（3）如果一个整数的末两位能被或25 整除，那么这个数就能被4 或 25 整除（4）如果一个整数的末三位能被8 或 125 整除，那么这个数就能被8 或 125 整除（5）如果一个整数各数位上的数字之和能被3 或 9 整除，那么这个数就能被3 或 9 整除证明由

28、101 mod3,101 mod9，有1110110101010mod3nnnnnnaaaaaaaa，11 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）如果一个整

29、数的奇位数字之和与偶位数字之和的差能被11 整除，则这个数能被11 整除证明由101 mod11，有11101110101010111mod11.nnnnnnnnaaaaaaaa3分解法主要用乘法公式如123221nnnnnnnababaabababb212122232422322nnnnnnnababaabababb2221222322221nnnnnnnababaabababb例 19 试证555129129证明改证55545 129设555129S，则555555555512344123418273645918273645999,Smmmmmmmm得9 S又555555555192837

30、465S51234412341928374655 22225,mmmmmmmm得5 S但9,51，得45 S，即555129129例 2021 11979,IMO设p与q为正整数，满足111112313181319pq，求证p可被 1979 整除（1979p）证明11111231 3 1 81 3 1 9pq111111112231318131924131812 111111111231318131923659111166066113181319660 1319661 1318989990660 1319661 1318989 99019796606611319659!19791319!MM得

31、 1979 整除1319!p，但 1979 为素数，1979,1319!1，得p可被 1979 整除例 20-1 2009 年 9 月 9 日的年、月、日组成“长长久久、永不分离”的吉祥数字20090909，而它也恰好是一个不能再分解的素数若规定含素因子20090909的数为吉祥数，请证明最简分数111220090908mn的分子m是吉祥数证明：由111220090908mn11111112009090822009090710045454100454552009090920090909200909091 200909082 2009090710045454 1004545520090909,1

32、 220090907 20090908p其中p为正整数，有200909091 22009090720090908npm，这 表 明，20090909整 除122 0 0 9 0 9 0 72 0 0 9 09m，但20090909为 素 数，不 能 整 除122 0 0 9 0 9 0 72 0 0 9，所以20090909整除m，得m是吉祥数4 余数分类法例 21 试证3121n nn证明 1 任何整数n被 3 除其余数分为3 类3,31,32,nk nknkkZ，（1）3nk时，有12133161,n nnkkk有3121n nn（2）31nk时，有121331 3221,n nnkkk有

33、3121n nn（3）32nk121332165,n nnkkk有3121n nn综上得，3121n nn证 明2 222211214nnnn nn，得3 22221nnn，又3,41，得13 3121n nn5数学归纳法6反证法 7构造法例 22 k个连续整数中必有一个能被k整除证明设k个连续整数为,1,2,1a aaak，若这k个数被k除没有一个余数为0，则这k个数的余数只能取1,2,1k，共1k种情况，必存在两个数,0ai ajijk，使1,aikqr2,ajkqr其中12qq，相减12ijk qq，有12ijk qqk，即ijk与ijk矛盾故k个连续整数中必有一个能被k整除也可以由12

34、ijk qq得120ijk qqk，推出1201qq，与12qq为整数矛盾例 23 k个连续整数之积必能被!k整除证明设k个连续整数为,1,2,1n nnnk，（1）若这k个连续整数为正整数，则121!n nnnknkknkknC只须证明，对任何一个素数p，分子中所含p的方次不低于分母中所含p的方次，由高斯函数的性质xyxy，有ssssknknknkpppp得knC为整数（证实了组合数的实际意义）（2）若这k个连续整数中有0，则连乘积为0，必能被!k整除（3）若这k个连续整数为负整数，则121!1211!1,kkknn nnnkknnnnkkC由（1）知knC为整数，故121!n nnnkk为

35、整数例 24 有男孩、女孩共n个围坐在一个圆周上（3n），若顺序相邻的3 人中恰有一个男孩的有a组，顺序相邻的 3 人中恰有一个女孩的有b组，求证3 ab证明现将小孩记作(1,2,)ia in，且数字化14 1,1,iiiaaa表示男孩时表示女孩时则“3 人组”数值化为12121212123,3,1,1,iiiiiiiiiiiiiiiia aaa aaAaaaa aaa aa 均为男孩均为女孩 恰有一个女孩恰有一个男孩其中njjaa又设取值为3 的iA有p个，取值为3的iA有q个，依题意，取值为1 的iA有b个，取值为1的iA有a个，得1212323413()()()()nnaaaaaaaaa

36、aaa3(3)(1)3()()pqabpqba，可见3 ab例 25（1956，中国北京）证明3231122nnn对任何正整数n都是整数，并且用3 除时余 2分 析只 需 说 明23131222nnnn为 整 数，但 不 便 说 明“用3除 时 余2”，应 说 明3212131222n nnnnn是 3 的倍数作变形32222213111,3,81228nnnnnn，命题可证证明已知即321213111222n nnnnn，因为相邻2 个整数,1n n必有偶数，所以3231122nnn为整数又可变为32222213111228nnnnnn，因为相邻3 个整数2,22,21nnn必有 3 的倍数

37、，故22221nnn能被 3 整除；又3,81，所以222218nnn能被 3 整除；得3231122nnn用 3 除时余 2五、同余根据定义，同余问题可以转化为整除问题来解决；同时，同余本身有很多性质，可以直接用来解题例 26 正方体的顶点标上1或1，面上标上一个数，它等于这个面四个顶点处的数的乘积，求证，这样得出的 14 个数之和不能为0证明记 14 个数的和为S，易知，这 14 个数不是1就是1，若八个顶点都标上1，则14S，命题成立对于顶点有1的情况，我们改变1为1，则和S中有 4 的数,a b c d改变了符号，用/S表示改变后的和，由15 0 mod2abcd知/20 mod4SS

38、abcd，这表明，改变一个1，和S关于模 4 的余数不变，重复进行，直到把所有的1都改变为1，则/1 11142 mod4SS，所以，0S例 27 设多项式nnnnaxaxaxaxf1110的系数都是整数，并且有一个奇数及一个偶数使得f及f都是奇数，求证方程0 xf没有整数根证明由已知有0121 mod21 mod2nfaaaa，1 mod21 mod2nfa，若方程0 xf存在整数根0 x，即00fx当0 x为奇数时，有00120 mod20 mod2nfxaaaa，与矛盾有0 x为偶数时，有00 mod20 mod2nfxa，与矛盾所以方程0 xf没有整数根六、不定方程未知数的个数多于方程

39、个数的整系数代数方程，称为不定方程求不定方程的整数解，叫做解不定方程解不定方程通常要解决3 个问题，方程是否有解？有解时，有几个解，解数是有限还是无穷？求出全部解例 28 解方程719213xy解法 1 由7,191知方程有整数解观察特解，列表得一个特解0025,2,xy从而通解为2519,27.xtyt方法总结：第 1 步，验证,a b c，经常是,1a b第 2步，求特解（观察、列举、辗转相除等）第 3 步，代入公式方法总结：modaxbycaxcb或modbyca例 29 求方程3222009xx y的整数解解由 2009 的分解式，有222212009741xxy，有21,1,1,10

40、04,1005,22009,xxxyyxy227,7,7,17,24.241,xxxyyxyy1 2 3 x197725 16 例 30甲乙两队各出7 名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1 号队员比赛，负者被淘汰，胜者再与负方2 号队员比赛，直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数为（1988，高中联赛）解法 1设甲、乙两队的队员按出场顺序分别为1234567,A AAAAAA和1234567,B BBBBBB如果甲方获胜，设iA获胜的场数是ix，则07,17ixi而且1277xxx，容易证明以下两点：在甲方获胜时（i）不同

41、的比赛过程对应着方程的不同非负整数解；（ii）方程的不同非负整数解对应着不同的比赛过程，例如，解（2，0，0，1，3，1，0）对应的比赛过程为：1A胜1B和2B；3B胜1A、和3A；4A胜3B后负于4B；5A胜4B、5B和6B但负于7B；最后6A胜7B结束比赛下面求方程的非负整数解个数，设1iiyx，问题等价于方程123456714yyyyyyy，正整数解的个数，将上式写成1 1 1 1 1 1 1 1 1 1 1 1 1 114，从 13 个加号取6 个的方法数613C种得甲方获胜的不同的比赛过程有613C种同理，乙方获胜的不同的比赛过程也有713C种，合计61323432C种比赛过程例 3

42、1（1989，高中）如果从数1，2，14 中按由小到大的顺序取出123,a a a，使同时满足21323,3aaaa，那么，所有符合上述要求的不同取法有多少种？解由已知得12132310,3030,140,aaaaaa4 项均为非负数，相加得121323133 147aaaaaa，于是123,a aa的取法数就是不定方程12347xxxx的非负整数解的个数，作一一对应11iyx，问题又等价于不定方123411yyyy的正整数解由1 1111，得310C个解，即符合要求的不同取法有310C种七数论函数主要是x高斯函数，n欧拉函数例 32 某学校要召开学生代表大会，规定各班每10 人推选一名代表，

43、当各班人数除以10 的余数大于6时再增选一名代表 那么，各班可推选代表人数y与该班人数x之间的函数关系用取整函数yx（x表示不大于x的最大整数）可以表示为17(A)10 xy(B)310 xy (C)410 xy(D)510 xy（2010 年全国高考数学陕西卷理科第10 题）解法 1 选（B）（求解对照）规则是“六舍七入”，故加 3 即可进 1 选310 xy解法2 选（B）（特值否定）取56x，按规定应选5 人，可否定(C)、(D)；再取57x，按规定应选6人，可否定(A)注：主要错误选(C)，误为“五舍六入”例 33用x表示不大于x的最大整数，求122004366366366366讲解题

44、目的内层有2004 个高斯记号，外层1 个高斯记号关键是弄清x的含义，进而弄清加法谁与谁加、除法谁与谁除：（1）分子是那些数相加，求出和来；由366 5183020042196366 6，知分子是05 的整数相加，弄清加数各有几个1365 0 365 个366731 1 366 个7321097 2 366 个1098 1463 3 366 个1464 1829 4 366 个1830 2004 5 175 个（2）除法谁除以366，求出商的整数部分原式0 365366 12345 1753661036687536614310236612.命题背景2004 年有 12 个月、366 天例 34

45、 50!的标准分解式中2 的指数 解35678912450!2 3 5 7 11 13 17 1923 29 31 37 41 43 472 的指数为18 2345505050505025126314722222图示（5 条横线，25 个偶数中2 的方次，按横线求和）八、综合练习例 35 整数勾股形中，证明（1）必有一条直角边长是3 的倍数；（2）必有一条直角边长是4的倍数；（3）必有一条边长是5 的倍数；（4）三角形的面积是6 的倍数证明当整数勾股形的三边有公约数时，可以先约去，使三边长,x y z互素，且满足222xyz.这时，若,x y两个均为偶数，则z也为偶数，与,x y z互素矛盾；

46、若,x y两个均为奇数，有221 mod4,1 mod4xy，得2222 mod4zxy，这与平方数模4 只能取 0，1 矛盾.所以，,x y中有且只有一个为偶数，不妨设x为偶数.（1）设,x y中无一为3 的倍数，则221 mod3,1 mod3xy，得2222 mod3zxy，这与平方数模3 只能取 0，1 矛盾，故,x y中有一个为3 的倍数.（2）由x为偶数.，必有,y z均为奇数，记2,21,21xm ypzq有22222222421214mxzyqpqqpp则211mq qp p右边是两个偶数的差，必为偶数，从而x为 4 的倍数.（3）若,x y中有 5 的倍数，命题已成立.若,x

47、 y均不是 5 的倍数，则若,x y只能是形如51k或52k的正整数.若,x y均为51k型，则2221 12 mod5zxy这与平方数模5 只能取 0，1，4 矛盾若,x y均为52k型，则222443 mod5zxy这与平方数模5 只能取 0，1，4 矛盾.所以，,x y只能分别取51k与52k型，有222410 mod5zxy得25 z，但 5 是素数，得5 z.（4）由上证（1）、（2）及3,41知，xy是 12 的倍数，则12xy是 6 的倍数，得三角形的面积是6 的倍数例 36 已知ABC内有n个点，连同,A B C共有3n个点，以这些点为顶点，把ABC分割为若干个互不重叠的小三角

48、形，现把,A B C分别染上红色、蓝色、黄色，而其余n个点，每点任意染上红、蓝、黄三色之一，证明三顶点都不同色的小三角形的总数必是奇数（斯潘纳定理）证明 1 给这些小三角形的边赋值：当边的两端点同色时，记为0；当边的两端点异色时，记为1；再用三边之和给小三角形赋值：当三角形的三顶点同色时，和值为0，记这样的小三角形有a个；当三角形的三顶点中仅有两点同色时，和值为2，记这样的小三角形有b个；当三角形的三顶点两两异色时，和值为3，记这样的小三角形有c个.下面用两种方法计算所有三角形赋值的总和S，一方面02323Sabcbc.另方面，,AB BC CA的赋值均为1，和为奇数；而ABC内的每一条连线，

49、在上述S的计算中都被计算了两19 次，和为偶数；这两者之和得S为奇数，记为21Sk由，得2123kbc可见c为奇数，即三顶点都不同色的小三角形的总数必是奇数（证明：n 个连续整数的乘积一定能被n!整除设 a 为任一整数，则式：(a+1)(a+2).(a+n)=(a+n)!/a!=n!*(a+n)!/(a!n!)而式中(a+n)!/(a!n!)恰为 C(a+n,a),也即是从 a+n中取出 a 的组合数，当然为整数。所以(a+1)(a+2).(a+n)一定能被 n!整除同余式与不定方程例：求使 2n+1 能被 3 整除的一切自然数n.解则 2n+1当 n 为奇数时，2n+1 能被 3 整除；当

50、n 为偶数时，2n+1 不能被 3 整除.例 2 求 2999最后两位数码.解 考虑用 100 除 2999所得的余数.又2999的最后两位数字为88.例 3 求证 31980+41981能被 5 整除.证明2不定方程不定方程的问题主要有两大类：判断不定方程有无整数解或解的个数；如果不定方程有整数解，采取正确的方法，求出全部整数解.(1)不定方程解的判定20 如果方程的两端对同一个模m(常数)不同余,显然,这个方程必无整数解.而方程如有解则解必为奇数、偶数两种，因而可以在奇偶性分析的基础上应用同余概念判定方程有无整数解.例 4 证明方程 2x2-5y2=7 无整数解.证明2x2=5y2+7，显