初等数论-第一章.pptx

一、整除的概念带余数除法二、最大公因数与辗转相除法第一章整数的可除性三、整除的进一步性质四、质数算术基本定理五、取整函数及其在数论中的一个应用

第一节整除的概念带余数除法

整除的基本定理定理1（传递性）：a?b，b?c?a?c定理2：若a，b都是m的倍数，则a?b都是m的倍数

3、带余数除法PART1

带余数除法的应用举例例1证明形如3n-1的数不是平方数。

例2、任意给出的5个整数中，必有3个数之和被3整除。

单击此处添加小标题第二节最大公因数与辗转相除法单击此处添加小标题任意整数的最大公因数可转化为正整数来讨论

3、下面先讨论两个非负整数的最大公因数添加标题定理2、设b是任一正整数，则（i)0与b的公因数就是添加标题(ii)(0,b)=b添加标题b的因数，反之，b的因数也就是0与b的公因数。添加标题定理3设a,b,c是三个不全为零的整数，且添加标题a=bq+c添加标题其中q是非零整数，则a,b与b,c有相同的公因数，添加标题因而(a,b)=(b,c)

下面要介绍一个计算最大公约数的算法——辗转相除法，又称Euclid算法。它是数论中的一个重要方法，在其他数学分支中也有广泛的应用。定义下面的一组带余数除法，称为辗转相除法。

说明：利用辗转相除法可以求两个整数的最大公因数

6、最大公因数的两个性质01

对于两个以上整数的最大公因数问题，不妨设

PARTONE本节最后介绍另外一种求两个整数最大公因数的方法，先给出下面几个结果：

即当a与b是正整数时，只要使用被2除的除法运算和减法运算就可以计算出(a,b)例1、求（12345,678）解：（12345,678）=（12345，339）=（12006,339）=（6003,339）=（5664,339）=（177,339）=（177,162）=（177，81）=（96,81）=（3,81）=3

所以，命题得证。

第三节整除的进一步性质及最小公倍数

解做辗转相除法：例用辗转相除法求(125,17)，以及x，y，使得125x?17y=(125,17)。

则

对于两个以上整数的最小公倍数问题，不妨设注：多项式的带余除法类似于整数的带余除法

一、质（素）数第四节质（素）数算术基本定理定义一个大于1的整数，如果它的正因数只有1及它本身，就叫做质数（或素数）；否则就叫合数。与素数相关的性质定理

注：利用第三节推论2.2证明。第一章

证：必要性显然。

添加标题对于一个给定的整数，我们根据上述定理不仅可以添加标题后面所有2的倍数，剩下的第一个数是3，它不是2的倍添加标题判别它是否是素数，且还可以找出所有不大于它的素数添加标题所以它是素数。添加标题把1划去，剩下第一个数是2,2是素数。从2起划去它添加标题依次，当我们把所有的不大于添加标题的素数。添加标题这种方法是希腊时代幼拉脱斯展纳发明的，添加标题好像用筛子筛出素数一样，称幼拉脱斯展纳筛法。

数的素性检验方法问题在近几年得到了飞速的发展,1若用计算机编成程序,对于10位数,几乎瞬间即可完成,2对于一个20位数,则需要2个小时,对于一个50位数就需3要一百亿年,令人吃惊的是,要检验一个一百位数,需要4的时间就猛增到10^36年.到了1980年,这种困难的情况5得到了改观,阿德曼(Adleman),鲁梅利(Rumely),科恩6(Cohen),和伦斯特拉(Lenstra)研究出一种非常复杂的7过去,要检验一个数是否是素数，最简单方法是试除法，8

01检验一个20位数只消10秒钟,对于一个50位数用15秒钟,单击此处添加小标题02100位数用40秒钟,如果要他检验一个1000位数,只要用单击此处添加小标题03一个星期也就够了.但是大部分的素性检验法都不能分单击此处添加小标题04解出因数来,只能回答一个数是否是素数.单击此处添加小标题05技巧,现在以他们的名字的首字母命名的ARCL检验法单击此处添加小标题

定理3、素数的个数是无穷的。添加标题注：2000多年前，古希腊数学家欧几里得（前330-添加标题前275），著有《几何原本》，他在此书中率先证明了添加标题受到历代数学家的推崇，因为这一定理及其证明既简洁、添加标题优美而不失深刻。其证明思路如下：添加标题素数的无限性，这个证明一直被当作数学证明的典范，

证明:假设正整数中只有有限个质数，设为第一章节

关于素数的个数，有著名的素数定理：下面列举的数字也可以说明定理的真实性。

许多学者都做过深入的研究，但都没有成功。1896年，法国数学家哈达马及比利时数学家德.瓦利-普斯因同时独立地证明了它，他们是用黎曼zata函数获