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

　整数的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． 一个正整数，如果用进制表示为，如果用进制表示为，请用10进制表示这个数.解：由题意知：0＜a,c≤4,0≤b≤4,设这个正整数为n,则 n＝＝a×72＋b×7＋c, n==c×52＋b×5＋a ∴49a＋7b＋c＝25c＋5b＋a 48a＋2b－24c＝0 b＝12(c－2a) ∴12｜b,又∵0≤b≤4　∴b＝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的方幂形式： 易发现其项数恰好是自然数列对应形式的二进制表示： 即 由于100＝ 所以原数列的第100项为。 例4．（1987年加拿大数学竞赛试题）1987可以在b进制中写成三位数，如果，试确定所有可能的和。　　　　　　　　　　　　　　　　　　 解：易知，从而， 即， 由知。由知故； 又因为有12个正约数，分别为1,2，3,6，9,18,109,218,327,654,981,1962，所以，从而。 又由知 例5．（第3届加拿大数学竞赛试题）设是五位数（第一个数码不是零），是由取消它的中间一个数码后所成的四位数，试确定一切使得是整数。　　　　　　　　　　　 解：设，其中且；； 而是整数，可证，即 即，这显然是成立的； 又可证，即＜ 即，这显然也是正确的。 于是，即，又因为是整数，从而； 于是，即＝ 即，而但3　102知为正整数） 从而，显然，因而推得其中。 例6. (1999年，保加利亚数学奥林匹克试题)． 求所有的自然数n的个救，4≤n≤ 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