5-1整除性 辗转相除_ou.pptVIP

第五章 数论基础 本章为数论的一部分。 数论是数学中最古老的分支之一。 公元前三世纪，古希腊数学家欧几里得所著《几何原本》中证明了质数的个数无穷多，并给出了求两个正整数公因数的算法（辗转相除法）。 公元前50年，在我国第一部数学名著《九章算术》的第一章中就开始讨论整数，介绍了辗转相除法，与欧几里得的辗转相除法是各自独立总结出来的。 四世纪时，在我国的《孙子算经》中对整数做了研究，给出了解一次同余式的算法，其中之一“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问至少物几何？ ”。把孙子所有算法推广开即闻名于世的孙子定理（秦九韶定理），国外称作中国剩余定理----初等数论中一个重要的定理。 数论主要用算术方法（加减乘除）研究整数性质。 任意两个整数相加、相减、相乘的结果仍是整数。但两个整数不一定能在整数的范围内相除，这是整数系统的特点，研究整数就针对这一特点加以分析，研究整数的性质基本上就是要研究整除性和因数分解等问题以及其它一些有关的问题。 数论特点：原理讲起来容易，应用起来很难，灵活性强。真正学好数论，不但需要数论的知识，还要有灵活、聪明的头脑，光死板学是学不好的。 数论包含内容很多，本章介绍其中最基本的知识，即，整数的一些最基本的性质。为下面三章作准备，因为抽象代数里一些较抽象的内容很多都可以在数论中找到根源和实例。 第五章 数论基础 §5.1 整除性 辗转相除 §5.2 互质 质因数分解 §5.3 合同 一次同余式 §5.4 秦九韶定理 Euler函数 §5.5 一元高次同余式 二次剩余 §5.1.1 整除及其性质 定义5.1.1 设a和b是任意整数，若存在整数c，使得a=bc，则称a是b的倍数，b是a的因数。或者称a被b整除，而b整除a。记为b|a。 Note: 1、任意整数整除0 ，特别0|0； 　但0不能整除任意整数。 2、1（-1）整除任意整数。 定理5.1.1 (带余除法定理) 对任意整数a和b，b?0，唯一存在一对整数q和r，使得 a=qb+r，0≤r＜|b|。 （q称为商数，r称为a被b除的余数。） 证明:(一）存在性 (1)若b0,a≥0，则算术中学过长除法，有q和r，使得a=qb+r，0≤r＜b。 (2) 若b0,a≤0 ，则取a’=-a，于是a’≥0。 由(1)知，对a’,b，有q’,r’，使得 a’= q’b+r’，0≤r’＜b。 于是 a=-a’=(-q’)b+(-r’) ①若r’=0，则取q=-q’，有a=qb ②若r’≠0，取r=b-r’，则0rb。于是 a=-a’=(-q’)b+r-b=(-q’-1)b+r 取q=-q’-1，有 a=qb+r，0＜r＜ |b| =b。 定理5.1.1 （3）若b? 0，而a任意，则取b’ =- b，于是 b’ 0 ，由(1)(2)知，存在q’，r’，使得 a=q’b’+r’，0≤r’?b’= |b| 。 即 a=q’(-b)+r’=(-q’)b + r’，0≤r’?|b| 故取q=-q’，r=r’，则得 a=qb+r，0≤r?|b| 。 综合(1)-(3)对任意b (b?0)，都有q，r，使得 a=qb+r 0≤r? |b| …………(?) 定理5.1.1 （二）q和r的唯一性。 设另有一对q’和r’满足 a=q’b+r’ 0? r’? |b| …………(??) 则(??) - (?)得 r’-r=(q-q’)b，从而有 |r’-r|=|q-q’||b|。注意到 |r’-r|?|b| ，而|q-q’|?0为整数，所以必有|q-q’|=0，从而 |r’-r|=0。即 q=q’，r=r’。 所以，唯一性成立。 推论 由整除的定义，易得如下推论： b|a，(b?0) 当且仅当a被b除（或者a除以b, 或者b除a）的余数为0。 练习题 设a，b是两个不全为0的整数, d = min{ax+by | ax+by0, x,y ? Z},证明d |（ as+bt ），其中s,t是任何整数。 整除的基本性质 性质1 若a|b，b|c，则a|c 证明：因为a|b，b|c，故有整数d，e使b=ad，c=be，因之，c=a(de)。而de是整数，所以a|c。 性质2 若a|b，则a|bc 证明：由定义知，b|bc。今a|b， 故由性质1，a|bc 整除的基本性质 性质3 若a|b，a|c，则a|b?c。 证明：因为a|b，a|c，故有整数d，e使b=ad，c=ae。因之，b?c=a(d?e)。而d?e为整数，所以a|b?c。 性质4 若a整除b1,…,bn, 则a| ?1b1+…+ ?nbn，