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

1、整数的p进位制及其应用基础知识给定一个m位的正整数a，其各位上的数字分别记为，则此数可以简记为：（其中）。由于我们所研究的整数通常是十进制的，因此a可以表示成10的次多项式，即，其中且，像这种10的多项式表示的数常常简记为。在我们的日常生活中，通常将下标10省略不写，并且连括号也不用，记作，以后我们所讲述的数字，若没有指明记数式的基，我们都认为它是十进制的数字。为了具备一般性，我们给出正整数a的p进制表示：，其中且。而仍然为十进制数字，简记为。典例分析例1(2007年中国数学奥林匹克协作体竞赛试题)假定正整数n的8进制表示为，那么下面四个判断中，正确的是（ ）a、n能被7整除而不能被9整除 b

2、、n能被9整除而不能被7整除c、n不能被7整除也不能被9整除 d、n既能被7整除也能被9整除答 d 由于，所以即n能被7整除n的8进制表示下各位数字之和能被7整除。类似的，n能被9整除n的8进制表示下奇数位数字之和与偶数位数字之和的差能被9整除例2 一个正整数，如果用7进制表示为，如果用5进制表示为，请用10进制表示这个数.解：由题意知：0a,c4,0b4,设这个正整数为n,则na×72b×7c, n=c×52b×5a 49a7bc25c5ba 48a2b24c0， b12(c2a) 12b,又0b4b0, c2a 当a1,c2时，n51 当a2,c4时

3、，n102例3（第4届美国数学邀请赛试题）递增数列1,3，4,9，10,12,13，是由一些正整数组成，它们或是3的幂，或是若个不同的3的幂之和，求该数列的第100项。解：将已知数列写成3的方幂形式：易发现其项数恰好是自然数列对应形式的二进制表示：即由于100所以原数列的第100项为。例4（1987年加拿大数学竞赛试题）1987可以在b进制中写成三位数，如果，试确定所有可能的和。解：易知，从而，即，由知。由知故；又因为有12个正约数，分别为1,2，3,6，9,18,109,218,327,654,981,1962，所以，从而。又由知例5（第3届加拿大数学竞赛试题）设是五位数（第一个数码不是零）

4、，是由取消它的中间一个数码后所成的四位数，试确定一切使得是整数。解：设，其中且；而是整数，可证，即即，这显然是成立的；又可证，即即，这显然也是正确的。于是，即，又因为是整数，从而；于是，即即，而但3102知为正整数）从而，显然，因而推得其中。例6. (1999年，保加利亚数学奥林匹克试题) 求所有的自然数n的个救，4n 1023使得n在二进制表示下，没有连续的三个数码相同例7. （l995年南斯拉夫数学奥林匹克试题）设n是正整数，n的二进制表示中恰有1995个l，求证：2n-1995整除n! 例8. (1982年英国数学奥林匹克试题)设自然数n为17的倍数，且在二进制写法中恰有三个数码为1.证

5、明n的二进制写法中至少有六个数码为0，且若恰有7个数码为0，则n是偶数。 例9. （第12届im o试题）设a，b，n均大于1在a进制中，在b进制中，其中 证明：当且仅当a>b时，例10已知利用的砝码可以使重量是连续自然数的63个重物平衡，求这组砝码例11.（2005年中国奥林匹克协作体夏令营试题）如果一个正整数在三进制下表示的各数字之和可以被3整除，那么我们称为“好的”，则前2005个“好的”正整数之和是多少？解：首先考虑“好的”非负整数，考察如下两个引理：引理1.在3个连续非负整数（是非负整数）中，有且仅有1个是“好的”。证明：在这三个非负整数的三进制表示中，0,1，2各在最后一位出

6、现一次，其作各位数字相同，于是三个数各位数字之和是三个连续的正整数，其中有且仅有一个能被3整除（即“好的”），引理1得证。引理2.在9个连续非负整数（是非负整数）中，有且仅有3个是“好的”。把这3个“好的”非负整数化成三进制，0,1，2恰好在这三个三进制数的最后一位各出现一次。证明：由引理1不难得知在9个连续非负整数（是非负整数）中，有且仅有3个是“好的”。另一方面，在这三个“好的”非负整数的三进制表示中，最高位与倒数第三位完全相同，倒数第二位分别取0,1，2。若它使它们成为“好的”非负整数，则最后一位不相同，引理2得证。将所有“好的”非负整数按从小到大的顺序排成一列，设第2004个“好的”非

7、负整数为，根据引理1，得，即。设前个“好的”正整数之和为，由于前2003个“好的”正整数之和等于前2004个“好的”非负整数之和。因此；又因为和都是“好的”正整数。因此前2005年“好的”正整数之和是：。例12. 把所有3的方幂及互不相等的3的方幂的和排列成一个递增数列：10,12，13， 求这个数列的第100项例13. （第12届im o试题）设a，b，n均大于1在a进制中，在b进制中，其中 证明：当且仅当a>b时，课外练习题1.（2005年全国高中数学联赛试题） 记集合，将m中的元素按从大到小顺序排列，则第2005个数是a. b. c. d. 2. 证明：对任何进制数是完全平方数3. 设v，w，x，y，z为5个五进制数码五进制下的三个三位(vyz)5，(vyx)5，（vvw）5以公差为1依次递增问在十进制中,三位数(xyz)5等于多少？4. 设其中是互不相等的非负整数，求的值5. 设1987可以写在b进制三位数且试确定所有可能的x,y,z及b值6. 求使能被7整除的所有正整数n7. 若二进制数满足则称n为“二进制回文数”，问在不超过1988的正整数中有多少个“二进制回文数”？8. 对每个正整数令 为n在k进制中的数字和，求证：对于小于20000的素数p，中至多有两个值为合数9. 设是正整数，定义数列和