资源描述:
《互质质因数分解(离散数学).ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、§5.2互质质因数分解§5.2.1整数互质定义5.2.1若a,b除±1外无其它公因数,则我们说a和b互质。据定义,a和b互质,必要而且只要a,b的最高公因数为1,且±1和任意整数互质。定理5.2.1a和b互质,当且仅当1可表示为a和b的倍数和形式,即存在整数s和t使1=sa+tb。证明:必要性;由a和b互质知,a和b的最高公因数为1,从而存在s,t,使sa+tb=1。充分性;只需证:若存在s,t,使sa+tb=1,则a和b的最高公因数d=(a,b)为1。假设d=(a,b)1,则d
2、a,d
3、b,从而d整除sa+tb=1的左端,因此d
4、1,矛盾。
5、定理5.2.2若a和b互质,而abc,则ac。证明:因为a,b互质,故有s,t使1=sa+tb,从而c=sac+tbc…………(1)今因abc,故a整除(1)右边每一项,因而ac。定理5.2.3若b和a1,a2,…,ak都互质,则b和a1a2…an互质。证明:由题设,对i=1,2,…,n,有si,ti使sib+tiai=1把所有这n个式子乘起来,右边得1,左边有2n项,其中有一项包含a1a2…an,而其余各项都包含b,所以,乘起来的式子如下:Sb+Ta1a2…an=1由定理5.2.1得,b和a1a2…an二者互质。定理5.2.4若m1,
6、m2,…,mk两两互质而都整除a,则m1m2…mk
7、a。证明:从简单到复杂对k进行归纳。当k=1时,结论显然。当k=2时,由于m1
8、a,所以存在整数q使得a=m1q。又m2
9、a,即m2
10、m1q,而(m1,m2)=1,故m2
11、q(定理5.2.2),于是存在p,使q=m2p。从而a=m1m2p,即m1m2
12、a。定理5.2.4假定对i(1≤i13、a………………(2)我们证明m1m2…mimi+1
14、a……………(3)由(2)知有q使a=m1m2…miq……………(4)今mi+1
15、a,且由定理5.2.3知mi+1和m1m2…mi互质,
16、故由定理5.2.2,mi+1
17、q。据此及(4)知(3)成立。归纳证毕。例5.2.1试证相继三个整数之积能被6整除。证明:三个相继整数必有一个为偶数,且必有一个为3的倍数,即2
18、n(n+1)(n+2),3
19、n(n+1)(n+2)。而(2,3)=1,故6
20、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(n3+3n-n)=3(3n+n(n2-1))=9n+3(n-1)n(n+1)而由上例5.
21、2.1知3
22、(n-1)n(n+1),故9
23、((n-1)3+n3+(n+1)3)。例5.2.3试证2p-1和2q-1互质的充要条件是p和q互质。证明:必要性;假若p和q不互质,(p,q)=a1,记p=ap1,q=aq1,则2p-1=2ap1-1,2q-1=2aq1-1。有公因数2a-11,矛盾。充分性;设(p,q)=1,(2p-1,2q-1)=d,往证d=1。不妨设pq,辗转相除得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=
24、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,则(a1a2…an,b1b2…bm)=1。特别当(a,b)=1时,(an,bm)=1,n,m为任意正整数。证明:由(ai,bj)=1,1≤j≤m,得(ai,b1b2…bm)=1,1≤i≤n,进而(a1a2…an,b1b2…bm)=1。取ai=a,bj=b,则(an,bm)=1。例5.2.5设a,b为大于1的自
25、然数,ba,且(a,b)=1,则logab是无理数。证明:反证法。若不然,logab=p/q为有理数。因ba,知p,q是正整数,且(p,q)=1。从而得ap/q=b,即ap=bq。因为(a,b)=1,由上例5.2.4知(ap,bq)=1,与ap=bq矛盾。设f(x)=anxn+an-1xn-1+…+a0是整系数多项式,若10
26、f(2),10
27、f(5),则10
28、f(10)。证明:注意到f(10)=an10n+an-110n-1+…+a0,所以10
29、f(10)当且仅当10
30、a0。因为10
31、f(2),所以2
32、f(2),于是2
33、a0,同样5
34、a0。
35、由(2,5)=1得10
36、a0。例5.2.6§5.2.2质数与合数算术基本定理一个正整数,如果不等于1而且除了自己和1没有其它正因数,则称其为一个质数