《整除带余除法辗转》PPT课件.ppt

《《整除带余除法辗转》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、专业基础课程初等数论NumberTheory邯郸学院数学系石立叶13第二章不定方程求解2第一章整数的整除性前言4第三章同余式求解初等数论前言主要内容主要内容发展过程初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布以及数论函数等内容，统称初等数论（elementarynumbertheory）。古代近代现代整除概念整除性质带余除法近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。1801年，高斯的《算术探究》是数论的划时代杰作。1、古希腊欧几里德的《几何原本》：证明了素数有无穷多个；求两个自然数的最大公约数的方法，即所谓欧

2、几里得算法。2、中国《孙子算经》：中国剩余定理”由于自20世纪以来引进了抽象数学和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等新分支。而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算方法等领域内更得到了广泛的应用第一章整数的整除性1.整除概念和带余除法2.最大公因数和辗转相除法3.质数的性质及最小公倍数4.质数.算数基本定理第一节整除的概念带余除法定义设a,b是任意两个整数，其中如果存在一个整数q，使得(1)成立，我们就说b整除a,或a能被b整除，记作：，b叫做因数，a叫做倍数。若这样的q不存在，则称b不能整

3、除a,或a不能被b整除，记做ba整除概念整除性质带余除法例2和-6，2和7的关系例6的因数，-6的因数。注：1、因数不能为零，但0不是因数，q是0的因数，所以，任何非零整数都是零的因数2、6和-6的因数相同???定理1若，则证：定理2：若定理3：若第一节整除的概念带余除法整除概念整除性质带余除法例若n是奇数，则8n21。解设n=2k1，则n21=(2k1)21=4k(k1)，在k和k1中有一个是偶数，所以8n21例以d(n)表示n的正约数的个数，例如：d(1)=1，d(2)=2，d(3)=2，d(4)=3，问：d(1)d(2)d(1997)是否为偶数？

4、提示：442<1997<452第一节整除的概念带余除法整除概念整除性质带余除法带余除法：若a和b是两个整数，其中b>0,则存在两个整数q及r,使得（2）成立，而且q及r是唯一的q叫做a被b整除所得的不完全商，r叫做a被b整除所得的余数第一节整除的概念带余除法整除概念整除性质带余除法注：带余除法要注意两点:b>0例：a=255,b=15,求商和余数a=417,b=15,求商和余数a=-81,b=15,求商和余数例：a是两位数，a除310的余数为37，则a=?例：证明，其中n是任何整数第一节整除的概念带余除法整除概念整除性质带余除法第一节整除的概念带余除法回顾：倍数和因数性质带余除法第

5、二节最大公因数与辗转相除法定义设是个整数，若d是它们之中每一个的因数，那末d就叫做的一个公因数最大公因数整数的公因数中最大的一个，记作：若=1，我们说互素，或互质若每两个整数互质，两两互质公因数概念公因数性质辗转相除法定理1：若是任意n个不全为零的整数，则(1)与的公因数相同(2)例:(6,-4)=(6,4)所以，我们只要讨论非负整数的公因数，公因数概念公因数性质辗转相除法第二节最大公因数与辗转相除法设a,b是非负整数，分情况：(1)两个都为零最大公因数不存在(2)有一个为零设a=0,（a,b）=(0,b)=b(3)两个都不为零即定理3设a,b,c是任意三个不全为零的整数，且a=b

6、q+c,q是不等于零的整数，则a,b和b,c的公因数相同，因而(a,b）=(c,b)两个都不为零(1)(2)a不整除b，或b不整除a第二节最大公因数与辗转相除法公因数概念公因数性质辗转相除法定理4若a和b是任意两个整数，则(a,b)等于(2)式中倒数第一个不为零的余数，即（2）式所提供求最大公因数的方法叫做辗转相除法，也称欧几里德算法例求(1859,1573)例求(169,121)例①用欧几里德算法求(1997,57).②用1997和57的线性组合表示(1997,57)．③求1997和57的所有公因数．第二节最大公因数与辗转相除法公因数概念公因数性质辗转相除法定理5设a,b是任意两

7、个不全为零的整数，(1)若m是任意正整数，则（am,bm）=(a,b)m(2)若是a,b任一公因数，则特别的定理6若是任意n个不全为零的整数，则公因数概念公因数性质辗转相除法第二节最大公因数与辗转相除法练习：判断：1、任意非零整数b,（0,b）=b2、设m是任意非零整数，则（am,bm）=(a,b)m3、设-2是a,b的公因数，则4、如果a,b是两个整数,,则存在唯一的整数对,使得,其中第二节最大公因数与辗转相除法公因数概念公因数性质辗转相除法辗转相除法和带余除法的关