《《离散数学》课件：5-2互质 质因数分解》由会员分享，可在线阅读，更多相关《《离散数学》课件：5-2互质 质因数分解（23页珍藏版）》请在金锄头文库上搜索。
1、5.2 互质互质 质因数分解质因数分解 5.2.1 整数互质整数互质 定义定义5.2.1 若若a，b除除1外无其它公因数，则外无其它公因数，则我们说我们说a和和b互质。互质。据定义，据定义，a和和b互质，必要而且只要互质，必要而且只要a，b的的最高公因数为最高公因数为1，且，且1和任意整数互质。和任意整数互质。定理定理5.2.1 a和和b互质，当且仅当互质，当且仅当1可表示为可表示为a和和b的倍数的倍数和形式，即存在整数和形式，即存在整数s和和t使使1=sa+tb。 证明：证明：必要性必要性；由；由a和和b互质知，互质知，a和和b的最的最高公因数为高公因数为1，从而存在，从而存在s，t，使使s
2、a+tb=1。充分性充分性；只需证：若存在；只需证：若存在s，t，使使sa+tb=1，则则a和和b的最高公因数的最高公因数d=(a,b)为为1。假设。假设d=(a,b) 1，则则d|a，d|b，从而从而d整除整除sa+tb=1的左端，因此的左端，因此d|1，矛盾。矛盾。 定理定理5.2.2 若若a和和b互质，而互质，而a bc，则则a c。证明：证明：因为因为a，b互质，故有互质，故有s，t使使1=sa+tb，从而从而c=sac+tbc (1)今因今因abc，故故a整除整除(1)右边每一项，因而右边每一项，因而a c。 定理定理5.2.3 若若b和和a1,a2,ak都互质，则都互质，则b和和a
3、1a2an互互质。质。证明：证明：由题设，对由题设，对i=1,2,n，有有si，ti使使sib+tiai=1把所有这把所有这n个式子乘起来，右边得个式子乘起来，右边得1，左边，左边有有2n项，其中有一项包含项，其中有一项包含a1a2an，而其余而其余各项都包含各项都包含b，所以，乘起来的式子如下：所以，乘起来的式子如下：Sb+Ta1a2an=1由定理由定理5.2.1得，得，b和和a1a2an二者互质。二者互质。 定理定理5.2.4若若m1,m2,mk两两互质而都整除两两互质而都整除a，则则m1m2mk|a。证明：证明：从简单到复杂对从简单到复杂对k进行归纳。进行归纳。当当k=1时，结论显然。时
4、，结论显然。当当k=2时，由于时，由于m1|a，所以存在整数所以存在整数q使得使得a=m1q。又又m2|a，即即m2|m1q，而而(m1, m2)=1，故故m2|q(定理定理5.2.2)，于是存在，于是存在p，使使q=m2p。从而从而a=m1m2p，即即 m1m2|a。 定理定理5.2.4假定对假定对i(1ik) 有有 m1m2mi|a (2)我们证明我们证明 m1m2mimi+1|a(3)由由(2)知有知有q使使 a=m1m2miq (4) 今今mi+1|a，且且由由定定理理5.2.3知知mi+1和和m1m2mi互互质质，故故由由定定理理5.2.2，mi+1|q。据据此此及及(4)知知(3)
5、成成立立。归纳证毕。归纳证毕。 例例5.2.1试证相继三个整数之积能被试证相继三个整数之积能被6整除。整除。证明：证明：三个相继整数必有一个为偶数，且三个相继整数必有一个为偶数，且必有一个为必有一个为3的倍数，即的倍数，即2|n(n+1)(n+2)，3| n(n+1)(n+2)。而而( (2，3) )=1，故，故6|n(n+1)(n+2)。 例例5.2.2试证相继三个整数的立方和是试证相继三个整数的立方和是9的倍数。的倍数。证明：证明：设设 n-1，n，n+1为三个相继整数，为三个相继整数，则则 (n-1)3+n3+(n+1)3=3n3+3n2-3n2+6n-1+1 =3(n3+2n)=3(n
6、3+3n-n)=3(3n+n(n2-1)=9n+3(n-1)n(n+1)而由上例而由上例5.2.1知知3|(n-1)n(n+1)，故故9|(n-1)3+n3+(n+1)3)。 例例5.2.3 试证试证2p-1和和2q-1互质的充要条件是互质的充要条件是p和和q互质。互质。证明：证明：必要性；假若必要性；假若p和和q不互质，不互质，(p,q)=a 1，记记p=ap1，q=aq1，则则2p-1=2ap1-1，2q-1=2aq1-1。有公因数有公因数2a-1 1，矛盾。矛盾。充分性；设充分性；设 (p,q)=1，(2p-1,2q-1)=d，往证往证d=1。不妨设不妨设 p q，辗转相除得辗转相除得
7、p=ql1+r1，q=r1l2+r2，rn-2=rn-1ln+rn，rn-1=rnln+1。由于由于(p,q)=1，故故rn=1。因为因为 2p-1=2ql1+r1-1 =2r1(2ql1-1)+2r1-1 =(2q-1)N+(2r1-1)，所以所以(2q-1,2r1-1)=d。同理推得同理推得 d=(2r1-1,2r2-1)= =(2rn-1-1,2rn-1)=1。 例例5.2.4若若(ai,bj) = 1，1 i n，1 j m，则则 (a1a2an,b1b2bm)=1。特别当特别当(a,b) = 1时，时，(an,bm) = 1，n,m为任意正整数。为任意正整数。证明：证明：由由(ai,
8、bj)=1， 1 j m ，得得( (ai, b1b2bm) )=1， 1 i n ，进而进而(a1a2an,b1b2bm) = 1。取取ai=a，bj=b，则则（an,bm）=1。 例例5.2.5 设设a,b为大于为大于1的自然数，的自然数，b a，且且(a,b)=1，则则logab 是无理数。是无理数。证明：反证法。若不然，证明：反证法。若不然，logab=p/q为有理为有理数。因数。因b a，知知p，q是正整数，且是正整数，且（p,q）=1。从而得从而得 ap/q=b，即即ap=bq。因为因为 (a,b)=1，由上例由上例5.2.4知（知（ap,bq）=1，与与ap=bq矛盾。矛盾。 设
9、设f(x)=anxn+an-1xn-1+a0是整系数多项式，是整系数多项式，若若10|f(2)，10|f(5)，则则10|f(10)。证明：证明：注意到注意到 f(10) =an10n+an-110n-1+a0，所以所以10|f(10)当且仅当当且仅当10|a0。因为因为10|f(2)，所以所以2|f(2)，于是于是2|a0，同样同样5|a0。由（由（2，5）=1得得10| a0。 例例5.2.6 5.2.2 质数与合数质数与合数算术基本定理算术基本定理 一个正整数，如果不等于一个正整数，如果不等于1而且除了自己和而且除了自己和1没有其它正因数，则称其为一个没有其它正因数，则称其为一个质数质数
10、(也也称为称为素数素数)；否则称其为；否则称其为合数合数。 例如：例如：2，3，5，7，11，都是质数。都是质数。1既既不是质数也不是合数。不是质数也不是合数。1之所以要摒于质数之所以要摒于质数之外，是因为它完全没有质数所具备的那之外，是因为它完全没有质数所具备的那些重要的数论性质。些重要的数论性质。 定义定义5.2.2质数质数p和和a互质，必要而且只要互质，必要而且只要p|a。事实上，事实上，若若p|a，则则p和和a除除1外还有公因数外还有公因数p，故二故二者不互质。若者不互质。若p|a，则则p当然就不是当然就不是p,a的公的公因数；但除了因数；但除了p，只有只有1才可能是才可能是p的因数，
11、的因数，所以只有所以只有1才可能是才可能是p,a的公因数，即二者的公因数，即二者互质。显然任意两个不同的质数互质。互质。显然任意两个不同的质数互质。 若质数若质数p整除整除a1a2an，则则p整除整除a1，a2，an之一。之一。证明：证明：假若假若a1，a2，an都不能被都不能被p整除，整除，则则p和它们都互质，故由定理和它们都互质，故由定理5.2.3，p和它和它们的乘积互质，因而们的乘积互质，因而p将不能整除此乘积，将不能整除此乘积，矛盾。矛盾。 定理定理5.2.5 任意正整数任意正整数n（n 1）恰有一法写成质数的恰有一法写成质数的乘积（不计因数乘积的顺序）。乘积（不计因数乘积的顺序）。
12、证明：证明：先证先证n可以写成质数的乘积。可以写成质数的乘积。用数学归纳法，用数学归纳法， n=2时时, ,显然成立，因为显然成立，因为2是质数，算是已经写成了质数的乘积。是质数，算是已经写成了质数的乘积。假定假定na时时n可以写成质数的乘积，可以写成质数的乘积，试证试证n=a时也可以这样写。时也可以这样写。定理定理5.2.6 ( (算术基本定理算术基本定理) ) 若若a是质数，则是质数，则a算是已经写成了质数的乘算是已经写成了质数的乘积。积。若若a不是质数，于是，不是质数，于是，a有因数有因数b，1ba。因之，因之，a=bc，1ca。既然既然b和和c都都a，故由故由归纳假定，归纳假定，b 和
13、和c都可以写成质数的乘积。都可以写成质数的乘积。又又a=bc，只要把这两个乘积连接起来就把只要把这两个乘积连接起来就把a写成了质数的乘积。归纳法已经完成，所写成了质数的乘积。归纳法已经完成，所以任意正整数以任意正整数n（n 1）可以写成质数的乘可以写成质数的乘积。积。 定理定理5.2.6 ( (算术基本定理算术基本定理) ) 再证再证n只有一法写成质数的乘积，换句话说，只有一法写成质数的乘积，换句话说，如果如果n=p1ph=q1qk (5)而而p1,ph，q1,qk都是质数，则都是质数，则h=k，而而且且p1,ph和和q1,qk完全一样，最多次序不完全一样，最多次序不同。同。由由(5)，p1|
14、q1qk，故由定理故由定理5.2.5，p1应整应整除除q1,qk之一，颠倒后者的次序，可假定之一，颠倒后者的次序，可假定p1|q1。今今q1是质数，只有是质数，只有q1和和1两个正因数，两个正因数，而而p1 1，故故p1必等于必等于q1。定理定理5.2.6 ( (算术基本定理算术基本定理) ) 由由(5)消去消去p1而得而得p2ph=q2qk由此同上可证由此同上可证p2应整除应整除q2,qk之一。如此之一。如此类推，可见类推，可见p1,ph和和q1,qk完全一样，最完全一样，最多次序不一样。不可能一边已经消完而另多次序不一样。不可能一边已经消完而另一边还剩下质数，因为，那样则一个质数一边还剩下
15、质数，因为，那样则一个质数或一些质数之积等于或一些质数之积等于1，这不可能。，这不可能。 定理定理5.2.6 ( (算术基本定理算术基本定理) ) 推论推论1 任意整数任意整数( 0， 1)恰好有一法写恰好有一法写成下面的形式：成下面的形式：p1pk (6)其中其中p1,pk都是质数。都是质数。推推论论2 任任意意整整数数( 0， 1)恰恰好好有有一一法法写写成下面的形式：成下面的形式：p1r1pnr n (7)其中其中p1, , ,pn是不同的质数，是不同的质数，r1,rn是正是正整数。整数。 定理定理5.2.6 ( (算术基本定理算术基本定理) ) 质数无穷多质数无穷多证明：假定质数只有有限的几个，设为证明：假定质数只有有限的几个，设为p1, , pn。试看试看N=p1p2pn+1因为因为p1, , ,pn都不能整除都不能整除N，故故N无质因数，无质因数，即即N为质数。而为质数。而N不同于不同于p1, , ,pn，与质数与质数只有只有p1, , ,pn矛盾。矛盾。 定理定理5.2.7（欧几里德）（欧几里德）
