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