初等數(shù)論-2013.2.26周二2

1、初等數(shù)論及其應(yīng)用,1.1 整除定義,整數(shù)集,正整數(shù)指的是數(shù)1, 2,…，而整數(shù)指的是數(shù)0,±1,± 2,…。全體整數(shù)的集合記為Z，而全體正整數(shù)的集合記為Z+。整數(shù)集Z關(guān)于加、減、乘運(yùn)算是封閉的：任意a，b ∈Z，有a+b，a-b，ab∈Z。但是，整數(shù)集Z關(guān)于除法運(yùn)算不是封閉的：存在a，b ∈Z， a/b 不屬于Z。比如：6不能被4整除。因此，我們需要考慮整除，即研究何時(shí)a/b∈Z。,2,整除的定義,定義1.1

2、.1 設(shè)a，b∈Z，且b≠0。如果存在q∈Z，使得a=bq，則稱b整除a，記作b|a。此時(shí)，b叫做a的因數(shù)，a叫做b的倍數(shù)。任意整數(shù)a，有1|a，即1是任意整數(shù)的因數(shù)；當(dāng)a≠0時(shí)，有a|0和a|a，即0是任意整數(shù)的倍數(shù)，任意非零整數(shù)是自身的因數(shù)也是自身的倍數(shù)。 如果一個(gè)整數(shù)是2的倍數(shù)，我們稱它為偶數(shù)；否則稱它為奇數(shù)。偶數(shù)和奇數(shù)可分別表示如下的一般形式：2k，2k+1，k∈Z。,3,整除的基本性質(zhì),命題1.1.1 設(shè)a

3、，b，c∈Z。如果c|b，b|a，那么c|a。如果b|a，c≠0，那么cb|ca。如果c|a，c|b，那么對任意m，n∈Z，有c|ma+nb。如果a|b，b|a，那么a=b或a=-b。證明：上述4點(diǎn)的證明類似，這里僅證明第4點(diǎn)。設(shè)b=aq，a=bp，其中p，q ∈Z。于是 b=aq=(bp)q=b(pq) 若b=0，則a=bp=0，即結(jié)論成立； 若b≠0，則由上

4、式可得pq=1。由于 p，q ∈Z，則p=q=1，或p=q=-1，即結(jié)論成立。,4,帶余除法,定理1.1.1 設(shè)a，b∈Z，且b≠0，則存在唯一的q，r ∈Z，使得 a=bq+r，0 ≤r0時(shí)，有a=bq+r；當(dāng)b<0時(shí)，有a=b(-q)+r。這就證明了q，r的存在性。,5,帶余除法,證明：唯一性證明。假設(shè)存在另一組q*，r*∈Z，滿足：a=bq*+r*，0 ≤r*&

5、lt;|b|，則 -|b|<r-r*=b(q*-q)<|b|。 因此b(q*-q)=0，從而r-r*=0，即q*=q， r*=r，所以唯一性成立。特別要注意的是，帶余除法是初等數(shù)論的證明中最基本、最常用的工具。例如，證明下面整數(shù)不同進(jìn)制表示相關(guān)的定理，就需要用到帶余除法。,6,整數(shù)的表示,定理1.1.2 設(shè)b≥2是給定的正整數(shù)，那么任意正整數(shù)n可以唯一表示為

6、 n=rkbk+rk-1bk-1+…+r1b+r0， 其中整數(shù)k ≥0，整數(shù)ri(i=0,1,..,k)滿足0≤ri<b，rk≠0。證明：對給定的正整數(shù)n，必存在唯一的整數(shù)k ≥0，使得bk ≤ n<bk+1。由帶余除法，存在唯一的的q0，r0 ∈Z，使得n=bq0 +r0 ，0 ≤r0<b。下面利用數(shù)學(xué)歸納法進(jìn)行證明。這里需要注意，數(shù)學(xué)歸納法包含兩步：證明結(jié)論在k=0時(shí)成立；

7、假設(shè)結(jié)論在k=m ≥0時(shí)成立，證明結(jié)論在k=m+1時(shí)也成立。,7,整數(shù)的表示,證明：（1）當(dāng)k=0時(shí)，由于1≤ n<b，則有q0=0，0<r0 =n<b，結(jié)論顯然成立。 （2）假設(shè)結(jié)論在k=m ≥0時(shí)成立，那么當(dāng)k=m +1時(shí)，有bm+1 ≤ n<bm+2，而n可以唯一表示為n=bq0 +r0 （0 ≤r0<b），這樣bm+1 ≤ bq0 +r0 <bm+2。由于0 ≤r0<b，則bm+1-b

8、 < bq0 <bm+2，即bm ≤ q0 <bm+1。由歸納假設(shè)知，q0 可唯一表示為 q0 =smbm+sm-1bm-1+…+s1b+s0， 其中整數(shù)si(i=0,1,..,m)滿足0 ≤si<b，sm≠0。因此有 n=bq0 +r0 =smbm+1+sm-1bm+…+s1b2+s0b+r0， 這種表示是滿足定理要求的唯一表示，否則與q0唯一

9、表示性矛盾。因此結(jié)論在k=m +1時(shí)成立。,8,證明方法的討論,上述定理的證明采用了數(shù)學(xué)歸納法，它的一般證明步驟為：(1) 證明結(jié)論在k=0時(shí)成立； (2) 假設(shè)結(jié)論在k=m ≥0時(shí)成立，證明結(jié)論在k=m+1時(shí)也成立。此外，上述定理的證明還可以采用如下方法：存在性證明采用構(gòu)造法，而唯一性證明采用反證法?？梢援?dāng)作課后練習(xí)，其中存在性證明的提示： 首先對n應(yīng)用帶余除法n=bq0 +r0（0 ≤r0<b），然后不斷地對上次得到的商應(yīng)

10、用帶余除法，直到商為0。,9,不同進(jìn)制的轉(zhuǎn)換,在上述定理給出的表示式中，如果b取不同值，則代表不同進(jìn)制的表示，常用的有2進(jìn)制（b=2）、10進(jìn)制（b=10）、16進(jìn)制（b=16）等。為了區(qū)分不同進(jìn)制，記(rkrk-1…r1r0)b=rkbk+rk-1bk-1+… +r1b+r0。由上述定理可以很容易得到任意正整數(shù)n的b進(jìn)制表示(rkrk-1…r1r0)b，計(jì)算方法如下： n=q0b+r0 =(rkbk

11、-1+rk-1bk-2+…+ r1)b+r0 q0= q1b+r1 =(rkbk-2+rk-1bk-3+…+r2)b+ r1 …… qk-2= qk-1b+rk-1=rkb + rk-1

12、 qk-1= qkb+rk =0*b+ rk,10,二進(jìn)制轉(zhuǎn)換的例子,例如，為了求出66的二進(jìn)制表示，我們可以連續(xù)使用帶余除法： 66=2*33+0 (低位) 33=2*16+1 16=2 * 8+0 8=2 * 4+0

13、 4=2 * 2+0 2=2 * 1+0 1=2 * 0+1 (高位) 按從低位到高位順序，依次取出上述除法中的余數(shù)，得到(66)10=(1000010)2。,11,余數(shù)的定義,定義1.1.2 帶余除法中的q為用b除a得出的不完全商，稱r為用b除a得到的最小非負(fù)余數(shù)，也簡稱為

14、余數(shù)，常記為b 或 a mod b。 例如，當(dāng)a=17，b=5時(shí)，17=5*3+2，這時(shí)q=3，r=2，即5 =2；當(dāng)a=-17，b=5時(shí)，-17 = 5* (-4)+3，這時(shí)q=-4，r=3，即5 =3。在不致引起混淆時(shí)， b 中的b常略去不寫。為方便起見，以后除非特別說明，我們總是假定除數(shù)b以及因數(shù)都大于零。,12,余數(shù)的基本性質(zhì),定理1.1.3 設(shè)a1，a2，b∈Z，且b>0，則= +>= ->

15、= >證明：上述3點(diǎn)的證明類似，這里僅證明第1點(diǎn)。設(shè)a1=bq1+，a2=bq2+，+= bq3++>。于是 a1+a2=b(q1+q2)+ + =b(q1+q2+q3) ++>， 因此，= +>。,13,課堂練習(xí),命題：設(shè)a，b∈Z。如果2a+3b， 9a+5b 中有一個(gè)能被17整除，那么另一個(gè)也能被17整

16、除。證明：注意到4(2a+3b)+(9a+5b)=17(a+b) 。 如果17|2a+3b，則有2a+3b=17q，q∈Z。于是9a+5b = 17(a+b-4q)，即17| 9a+5b。 如果17| 9a+5b ，則有9a+5b =17p，p∈Z。于是4(2a+3b)= 17 (a+b-p) ，即4| 17 (a+b-p) 。雖然a+b-p可以表示為4k，4k+1，4k+2，或4k+3 (k∈Z ) ，但是只有當(dāng)a+b

17、-p= 4k時(shí)才有4| 17 (a+b-p) 成立。因此， 4(2a+3b)= 17 (a+b-p) =17*4k，等價(jià)為2a+3b= 17k (k∈Z ) ，即17|2a+3b。,14,課堂練習(xí),命題：對任意a∈Z，6|a3-a。證明：注意到a3-a=a(a2-1)=a(a-1)(a+1)。對任意a∈Z， a可以表示如下6種形式之一： a=6k，6k+1，6k+2， 6k+3， 6k+4， 6k+5，k∈Z 。 容易驗(yàn)證當(dāng)a

18、=6k ，6k+1，6k+5時(shí)， 6|a3-a。當(dāng)a= 6k+2時(shí)，a3-a= (6k+2)(6k+1)(6k+3)，即6|a3-a。當(dāng)a= 6k+3時(shí)，a3-a=(6k+3) (6k+2) (6k+4) ，即6|a3-a。當(dāng)a= 6k+4時(shí)，a3-a=(6k+4) (6k+5) (6k+3) ，即6|a3-a。綜上所述，命題結(jié)論成立。,15,課堂練習(xí),計(jì)算：把89156轉(zhuǎn)換為八進(jìn)制表示，把(706113)8轉(zhuǎn)換為十進(jìn)制表示。解：（

19、1） 89156=11144*8+4， 11144= 1393*8+0， 1393= 174*8+1， 174= 21*8+6， 21= 2*8+5，

20、 2= 0*8+2， 即89156=(256104) 8 （2） (706113)8=7*85+0+6*83+1*82+1*8+3=232523,16,課堂練習(xí),計(jì)算：將 (256104) 8與(706113)8都轉(zhuǎn)換成二進(jìn)制。解：易知對八機(jī)

21、制0-7有如下二進(jìn)制轉(zhuǎn)換： 0->000 1->001 2->010 3->011 4->100 5->101 6->110 7->111 因此， (256104) 8= (10101110001000100) 2 (70611