《互质质因数分解》PPT课件

《《互质质因数分解》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.2

5、.2若a和b互质，而abc，则ac。证明：因为a，b互质，故有s，t使1=sa+tb，从而c=sac+tbc…………(1)今因abc，故a整除(1)右边每一项，因而ac。定理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,m2,…,mk两两互

6、质而都整除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≤i

13、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互质，故由定理5.2.2，mi+1

16、

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.2.1知3

21、(n-1)n(n+1)，故9

22、

23、((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，辗转相除得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

24、+(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的自然数，ba，且(a,b)=1，则logab是无理数。证明：

25、反证法。若不然，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矛盾。设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。由（2，5）=1得10

35、a0。例5.2.6§5.2.2质数与合数算术

36、基本定理一个正整数，如果不等于1而且除了自己和1没有其它正因数，则称其为一个质数