1、第五章 數(shù)論基礎(chǔ),第五章 數(shù)論基礎(chǔ),5.1 整除性 輾轉(zhuǎn)相除 5.2 互質(zhì) 質(zhì)因數(shù)分解 5.3 合同 一次同余式 5.4 秦九韶定理 Euler函數(shù) 5.5 一元高次同余式 二次剩余,5.1.1 整除及其性質(zhì),定義5.1.1 設(shè)a和b是任意整數(shù)，若存在整數(shù)c，使得a=bc，則說a是b的倍數(shù)，b是a的因數(shù)?；蛘哒fa被b整除，而b整除a。記為b|a。 顯然，任意數(shù)整除0，特別0|0；1（-1）整除任意整數(shù)。,定理5.1.1,對任意整數(shù)a和b，b0，唯一存在一對整數(shù)q和r，使得0r|b|， a=qb+r。q稱為(不完全)商數(shù)，r稱為a被b除的余數(shù)。 證明：（1）當b0時，存在性成立。 看函數(shù) y=b

2、x, xZ。因為b0，所以y是x的單調(diào)遞增函數(shù)，且當x+時，y+；當x-時，y-,從而存在q，使得x=q時，ya；x=q+1時ya。即 bqa，b(q+1) a。令r=a-bq，則r0且rb。于是 a=qb+r, 0rb。,定理5.1.1,（2）當b=-b 0時，存在性成立。 由(1)知，存在q，r，使得a=qb+r，0rb。取q=-q，r=r，則得a=-qb+r =qb+r，0r-b。 綜合(1)，(2)對任意b (b0)，都有q，r，使得a=qb+r 0r |b| (),定理5.1.1,（3）q和r的唯一性。 設(shè)另有一對q和r滿足 a=qb+r 0 r |b| () 則() - ()得 r

3、-r=(q-q)b，從而有 |r-r|=|q-q|b|。注意到 |r-r|b| ，而|q-q|0為整數(shù)，所以必有|q-q|=0，從而 |r-r|=0。即 q=q，r=r。所以，唯一性成立。,由整除的定義，易得如下推論： b|a，(b0) 當且僅當a被b除的余數(shù)為0。,整除的基本性質(zhì),性質(zhì)1 若a|b，b|c，則a|c 證明：因為a|b，b|c，故有整數(shù)d，e使b=ad，c=be，因之，c=a(de)。但de是整數(shù)，所以a|c。 性質(zhì)2 若a|b，則a|bc 證明：由定義知，b|bc。今a|b，故由性質(zhì)1，a|bc,整除的基本性質(zhì),性質(zhì)3 若a|b，a|c，則a|bc。 證明：因為a|b，a|c

4、，故有整數(shù)d，e使b=ad，c=ae。因之，bc=a(de)。但de為整數(shù)，所以a|bc。 性質(zhì)4 若a整除b1,bn, 則a|1b1+nbn，其中i為任意整數(shù)。 證明：因為a|bi，故由性質(zhì)2，a|ibi。因為a|1b1，a|2b2，故由性質(zhì)3，a|1b1+2b2。由此及a|3b3，又有a|1b1+2b2+3b3。如此類推歸納證明了a|1b1+nbn。,整除的基本性質(zhì),性質(zhì)5 若在一等式中，除某項外，其余各項都是a的倍數(shù)，則此項也是a的倍數(shù)。 證明：這是性質(zhì)4的直接推論。 例如，在等式b-c=-d+e+f中，設(shè)b，c，d，f都是a的倍數(shù)，求證e也是a的倍數(shù)。解出e得e=b-c+d-f。由性質(zhì)

5、4，此式右邊是a的倍數(shù)，故e是a的倍數(shù)。,整除的基本性質(zhì),性質(zhì)6 若a|b，b|a，則b=a。 證明：由條件知，或者a=b=0，或者a，b都不為0。若a=b=0，則b=a自然是對的。若a，b都不是0。因為a|b，b|a，故有整數(shù)d，e使b=ad，a=be，從而a=ade。消去a得1=de。今d，e是整數(shù)而相乘得1，故此二數(shù)必然都是1，因而b=a。,整除的基本性質(zhì),定義5.1.2 若d是a的因數(shù)也是b的因數(shù)，則稱d為a，b的公因數(shù)。若d是a，b的公因數(shù)，而a，b的任意公因數(shù)整除d，則稱d為a，b的最高公因數(shù)。a，b的最高公因數(shù)通常記為d=(a,b)。,整除的基本性質(zhì),性質(zhì)7 設(shè)a=qb+c，則a

6、，b的公因數(shù)與b，c的公因數(shù)是完全相同的。 證明：若d是b，c的公因數(shù)，則由上式及性質(zhì)5，d也是a的因數(shù)，因而是a,b的公因數(shù)。反之，若d是a，b的公因數(shù)，則由上式及性質(zhì)5，d也是c的因數(shù)，因而是b，c的公因數(shù)。,最高公因數(shù)的定義只是說，如果有那樣的d，則d叫做a，b的最高公因數(shù)。對于任意的a，b是否有那樣的d呢？現(xiàn)在還不知道，等下面再研究。不過，有一點是容易說明的：如果a，b有最高公因數(shù)，則最高公因數(shù)除符號外唯一確定。事實上，若d和d都是a，b的最高公因數(shù)，則d|d，d|d，因而由性質(zhì)6知，d=d。,現(xiàn)在我們來看，是否任意a，b有最高公因數(shù)？ 若b|a，則由定義易見，b就是a，b的最高公因數(shù)

7、。同樣，若a|b，a 就是a，b的最高公因數(shù)。,5.1.2 輾轉(zhuǎn)相除,a=q1b+r1 b=q2r1+r2 rk-2=qkrk-1+rk rn-2=qnrn-1+rn rn-1=qn+1rn。,5.1.2 輾轉(zhuǎn)相除,任意二整數(shù)a，b有最高公因數(shù)。 上面求最高公因數(shù)的方法叫做輾轉(zhuǎn)相除法。對a，b使用輾轉(zhuǎn)相除得到的最后一個非0余項(rn)即為a，b的最高公因數(shù)。,定理5.1.2,任意二整數(shù)a，b的最高公因數(shù)d可以表示為a，b的倍數(shù)和，即表為下面的形式：d=sa+tb 其中 s，t都是整數(shù)。 證明：(方法一） 由輾轉(zhuǎn)相除法知d=rn。只需證明對每一個i(i=1,n)，ri都可以表示成 ri=sa+t

8、b的形式。,定理5.1.3,當i=1時，r1=a-q1b。 當i=2時，r2=b-r1q2=b-(a-bq1)q2=-q2a+(1+q1q2)b。假設(shè) rm-1，rm-2，3mn，分別有s，t及s”，t”使得rm-2=s”a+t”b，rm-1=sa+tb，下面說明rm也可以表示成這種形式。 rm= -rm-1qm+rm-2 =-(sa+tb)qm+s”a+t”b =(s”-sqm)a+(t”-tqm)b 因此對一切i (i=1, , n)成立。,定理5.1.3,證明：(方法二） 若a，b中有一個整除另一個，不妨假設(shè)b|a，則d=b=0a+1b，得證。,定理5.1.3,定理5.1.3,則由(1)

9、的第一式知 :,由(1)的第二式知 :,定理5.1.3,依此類推 :,令,定理5.1.3,又,則,定理5.1.3,故,又,定理5.1.3,故,定理5.1.3,因此,所以，我們有,定理5.1.3,取k=n，則因rn即最高公因數(shù)d而得,即為所求的形式 這表明，任給兩個數(shù)，我們都可將它們的最高公因表為它們的倍數(shù)和的形式，這里需求出n，Sn，Tn。,定理5.1.3,為能簡便地計算它們，讓我們看下面的等式：,比較最左最右兩矩陣的第二列知:Uk=Sk-1，Vk=Tk-1。 因而，Uk-1=Sk-2，Vk-1=Tk-2 (1),再比較這兩個矩陣的第一列：Sk=qkSk-1+Uk-1 Tk=qkTk-1+Vk-1 (2) 由(1)式和(2)式得：Sk=qkSk-1+Sk-2 Tk=qkTk-1+Tk-2 (3) (1)式在k2時成立，(2)式在k2時成立，所以(3)式在k2時成立。,定理5.1.3,現(xiàn)令S0=U1， T0=V1 則(1)式在k=2時也成立，即(3)式在k=2時也成立。 由,定理5.1.3,得S0=U1=0，S1=1，T0= V1 =1，T1=q1 根據(jù)這個初值及(3)式，便可求出任意的Sk，Tk。,例5.1.2