pascal算法讲义-第十三讲.pdfVIP

百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十三讲 第十三讲 初等数论基础 一、数论总述 数论是纯粹数学的分支之一，主要研究整数的性质。 按研究方法来看，数论大致可分为初等数论和高等数论。初等数 论是用初等方法研究的数论，它的研究方法本质上说，就是利用整数 环的整除性质，主要包括整除理论、同余理论、连分数理论。高等数 论则包括了更为深刻的数学研究工具。它大致包括代数数论、解析数 论、计算数论等等。 总而言之呢，数论是一门很高深的学科，有些命题是否看上去很 简单（我指的是容易理解），实际上证明起来却很复杂很麻烦，有些 命题看上去很复杂，实际上证明起来更复杂，所以对于一般的大学生 而言，数论都不是必修课，笔者能力也非常有限，但考虑到 NOIP、 NOI 系列考试会有对比较基础的初等数论的内容的考察，这里就冒昧 地为大家对初等数论的一些基础知识，联系编程实际稍作介绍。 这里我们想首先注明，本节内容涉及有关定理基本不会给出证明， 对数论特别有兴趣的同学，可以去查阅一些专门的有关数论的书籍， 例如潘承洞和潘承彪编写的《初等数论》等。 另外，我们也想说明，无论是计算机竞赛，还是数学竞赛，竞赛 考试考察的数论都不会是要求很高基础的，主要还是考察考生灵活运 用已经掌握知识的能力，其考察范围绝不会超出初等数论要求，绝不 会涉及高等数论内容。 第 1 页，共 34 页 百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十三讲 二、预备知识 首先介绍什么是自然数。 皮亚诺公理（Peano axioms），也称皮亚诺公式，是数学家皮亚 诺（皮阿罗）提出的关于自然数的五条公理系统。根据这五条公理可 以建立起一阶算术系统，也称皮亚诺算术系统。 皮亚诺的这五条公理用非形式化的方法叙述如下： Ⅰ)0 是自然数； Ⅱ)每一个确定的自然数 a，都有一个确定的后继数 a ，a也是 自然数。（数 a 的后继数 a就是紧接在这个数后面的整数（a+1）。 例 如，1=2，2=3 等等） Ⅲ)0 不是任何自然数的后继数； Ⅳ)如果 b、c 的后继数都是自然数 a，那么 b = c； Ⅴ)设 S ，且满足?N 2 个条件（i）0∈S；（ ii）如果 n∈S，那么 n∈S。则 S 是全体自然数的集合，即 S=N。(这条公理也叫归纳公理， 保证了数学归纳法的正确性) 依据归纳公理，产生了第一数学归纳法以及第二数学归纳法，这 些在高中阶段使用极广，我们就不多赘述了。 最小自然数定理（良序定理）： 自然数集的每个非空子集都有个 最小元素，即自然数在其标准的大小关系下构成一良序集。 该定理在 Peano 算术系统中是可以根据公理证明的。证明从略。 同样的还有最大自然数原理，就是在一个自然数集的有限子集中， 一定存在一个最大的自然数。 第 2 页，共 34 页 百度 Pascal 吧公开培训教材-Pascal 培训课程算法讲义-第十三讲 抽屉原理（鸽巢原理）： 如果 n+1 个物体被放进 n 个盒子，那么 至少有一个盒子包含两个或更多的物体。 这个原理有个加强。 抽屉原理加强（鸽巢原理加强）： 如果 mn+1 个物体被放进 n 个盒 子，那么至少有一个盒子包含 m+1 个或更多的物体。 这个可以用反证法证明，希望读者自行完成。 讲到抽屉原理，不得不说一下 Ramsey 定理。这是一个组合数学 图论中一个经典的定理，在介绍它之前，我们先看一个简单的数学竞 赛题。 例题 .1：求证：世界上任意 6 个人中，总有 3 个人相互 认识，