初等数论_.doc

(完整word版)《初等数论》
(完整word版)《初等数论》
(完整word版)《初等数论》

第一节整数的p进位制及其应用
正整数有无穷多个，为了用有限个数字符号表示出无限多个正整数，人们发明了进位制，这是一种位值记数法.进位制的创立体现了有限与无限的对立统一关系，近几年来，国内与国际竞赛中关于“整数的进位制"有较多的体现,比如处理数字问题、处理整除问题及处理数列问题等等。在本节，我们着重介绍进位制及其广泛的应用。
基础知识
给定一个m位的正整数A,其各位上的数字分别记为，则此数可以简记为：（其中)。
由于我们所研究的整数通常是十进制的,因此A可以表示成10的次多项式，即，其中且，像这种10的多项式表示的数常常简记为。在我们的日常生活中，通常将下标10省略不写，并且连括号也不用，记作,以后我们所讲述的数字,若没有指明记数式的基,我们都认为它是十进制的数字。但是随着计算机的普及，整数的表示除了用十进制外，还常常用二进制、八进制甚至十六进制来表示。特别是现代社会人们越来越显示出对二进制的兴趣,究其原因，主要是二进制只使用0与1这两种数学符号,可以分别表示两种对立状态、或对立的性质、或对立的判断，所以二进制除了是一种记数方法以外，它还是一种十分有效的数学工具，可以用来解决许多数学问题。
为了具备一般性，我们给出正整数A的p进制表示：
，其中且。而仍然为十进制数字，简记为。
典例分析
例1．将一个十进制数字2004(若没有指明，我们也认为是十进制的数字）转化成二进制与八进制，并将其表示成多项式形式.
分析与解答
分析：用2作为除数（若化为p进位制就以p作为除数),除2004商1002,余数为0;再用2作为除数，除1002商501余数为0；如此继续下去，起到商为0为止。所得的各次余数按从左到右的顺序排列出来，便得到所化出的二进位制的数。
解:
各次商数被除数除数013715316212525050110022004211111010100各次余数故，；
同理,有,。
处理与数字有关的问题，通常利用定义建立不定方程来求解。
例2．求满足的所有三位数。（1988年上海市竞赛试题)
解：由于，则，从而;
当时，；
当时,；
当时，；
当时，；
当时,；
于是所求的三位数只有512.
例3．一个四位数，它的个位数字与百位数字相同。如果将这个四位数的数字顺序颠倒过来(即个位数字与千位数字互换,十位数字与百位数字互换），所得的新数减去原数，所得的差为7812，求原来的四位数。
（1979年云南省竞赛题)
解:设该数的千位数字、百位数字、十位数字分别为，则
原数=1\＊GB3①
颠倒后的新数=2\＊GB3②
由=2\*GB3②－=1\*GB3①得7812＝
即=3\*GB3③
比较=3\＊GB3③式两端百位、十位、个位数字得
由于原四位数的千位数字不能为0，所以,从而，又显然百位数字,所以.所以所求的原四位数为1979。
例4．递增数列1,3，4,9，10，12，13，……是由一些正整数组成，它们或是3的幂，或是若个不同的3的幂之和，求该数列的第100项.（第4届美国数学邀请赛试题)
解:将已知数列写成3的方幂形式：

易发现其项数恰好是自然数列对应形式的二进制表示：
即
由于100＝
所以原数列的第100项为.
例5．1987可以在b进制中写成三位数，如果，试确定所有可能的和。（1987年加拿大数学竞赛试题）
解:易知，从而，
即，
由知。由知故；
又因为有12个正约数,分别为1,2，3，6，9,18,109,218，327，654,981,1962，所以,从而。
又由知
例6．设是五位数（第一个数码不是零），是由取消它的中间一个数码后所成的四位数，试确定一切使得是整数。(第3届加拿大数学竞赛试题）
解:设，其中且;；
而是整数，可证,即
即,这显然是成立的；
又可证，即＜
即，这显然也是正确的.
于是，即，又因为是整数，从而；
于是,即＝
即，而但3102知为正整数）
从而，显然，因而推得其中.
例7．若且是其各位数字和的倍数，这样的有多少个？
（2004年南昌竞赛试题)
解:(1）若为个位数字时,显然适合，这种情况共有9种;
（2）若为100时，也适合；
（3）若为二位数时，不妨设，则，由题意得
即即也就是；
若显然适合，此种情况共有9种；
若，则由,故
若，则显然可以，此时共有2＋8＝10个；
若（)9，则或，这样的数共有24，42，48,84共4个；
综上所述,共有9＋1＋9＋10＋4＝33个。
例8．如果一个正整数在三进制下表示的各数字之和可以被3整除，那么我们称为“好的”，则前2005个“好的”正整数之和是多少？（2005年中国奥林匹克协作体夏令营试题）
解：首先考虑“好的”非负整数，考察如下两个