数论的方法和技巧05整数的p进位制及其应用

1、整数的p进位制及其应用基础知识给定一个m位的正整数A,其各位上的数字分别记为ami,am2, ,ao ,则此 数可以简记为：A am a 2 ao (其中am i 0)。由于我们所研究的整数通常是十进制的，因此 A可以表示成10的m 1次多 项式， 即 A am 110m 1am 2 10m 2a110 a0,其中ai 0,1,2, ,9, i 1,2, ,m 1且am1 0 ,像这种10的多项式表示的数常常简 记为A (am 1am 2 a0)10。在我们的日常生活中，通常将下标10省略不写，并且连括号也不用，记作A am 1am 2 a0,以后我们所讲述的数字，若没有指明 记数式的基，我们

2、都认为它是十进制的数字。为了具备一般性，我们给出正整数 A的p进制表示：A am1 pm1 am2 Pm2a1 p a0 ,其中 a 0,1,2, , p 1, i 1,2, ,m 1 且am 10。而m仍然为十进制数字，简记为 A (am1am 2 a0)p。典例分析例1. (2007年中国数学奥林匹克协作体竞赛试题)假定正整数N的8进制表示为 N (12345677654321)8,那么下面四个判断中，正确的是()A、N能被7整除而不能被9整除B、N能被9整除而不能被7整除C、N不能被7整除也不能被9整除 D、N既能被7整除也能被9整除 答D由于 8 1(mod 7),所以 8i 1(mo

3、d 7)kkNakak 1 a1a0 8 ai8ia/mod 7)1 0i 0即N能被7整除 N的8进制表示下各位数字之和能被 7整除。类似的，N能被9整除 N的8进制表示下奇数位数字之和与偶数位数字之和 的差能被9整除例2. 一个正整数，如果用7进制表示为abc,如果用5进制表示为丽，请用10进 制表示这个数.解：由题意知：0V a,c04,0&b谟这个正整数为n,则n= abc = a>72+bX7+ c, n= cba =c >52+ b X5+ a 49a+ 7b+ c= 25c+ 5b+ a48a+ 2b24c= 0,b=12(c 2a) . . 12 | b,又

4、< 0<b<4力=0, . .c=2a.当 a= 1,c= 2 时，n = 51当 a=2,c= 4 时，n=102例3.（第4届美国数学邀请赛试题）递增数列1,3, 4,9, 10,12,13,是由一些正整数组成，它们或是 3的事, 或是若个不同的3的幕之和，求该数列的第100项。解：将已知数列写成3的方幕形式：01102202a13 , a23 , a3 33 , a43 ,a§33 , a6 3易发现其项数恰好是自然数列对应形式的二进制表示:20,6 22 2,7 22 21 20,即 120,2 21,3 2120,4 22,5 22由于 100= (110

5、0100)2 26 25 22所以原数列的第100项为36 35 32 981例4. (1987年加拿大数学竞赛试题)1987可以在b进制中写成三位数xyz,如果x y z 1 9 8 7,试确定所有可能的x,y, z和b。解：易知 xb2 1987, x y z 25 ,从而 x(b2 1) y(b 1) 162 ,即(b 1)(b 1)x y 1962 2 32 109,由 b 10知 b 1 9。由 1962 b2 1 知 b 1963 45 故9 b 1 45;又因为1962 2 32 109有 12个正约数，分别为1,2 , 3,6 , 9,18,109,218,327,654,98

6、1,1962 所以 b 1 18,从而 b 19。又由 1987 5 192 9 19 11 知 x 5, y 9,z 11.例5.(第3届加拿大数学竞赛试题)设n是五位数(第一个数码不是零)，m是由n取消它的中间一个数码后所 成的四位数，试确定一切n使得口是整数。m解：设 n xyzuv x 104 y 103 z 102 u 10 v ,其中 x, y,z,u,v 0,1,2, ,9且 x 1; m xyuv x 103 y 102 u 10 v；而 k 口是整数，可证 9m n,即 9(x103 y 102 u 10 v) x 104 y 103 z 1C2 u 10 v m即80u 8

7、V 103x 102y 102z ,这显然是成立的；又可证 n 11m,即 x104y103z1C2u 10 v< 11(x103y102u 10 v)即102z 103 x 102 y 102u 10v,这显然也是正确的。于是9m n 11m,即9 k 11 ,又因为k是整数，从而k 10 ；于是 n 10m,即 x1(4 y 1。z 102 u 10 v=10(x 103 y 102 u 10 v)即 z 102 90u 9v 9(10 v),而 9|102z 但* 102 知 z 9t(t 为正整数)从而t 102 10u v,显然t u v 0,因而推得n xyz00 N 103

8、其中10 N 99。例6.(1999年，保加利亚数学奥林匹克试题).求所有的自然数n的个救，4<n<1023.使得n在二进制表示下，没有连续 的三个数码相同.【剖析与解】 记二进制表示中，以I开头，不出现连城三个相同数码的四位数的个数为4一对m&W Q.1I,用匕表示二进制表示中，以1开头，以而结尾，不出现连续三个相同数码的« 位数的个数,则耳？5时，易知 n n J n = -I. .h - I i - 3生加二/。，与i=x(n +- -iji +如 ，工-利用上述递推关系，可知注意到硒=3,% =5,于是的=8,. = 13,4=21 + 4 = 34.叼=

9、55,痛处二89一所求满足条件的自然数R的个数为为+%+十/。,于是，问题的答案为228.例7.(1995年.南斯拉夫数学奥林匹克试题)设n是正整数，n的二进制表示中恰有1995个1,求证：2n-1995整除n!剖析与解】 我们证明更一般的命题:设正整数再在二进制表示中恰有乂於个，则2*3'” "上为此我们先证明如下引理.引理 设满足2(2)!的A的最大值汹=21L证M =号4净4号+二尸t +却“442+1 =-1.下面用数学归纳法证明命题，令43)=在N+ .对A进行归纳，当A = 1时，口是2的方痛、设=然,由引理知结论成立.设对于左41结论成立.那么对于k + ，设龙

10、题£N，利才且=VftJ =(2)！ (7+2)72'+).由引理知” -0(23)又乂尸+叔)是m个连续自然数的积,故这个乘积能被 用 整除.又由归纳假设知m! -0(皿也”*),*.(善去 1)(2' + 2)(2/+ m)=O(m«irT).由、知朴!看OOixx't.z时)匚仪科“")，即对于上十】结论成立.综上知命题成立.例8. (1982年英国数学奥林匹克试题)设自然数n为17的倍数，且在二进制写法中恰有三个数码为1.证明n的二进制写法中至少有六个数码为 0,且若恰有7个数码为0,则n是偶数I分析与解答】因为n的二进制写法中恰

11、有三个数码是1,其余都是0,所以它可以表示 为 m = 2l +2f +2"".其中由儿皿为非负整数，旦入k河飞1果配的一进制写法中口的个数小于6, 则m C当i=0/QJ,%5,6,7时一被17除的 余数依次为1,2,4,8, - 1. - 2, - % 8,可验 证，其中任意三个数之和均不能被17整除，从 而甘=2上+丁 +T不能被17整除,与超设矛 面因此，在打的二进制中至少有6个0,如果汁的二进制写法中恰有7个。，则用 =9.如果及为奇数.则门的二进制表示中最末 一位是 丁从而 k 0.由于 2 + 2* = 20 +=513=3 (modJ7).则为使门是17的倍

12、数，应有2,三一 3 (hi<m1!7 ).但是，当工在|1,2,，81时，2,#-3 ( modi?).出现矛盾.因此m为偶数，这样的偶数确实存在，比 如 *i=2W +2, =578 = (1001000010)j.例9.（第12届IM O试题）设a, b, n均大于1.在a进制中，An 1 xn 1 xn 2 x0, An xnxn 1 x0 .在b进制中，Bn 1 xn 1xn 2 x0, Bn xnxn 1 x0.其中 xn 0, xn 10.证明：当且仅当a>b时，等鸵 AnBn ' B1L 置25时*怨1&*田I）-i）=1乩.| -炉 U,仆=*（小

13、. J / 5" ：-/-3*-）卡孙（3.m,其中- 1招-,口 $ = 1,2 .，rr - I.从前 用酒.T - 4. T生）以予<生*反之亦然./IX3L例10.已知利用的整码可以使重量是连续自然数的63个重物平衡，求这组整码.【分析与解答】设所求的6个碳码的重量按不减排列为孙小看妥冬舞.由数。，码，血中的某几个组成的和数可表示为马餐+ E产i +时备，其中与=01，且至少有一个约r0.形如的表达式恰好有£ -1 =9个.依照题设条件，这63个数可记为/ + 1，/+ 2,，航+63,由于的所有表达式均不相同，因此必有H I C0M并H有殉+ I =+62三

14、蜘+町+场，斗+63二知+x3 +%由此可得面=1.于是软=0,11 -2,* +的=3 吊=4,假设数瞑必，#JAW5)已经求出，这样表达式&1航+右之£ + - + S/J E, =0*1),就TiJ以给出数1工,*上-1、那么%M =升，且表达式若卢+ £工典+ - ， - + £& + | M* + i对同样的£|表小数12-L于是可依次求出二【评注1这是只能在天平一端放思码的情如二I,郢2, 4 =4,2=2=8,的=2'="在2000高中联赛中可以的边放藉码，那样也用二丁=3工，就是一个三进制问题，本题为二进

15、制，例11.( 2005 年中国奥林匹克协作体夏令营试题)如果一个正整数n 在三进制下表示的各数字之和可以被3 整除，那么我们称n 为 “好的 ”，则前 2005个 “好的 ”正整数之和是多少？解：首先考虑“好的 ”非负整数，考察如下两个引理：引理1.在3个连续非负整数3n,3n 1,3n 2 (n是非负整数)中，有且仅有1个是 “好的 ”。证明：在这三个非负整数的三进制表示中，0,1， 2各在最后一位出现一次，其作各位数字相同，于是三个数各位数字之和是三个连续的正整数，其中有且仅有一个能被 3 整除(即 “好的 ”) ，引理 1 得证。引理2.在9个连续非负整数9n,9n 1, 9n 8 (

16、n是非负整数)中，有且仅有3个是 “好的 ”。把这 3个 “好的 ”非负整数化成三进制，0,1， 2恰好在这三个三进制数的最后一位各出现一次。证明：由引理1不难得知在9个连续非负整数9n,9n 1, 9n 8 (n是非负整数)中，有且仅有3 个是 “好的 ”。另一方面，在这三个 “好的 ”非负整数的三进制表示中，最高位与倒数第三位完全相同，倒数第二位分别取0,1， 2。若它使它们成为“好的 ”非负整数，则最后一位不相同，引理2 得证。将所有 “好的 ”非负整数按从小到大的顺序排成一列，设第2004 个 “好的 ”非负整数为 m ，根据引理1，得 2003 3 m 2004 3，即6009 m

17、6012。设前 m 个 “好的 ”正整数之和为Sm， 由于前 2003个 “好的 ”正整数之和等于前2004个 “好的 ”非负整数之和。因此S2003(0 1 22003) 3 2004 6023022；又因为 (6013) 10 (22020201)3和 (6015)10( 22020210) 3都是 “好的 ”正整数。因此前 2005 年 “好的 ”正整数之和是：S2005 S2003 6013 6015 6035050 。例12.把所有3的方幕及互不相等的 13, 求这个数列的第100项.【分析与解答】这个数列的每项都居正 数，其3进制表示只由0和1组成,所以可以在 全体正整数与数列的耍

18、之间建立对应.他 数m的二进制表示与它所对应的数列中的三 进制表示相同.3的方幕的和排列成一个递增数列：10,12,1 = 1 ,1I = 1，2 = 1。 f0=3.3 -11I I I（3）. =4，4 : 100.clOO=9,5 = 101 - 101 =10,6 二 “口一"。=12,7 = 111 rill =13.在这个对应中，第土个正整数对应于数列 中的第小项，所以，为了求已知数列的第100项，只需在 二进制中找到卜进制100的对应数，再进而求 这个对应数在三进制中的对应数即可.100 = 110010011001 DO fJ? =%1,因此.所求数列的第100项是9

19、81 （十进 制），例13.（第12届IM O试题）设a, b, n均大于1.在a进制中,An 1 Xn 1Xn 2 Xo, An在b进制中，XnXn 1Xo.Bn 1Xn 1 Xn 2X0 , BnXnXn 1Xo.其中 Xn0, Xn 10.证明：当且仅当a>b时,An1 Bn1ABnB11.当C b时.出 口DN 苹;建 产&司* Hi%_ =/7凡.1 -丛-14=J =/（知 _八 d" V-状 T）其中兴隼潸卑黔绅货蹲二口"打"胪秘 >（1,» = L2in_ L从而 心比_ L 4. t':0,牛 与.反之亦然.

20、JT1£>-课外练习题1. (2005年全国高中数学联赛试题)记集合 T 0,1,2,3,4,5,6 , Ma1 争 学 号 a T,i 1,2,3,4，将 M 中的元素按从大到小顺序排列，则第 2005个数是A.C.599 0B 59_6_27727374.7727"7411041103234D.2347 72 73 747 72 73 742 .证明：对任何k z,k 6,k进制数(123454321)k是完全平方数.E 一明 因C2孤k +6T A+】)'一 口 11111)/"故就成工3 .设V, W, X, Y, Z为5个五进制数码.五进制

21、下的三个三位(VYZ) 5, (VYX) 5, (VVW ) 5以公差为1依次递增.问在十进制中，三位数(XYZ) 5等于多少？I - JJ i :!: »!-_ - - -解 由+ 1 = (VYX)S = (VVW ) 一【得 5(*一 Y)=X-讣,I ,岐然-一丫0】，犬一卬4.所以，只打“一丫=1,乂一可7,M面推出 不一二 3炉=''=1 ,这样XY7), = 0& = 108，4 .设19972a1 2a22an,其中a1,a2, ,an是互不相等的非负整数，求a1 a2an 的值.解 据例1的知0J997可以唯一地表示为. . J,1997叶2

22、 +22* +2 + 2 4-2，故所求的和为-15.5 .设1987可以写在b进制三位数(xyz)b,且x y z 1 9 8 7,试确定所有可 能的x,y,z及b值.解 山题设傅此的十二一1招九因此斤1987：" J2 ：6 45； 又H十了十七=2鼠故8一1=即人=19.因此，】987 = 5 乂 19 4y 19 + 11,得5沙=9，上口6 .求使2n 1能被7整除的所有正整数n.解借助于二进制很容易解决这个问题.因为 2" = (100-«0>aT2" 1=<111*“1)-而 7 = (111)2,欲使鼻牛。十171 T).则1

23、口).(1】11%则需使懵=3*3£4,冲7 .若二进制数 n (amam i aao)2满足(amam 1aiao)2 (a°ai amiam)2,贝U称 n为上进制回文数”，问在不超过1988的正整数中有多少个 七进制回文数”？解k位二迸制回文数共有个，而198彳(J 113 1000100),是li位二进耦数J1位的二二进制何丈数只由他个超过 总部,它打是和门llimuilL ,故所求的进制同文数有11兄 2+" J2n2( 1+2 + 2* + 宫+2')+1 J2=g(个).8 .对每个正整数k,n,令Sk(n)为n在k进制中的数字和，求证：对于

24、小于 20000的素数P, S3i(P)中至多有两个值为合数.证明 苜先因为20000= £质25 5人.所以，小于20000,正髓数的数字和在31进制中不大于20 430 +勖=8d：对于票数, V20000 .设 p = a ) = 960% + 30。1一(0 +西 十%).这 IE Sii，(p) =Lt? +(11 +a *由上述知公+q +&W80.又p是索数,故“ +处+%不能械235整除否则"不是素数)，在1到的之间*蠲足这惮条件的台 歌只有旧和77两个.9 .设a0,bo是正整数，定义数列a0, a1,a2,和boq,如下： aak i ,bk i

25、 2bk,k 0,1,2,.右p是使行ap 1的数，求证：对所有使得aj是奇数的bj的和等于aobo证明设网 和因为% =1,故4.=。,将/ *6 *£!?,%用二 进制表示，则有4 - C4#4 . ：八.卜 Ap 2* + Aa- 2* ' " 上九 ：41#=4 ,- 1 *当“1时皿为奇数1当A=U时以为偶数仃="h2，川.比.使得为为舒数的山的和等于九岛+ A向+永儿+"洲.'U。ina1a2a 3a 410 .设集合 A|ai 0,1,2, ,8, i 1,2, 3,4）,9929394把A中各数按照从大到小的顺序排列，求第

26、 1997个数.解 A中的元素形如如*阴+* 9+nJ.括号内的致川九逋制茬示为5 口 .其中最小者为3最大者为 眺38% = 65S0.剜A中共有6561个元素这样，从大到小的第 1997个数就是从小到大的第6萨1-1997 -1-4565个数.它是t址制题4564 , Iij 456“（623】）.故所求的数是7+子+于斗谪”例38 (1999年全国高中或赛题)给定正整数，匕知用克数为正整数的k块祛码 和一台天平可以称出质最为1,2,，克的所有物品.(1)求A的最小值j(2)当且仅当n取什么值时，上述/(n)块硅码的组成方式是惟一确定的？证明你 的结论.分析应注意用天平称物件时，祛码可放在

27、天平的两侧这一基本常识，我们就不 难用三进制数来解决问题(若限定重物在一侧，曲码只能在另一侧，则必须用二进制数 来处理).解(D 设A块硅码的质量分别为七，生，4，那么这k块破码可称出的质量为 $。工.£ W(因为征的可放天平两侧).若利用这块核仍可称出质量为1，2,克物品，则玄am可取值0,1,2,小由对称性，它也可以取值一 1, 一2,， 一明即(玄5 |工 W -10.1)»(0,±1，±2,，士*所以.i-1 A2 + 1 = | 0, 士 1,，士讨 |W| (| 了. 6 - 1。1 1< 3'，即714亚尹.设正整数机满足3二

28、，】V 竺尹，则»m.另一方面/=柩时,取反块破码的质量为=1,1 = 3,= 3卜，我们证明 用这6块破码可称出质量为12,的任何物品.为此，我们只须证明,对任意/£ (1>2.，又存在 z, 6 (一 1,0,1)。= 1,2,/)，使/= 2；31劣.事实上，对任意正整数0 4。43E 1,由三进制表示可知，存在y, e (0,1.2)使P =* 31y.则 P-"尹-*3iy -®3i = * -D3i.Cj=1I】»»1令工= y-l,则工£ -1.0,1 因此，对一切满足一彩虫竺异的整数/, 乙乙都存在6

29、(- 1,0,1),使/= £>3一/-I由于亚尹，故对一切满足一的/，也存在上述表示.这就证明了用利块昧码1,3,31可称出质量为1,2,n的任何物品.综上可知，h的最小值/5) = m，其中m为满足弓二1 <«<"异的正整数.证明(2) I.我们首先证明当n # 21ZZ1时,f(Q块祛码组成的方式不惟一.乙当产;二1 V V更异时J5)=如由 知1,3,31就是甑码的一种组成方式,下面证明：1,3,3-2,3 1也是一种方式.若&汇户，则由(D知"=31,工 - 1AD,则 I = 3i 4-0 (3 1).I】y3"' - 1 / / / 3° 1 皿3*' 1 1 ； I y / 3° 1 rh/i、HT5若 2 V I 4九V 29则 2