竞赛数学中的初等数论0.pdf

《竞赛数学中的初等数论》 贾广素 编著 2006-8-21 序 言 数论是竞赛数学中最重要的一部分，特别是在 1991 年，IMO 在 中国举行，国际上戏称那一年为数论年，因为 6 道 IMO 试题中有 5 道与数论有关。 数论的魅力在于它可以适合小孩到老头，只要有算术基础的人均 可以研究数论――在前几年还盛传广东的一位农民数学爱好者证明 了哥德巴赫猜想，当然，这一谣言最终被澄清了。可是这也说明了最 难的数论问题，适合于任何人去研究。 初等数论最基础的理论在于整除，由它可以演化出许多数论定理。 做数论题，其实只要整除理论即可，然而要很快地解决数论问题，则 要我们多见识，以及学习大量的解题技巧。这里我们介绍一下数论中 必需的一个内容：对于a,b N , q, r N ，满足a bqr ，其中0  r  b 。 除了在题目上选择我们努力做到精挑细选，在内容的安排上我们 也尽量做到讲解详尽，明白。相信通过对本书学习，您可以对数论有 一个大致的了解。希望我们共同学习，相互交流，在学习交流中，共 同提高。 编者：贾广素 2006-8-21 于山东济宁 第一节 整数的 p 进位制及其应用 正整数有无穷多个，为了用有限个数字符号表示出无限多个正整数，人们发明了进位制， 这是一种位值记数法。进位制的创立体现了有限与无限的对立统一关系，近几年来，国内与 国际竞赛中关于“整数的进位制”有较多的体现，比如处理数字问题、处理整除问题及处理 数列问题等等。在本节，我们着重介绍进位制及其广泛的应用。 基础知识 给定一个 m 位的正整数 A ，其各位上的数字分别记为am1 , am2 ,, a0 ，则此数可以简 记为： A am1am2 a0 （其中am1  0 ）。 由于我们所研究的整数通常是十进制的，因此 A 可以表示成 10 的m  1次多项式，即 A a 10m1 a 10m2 a 10a ，其中ai {0,1,2,,9},i 1,2,, m 1且 m1 m2 1 0 a  0 ，像这种 10 的多项式表示的数常常简记为A (a a a ) 。在我们的日常 m1 m1 m2 0 10 生活中，通常将下标 10 省略不写，并且连括号也不用，记作A am1am2 a0 ，以后我们 所讲述的数字，若没有指明记数式的基，我们都认为它是十进制的数字。但是随着计算机的 普及，整数的表示除了用十进制外，还常常用二进制、八进制甚至十六进制来表示。特别是 现代社会人们越来越显示出对二进制的兴趣，究其原因，主要是二进制只使用 0 与 1 这两种 数学符号，可以分别表示两种对立状态、或对立的性质、或对立的判断，所以二进制除了是 一种记数方法以外，它还是一种十分有效的数学工具，可以用来解决许多数学问题。 为了具备一般性，我们给出正整数A 的p 进制表示： A a p m1 a p m2 a p a ，其中 ai {0,1,2,,p 1},i 1,2,,m 1 且 m1 m2 1 0 a  0 。而m 仍然为十进制数字，简记为A (a a a ) 。 m1 m1 m2 0 p 典例分析 例 1．将一个十进制数字 2004（若没有指明，我们也认为是十进制的数字）转化成二进制与 八进制，并将其表示成多项式