数论的方法和技巧 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． 一个正整数，如果用7进制表示为，如果用5进制表示为，请用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进制中，

其中
证明：当且仅当a>b时，

例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进制中，

其中
证明：当且仅当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整除的所有正整数n．

7. 若二进制数满足则称n为“二进制回文数”，问在不超过1988的正整数中有多少个“二进制回文数”？

8. 对每个正整数令 为n在k进制中的数字和，求证：对于小于20000的素数p，中至多有两个值为合数．

9. 设是正整数，定义数列和如下：
若p是使得的数，求证：对所有使得
是奇数的的和等于

10. 设集合
把A中各数按照从大到小的顺序排列，求第1997个数．

m为正整数，定义f(m)为m! 中因数2的个数（即满足2k|m!的最大整数k）。证明有无穷多个正整数m，满足m-f(m)=1989