第一章 (3) 质数 算术基本定理 函数[x],{x}

《第一章 (3) 质数 算术基本定理 函数[x],{x}》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、质数.算数基本定理函数[x],{x}及其应用复习最大公因数与辗转相除法定义设aa,,,a是nn(2)个整数.若整数d12n是它们之中每一个的因数,那么d就叫作aa,,,a12n的一个公因数.整数aa,,,a的公因数中最大的一个叫作最大12n公因数,记作(,aa,,a),若(,aa,,a)1,我们说12nn12aa,,,a互质或互素,若aa,,,a中每两个整数互质，12nn12我们就说它们两两互质.2定理1若aa,,a,n是任意个不全为零的12n整数,则(i)aa,a,,a,与a,a,的公因数相同；1212nn(ii)(aa,a,a,

2、aa)(,,,)1212nn3定理2若bb是任一正整数,则(i)0与的公因数就是bb的b因数,反之,的因数也是0与的公因数.(ii)(0,)bb.定理3设abc,,是任意三个不全为0的整数,且abqc,其中q是非零整数,则ab,与bc,有相同的公因数,因而(,)(,).abbc4设ab,是任意两个正整数,由带余数除法,我们有下面的系列等式：abqr,0rb<,111brqr,0r<,r12221(1)rrqr,0r

3、余数除法,余数就至少减一，而bb是有限的,所以我们最多进行次带余数除法，总可以得到一个余数是零的等式,即r=0.(1)式n+1所指的计算方法,.叫作辗转相除法在西方常把它叫做欧几里得除法.它就是我国著名的古代数学著作《九章算术》中提出的“更相减损术”.6辗转相除法的应用求出两个正整数的最大公因数推出最大公因数的重要性质解一次不定方程的基本工具7辗转相除法在密码学中的应用RSA算法的重要部分还被用来解丢番图方程，寻找满足中国剩余定理得数，或者求有限域的倒数。还可以用来构造连分数，在一些整数分解算法中也有应用。同时在处理大数时

4、非常高效，它需要的步骤不会超过较小数的位数（十进制下）的五倍。8定理4若ab,(,)ab是任意两个整数,则就是(1)中最后一个不等于零的余数,即(,)ab.rn推论4.1ab,(,)ab的公.因数与的因数相同9定理5设ab,是任意两个不全为零的整数(i)若mambm是任意abm一正整数，则,,abab,()ii若,,是ab的任一公因数，则，ab特别,1ab,,ab10现在来研究两个以上整数的最大公因数.由定理12及，,,,.不妨假设aaan是任意个正整数12n令aa12,2,

5、,2,3d,3,da1(2)ddadnnn定理6,若,aa1,,2a1,2n,aa.n是nna个d整数,则11定理1,,若ab是任意两个正整数则k1QaPbkkkrkn1,1,,;(2)其中PP1,qP,,qPP01112kkkkQQQ0,qQ1,,(3)Q0112kkkkkn2,,12推论1.1,,若ab是任意两个不全为零的整数则存在两个整数st,,(4)asbt使得ab定理2,,若,,abc1,是ac三个整数且则(,i),abcbc与有相同的公因数，()i

6、i,,(5)abcbc上面假定了abc,,.至少一个不为零13推论2.1若ac,1,cab,.cb则推论2.2,设,aa,,,abb,.及b是任意两组整数1212nm若前一组中任一整数与后一组中任一整数互质,则aaa与bbb互质.1212nm14定义设aa12,,,an是nn2个整数.若d是这n个数的倍数,则d就叫作这n个数的一个公倍数.又在aa,,,a的12n一切公倍数中的最小正数叫作最小公倍数,记作[aa,,,a].12n由于任何正数都不是0的倍数,故讨论整数的最小公倍数时,一概假定这些整数都不是零.定理3[,

7、aa,,a][a,a,,a].12nn1215定理4设ab,,ab是任意两个正整数,则(i)的所有公倍数就是ab,,ab的所有倍数;(ii)的最小公倍数等于以它们的最大公因数除它们的乘积所得的商,ab即ab,.,1,ab,.ab特ab别的,若则ab,16现在来研究两个以上整数的最小公倍数.设aa,,,a是任意n个正整数.12n令aa1,2m2,ma2,3m3,,mn1,anmn(7)定理5若aa12,a,nn,2n是个整数,则aa12,a,m,.nn17§4质数.算数基本定理

8、定义一个大于1的,正整数如果它的正因数只有1及它本身，就叫做质数（或素数）；否则叫做合数.18定理1设aa是任一大于1的整数,则的除1外最小正因数q是一质数,并且当a是合数时，qa.[证]假定qq不是质数