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

(完整版)数论的方法和技巧 05整数的p进位制及其应用整数的p进位制及其应用基础知识给定一个m位的正整数A，其各位上的数字分别记为，则此数可以简记为：（其中）。由于我们所研究的整数通常是十进制的，因此A可以表示成10的次多项式,即，其中且，像这种10的多项式表示的数常常简记为。在我们的日常生活中，通常将下标10省略不写，并且连括号也不用,记作，以后我们所讲述的数字，若没有指明记数式的基，我们都认为它是十进制的数字.为了具备一般性，我们给出正整数A的p进制表示：,其中且。而仍然为十进制数字，简记为。典例分析例1（2007年中国数学奥林匹克协作体竞赛试题）假定正整数N的8进制表示为，那么下面四个判断中，正确的是( )A、N能被7整除而不能被9整除 B、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,则na72b7c, n=c52b5a 49a7bc25c5ba 48a2b24c0， b12(c2a） 12b,又0b4b0, c2a 当a1，c2时，n51 当a2，c4时，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届加拿大数学竞赛试题）设是五位数（第一个数码不是零)，是由取消它的中间一个数码后所成的四位数,试确定一切使得是整数.解：设，其中且；而是整数，可证,即即，这显然是成立的；又可证,即即，这显然也是正确的。于是，即,又因为是整数，从而;于是，即即,而但3102知为正整数）从而，显然，因而推得其中。例6。 （1999年，保加利亚数学奥林匹克试题） 求所有的自然数n的个救,4n 1023使得n在二进制表示下,没有连续的三个数码相同例7. （l995年南斯拉夫数学奥林匹克试题）设n是正整数，n的二进制表示中恰有1995个l，求证：2n-1995整除n！ 例8. (1982年英国数学奥林匹克试题）设自然数n为17的倍数，且在二进制写法中恰有三个数码为1。证明n的二进制写法中至少有六个数码为0，且若恰有7个数码为0，则n是偶数。 例9。 （第12届IM O试题）设a,b,n均大于1在a进制中，在b进制中，其中 证明：当且仅当ab时，例10已知利用的砝码可以使重量是连续自然数的63个重物平衡,求这组砝码例11。(2005年中国奥林匹克协作体夏令营试题）如果一个正整数在三进制下表示的各数字之和可以被3整除,那么我们称为“好的”，则前2005个“好的”正整数之和是多少？解：首先考虑“好的”非负整数,考察如下两个引理：引理1。在3个连续非负整数(是非负整数）中，有且仅有1个是“好的”。证明：在这三个非负整数的三进制表示中，0，1，2各在最后一位出现一次,其作各位数字相同，于是三个数各位数字之和是三个连续的正整数，其中有且仅有一个能被3整除（即“好的）,引理1得证。引理2.在9个连续非负整数(是非负整数)中,有且仅有3个是“好的”。把这3个“好的非负整数化成三进制，0,1，2恰好在这三个三进制数的最后一位各出现一次。证明：由引理1不难得知在9个连续非负整数（是非负整数）中，有且仅有3个是“好的。另一方面，在这三个“好的”非负整数的三进制表示中，最高位与倒数第三位完全相同，倒数第二位分别取0，1,2。若它使它们成为“好的非负整数，则最后一位不相同,引理2得证。将所有“好的”非负整数按从小到大的顺序排成一列，设第2004个“好的”非负整数为,根据引理1，得，即.设前个“好的”正整数之和为,由于前2003个“好的正整数之和等于前2004个“好的非负整数之和。因此;又因为和都是“好的”正整数。因此前2005年“好的”正整数之和是:。例12. 把所有3的方幂及互不相等的3的方幂的和排列成一个递增数列：10,12，13, 求这个数列的第100项例13. （第12届IM O试题）设a，b，n均大于1在a进制中，在b进制中，其中 证明：当且仅当ab时，课外练习题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。 设是正整数，定义数列和如下：若p是使得的数，求证：对所有使得是奇数的的和等于10. 设集合把A中各数按照从大到小的顺序排列，求第1997个数m为正整数，定义f（m)为m！ 中因数2的个数（即满足2km!的最大整数k）.证明有无穷多个正整数m，满足mf（m）=1989