5-2互质 质因数分解_ou.ppt

§5.2 互质 质因数分解 §5.2.1 整数互质 定义5.2.1 若a，b除±1外无其它公因数，则称a和b互质。 结论： 1、a和b互质，必要而且只要a、b的最高公因数为1(通常只考虑+1)。 2、±1和任意整数(包括0)互质。 定理5.2.1 a和b互质，当且仅当1可表示为a和b的倍数和形式，即存在整数s和t使1=sa+tb。 证明：必要性；由a和b互质知，a和b的最高公因数为1，从而根据定理5.1.3，存在s，t，使sa+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) 今因a?bc，a|ac，故a整除(1)右边每一项，因而a?c。 定理5.2.3 若b和a1,a2,…,an都互质，则b和a1a2…an互质。 证明：由题设，对i=1,2,…,n，有si，ti使 sib+tiai=1 把所有这n个式子乘起来，右边得1，左边有2n项，其中有一项包含a1a2…an，而其余各项都包含b，所以，乘起来的式子如下： S b+T a1a2…an=1 由定理5.2.1得，b和a1a2…an二者互质。 定理5.2.4 若m1,m2,…,mk两两互质而都整除a，则m1m2…mk|a。 证明：对k用数学归纳法。 当k=1时，结论显然。 当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(1≤ik) 有 m1m2…mi|a……………… (2) 我们证明 m1m2…mimi+1|a……………(3) 由(2)知有q使 a=m1m2…miq…………… (4) 今mi+1|a，且由定理5.2.3知mi+1和m1m2…mi互质，故由定理5.2.2，mi+1|q。据此及(4)可以得到(3)成立。归纳证毕。 例5.2.1 试证相继三个整数之积能被6整除。 证明：三个相继整数必有一个为偶数，且必有一个为3的倍数，即2|n(n+1)(n+2)，3| n(n+1)(n+2)。而(2，3)=1，故根据定理5.2.4有，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(n3+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，辗转相除得 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)= … = 。 例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。 更正 P161, 定理5.2.1中“充分性”证明的第二个sa+td=1(“从而d整除sa+td=1的左端”),应该是sa+tb=1. P161, 定理5.2.