整数的因子分解

《整数的因子分解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章整数的因子分解整除的概念带余数除法最大公因数与辗转相除法整除的进一步性质质数（素数）算术基本定理取整函数及其在数论中的一个应用第一章整数的因子分解$1整除的概念带余数除法2、整除的基本定理定理1（传递性）：ab，bcac定理2：若a，b都是m的倍数，则ab都是m的倍数3、带余数除法带余除法的应用举例例1证明形如3n-1的数不是平方数。例2、任意给出的5个整数中，必有3个数之和被3整除。$2最大公因数与辗转相除法2、任意整数的最大公因数可转化为正整数来讨论3、下面先讨论两个非负整数的最大公因数定理2

2、设b是任一正整数，则(i)0与b的公因数就是b的因数，反之，b的因数也就是0与b的公因数。(ii)(0,b)=b。4、定理3设a,b,c是三个不全为零的整数，且a=bq+c其中q是非零整数，则a,b与b,c有相同的公因数，因而(a,b)=(b,c)5、计算最大公约数的算法——辗转相除法，又称Euclid算法。它是数论中的一个重要方法，在其他数学分支中也有广泛的应用。定义下面的一组带余数除法，称为辗转相除法。说明：（1）利用辗转相除法可以求两个整数的最大公因数解：因为735000=238948×3+18156，23

3、8948=18156×13+292018156=2920×6+6362920=636×4+376636=376×1+260376=260×1+116260=116×2+28116=28×4+428=4×7所以（735000，238948）=4.例1：求（735000，238948）.例2：求（2605，-5125）.解：因为5125=2605×1+2520，2605=2520×1+852520=85×29+5585=55×1+3055=30×1+2530=25×1+525=5×5所以（2605，-5125）=5.

4、6、最大公因数的两个性质对于两个以上整数的最大公因数问题，不妨设例3：求（2605，3245，7250）.解：先求2065和3245的最大公因数。因为3245=2605×1+1180，2605=1180×1+8851180=885×1+295885=295×3所以（2605，3245）=295.再求295与7250的最大公因数。7250=295×24+170，295=170×1+125170=125×1+45125=45×2+3545=35×1+1035=10×3+510=5×2所以（2605，3245，7250

5、）=（295，7250）=5.本节最后介绍另外一种求两个整数最大公因数的方法，先给出下面几个结果：即当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所以，命题得证。$3整除的进一步性质及最小公倍数例用辗转相除法求(125,17)，以及x，y，使得12

6、5x17y=(125,17)。解做辗转相除法：则对于两个以上整数的最小公倍数问题，不妨设注：多项式的带余除法类似于整数的带余除法$4质（素）数算术基本定理一、质（素）数1、定义一个大于1的整数，如果它的正因数只有1及它本身，就叫做质数（或素数）；否则就叫合数。2、与素数相关的性质定理证：必要性显然。对于一个给定的整数，我们根据上述定理不仅可以判别它是否是素数，且还可以找出所有不大于它的素数把1划去，剩下第一个数是2,2是素数。从2起划去它后面所有2的倍数，剩下的第一个数是3，它不是2的倍所以它是素数。依次，当我

7、们把所有的不大于的素数。这种方法是希腊时代幼拉脱斯展纳发明的，好像用筛子筛出素数一样，称幼拉脱斯展纳筛法。数的素性检验方法问题在近几年得到了飞速的发展。过去,要检验一个数是否是素数，最简单方法是试除法。若用计算机编成程序，对于10位数，几乎瞬间即可完成，对于一个20位数，则需要2个小时，对于一个50位数就需要一百亿年，令人吃惊的是，要检验一个一百位数，需要的时间就猛增到1036年。到了1980年,这种困难的情况得到了改观,阿德曼(Adleman),鲁梅利(Rumely),科恩(Cohen),和伦斯特拉(Lenst

8、ra)研究出一种非常复杂的技巧,现在以他们的名字的首字母命名的ARCL检验法。检验一个20位数只消10秒钟,对于一个50位数用15秒钟,100位数用40秒钟，如果要他检验一个1000位数，只要用一个星期也就够了。但是大部分的素性检验法都不能分解出因数来，只能回答一个数是否是素数.定理3、素数的个数是无穷的。注：2000多年前，古希腊数学家欧几里得（前330-前275），著