(1.1)-第0章預(yù)備知識近世代數(shù)

近世代數(shù)(ContemporaryAbstractAlgebra)2主要參考書JosephA.Gallian,ContemporaryAbstractAlgebra,8thEdition,CengageLearning,2010.3整數(shù)性質(zhì)模運(yùn)算歸納法復(fù)數(shù)第0章預(yù)備知識等價關(guān)系映射第0章預(yù)備知識(Preliminaries)4整數(shù)性質(zhì)模運(yùn)算歸納法復(fù)數(shù)第0章預(yù)備知識等價關(guān)系映射第0章預(yù)備知識(Preliminaries)5良序原理(WellOrderingPrinciple)一、整數(shù)性質(zhì)每一個非空正整數(shù)集合都包含一個最小整數(shù)整數(shù)性質(zhì)注意：在具體問題中,良序原理有許多變形.比如，設(shè)a為整數(shù),S為任一非空整數(shù)集合.若S中元素都大于等于a,

則S包含最小元素,若S中元素都小于等于a,

則S包含最大元素.6本課程記號約定

Z：整數(shù)集合；C：復(fù)數(shù)集合；R:實數(shù)集合；Q:有理數(shù)集合令F為上面四個數(shù)集之一，F(xiàn)*=F-{0},

F+={x∈F|x>0}7設(shè)

s,t,u∈Z，滿足

s=tu倍數(shù)(multiple):稱

s

為t

的倍數(shù).因子(divisor):若

t≠0,稱

t

為

s的一個因子,記為t|s.

反之,記為

素數(shù)(prime):一個大于1的整數(shù),如果它大于0的因子只有1和它自

己,則稱它為素數(shù).1、因子,素數(shù),倍數(shù)整數(shù)性質(zhì)證：定理0.1

帶余除法(DivisionAlgorithm)設(shè)a∈Z,b∈Z+,則存在唯一的q,r∈Z,使得a=bq+r,0≤r<b.8唯一性：假設(shè)存在兩對整數(shù)q,r;x,y滿足a=bq+r=bx+y,0

≤r,y<b.

不妨設(shè)r≥y.則上式可變形為：r-y=b(x-q).則b整除r-y但0

≤r-y<b.從而必有r-y=0,即r=y.因b>0,故x-q=0,即x=q.

整數(shù)性質(zhì)作為良序原理的第一個重要應(yīng)用，先來證明帶余除法.存在性：令S={a-bk|k∈Z,a-bk≥0}.顯然S非空.根據(jù)良序原理，可取r=a-bq為S中最小元素.假設(shè)r≥b.則r-b<r,且0≤r-b=a-b(q+1)∈S.與r的極小性矛盾.因此，0≤r<b.

定義：帶余除法中,q

為

b

除

a的商,

r

為余數(shù).本次課到此結(jié)束謝謝！10整數(shù)性質(zhì)模運(yùn)算歸納法復(fù)數(shù)第0章預(yù)備知識等價關(guān)系映射第0章預(yù)備知識(Preliminaries)112、最大公因子，互素最大公因子(GreatestCommonDivisor):非零整數(shù)a,b的最大的公因子稱為是a,b的最大公因子,記為gcd(a,b).互素(RelativePrime):如果

gcd(a,b)=1,那么稱整數(shù)a,b互素.整數(shù)性質(zhì)兩個整數(shù)的GCD如下性質(zhì)在近似代數(shù)扮演著特別重要的角色,其證明應(yīng)用到了帶余除法和良序原理.

定理0.2(GCD是一個線性組合)

任給兩個非零整數(shù)a,

b,則

存在整數(shù)s,t

使得

gcd(a,b)=as+bt.gcd(a,b)是具有as+bt形式的最小正整數(shù).

12證：令S={am+bn|m,n∈Z,am+bn>0}.則S非空.根據(jù)良序原理,S中有最小元素,設(shè)為d=as+bt>0.下證d=gcd(a,b).易見gcd(a,b)|d.

故只需證明d為a,b的公因子.由帶余除法，可得a=dq+r(0≤r<d).從而,r=a-dq=a(1-sq)+btq.由d的極小性，可得r=0,即d|a.類似地，可證d|b.整數(shù)性質(zhì)13推論:如果整數(shù)a,b互素,那么存在整數(shù)

s,t,

使得

as+bt=1.值得指出的是：推論中條件既充分也必要.充分性的證明留作練習(xí)Ex.11,請讀者自行完成.整數(shù)性質(zhì)上述定理的特殊情形,即當(dāng)a,b互素時,在近世代數(shù)中是相當(dāng)重要的,將其單獨寫為一個推論.14歐幾里德引理(Euclid’sLemma)設(shè)

p是素數(shù),且p|ab,

則

p|a或者

p|b.證：若p不整除a，那么gcd(p,a)=1.由上面推論,存在整數(shù)s,t使得1=as+pt.等號兩邊同乘以b，有b=abs+pbt.

從而，p|b.整數(shù)性質(zhì)下面引理給出素數(shù)的一個重要性質(zhì).在今后的學(xué)習(xí)中,將會經(jīng)常用到.注：當(dāng)p不是素數(shù)時,歐幾里德引理不一定成立.比如6|(4?3)但6既不整除4,也不整除3.15定理0.3算術(shù)基本定理(FundamentalTheoremofArithmetic)任意大于1的整數(shù)可分解為素數(shù)乘積,若不考慮因子順序分解惟一.定理0.3的存在性部分的證明將在講歸納法時給出證明(例子11),而唯一性部分的證明則由歐幾里德引理可證

(留作練習(xí)Ex.31，讀者自行完成).整數(shù)性質(zhì)下面定理表明素數(shù)是構(gòu)成整數(shù)的基本元素.163、最小公倍數(shù)(LeastCommonMultiple)非零整數(shù)a,b的所有公倍數(shù)中的最小正整數(shù)稱為a,b的最小公倍數(shù),

記為

lcm(a,b).簡單觀察：

a,b的任一公倍數(shù)均是lcm(a,b)的倍數(shù).這一結(jié)論留作練習(xí)Ex.10,讀者自行完成證明.整數(shù)性質(zhì)在整數(shù)性質(zhì)這一部分的最后,我們介紹如下概念.本次課到此結(jié)束謝謝！18整數(shù)性質(zhì)模運(yùn)算歸納法復(fù)數(shù)第0章預(yù)備知識(Preliminaries)第0章預(yù)備知識等價關(guān)系映射19二、模運(yùn)算現(xiàn)在是三月份，25個月后是幾月份

25=2×12+1,答案:四月模運(yùn)算

模運(yùn)算是帶余除法的一個重要應(yīng)用，也是我們常用的計數(shù)方法一個抽象，比如：20模運(yùn)算這些運(yùn)算法則的證明留作練習(xí)Ex7和Ex9,讀者自行完成.模運(yùn)算例5：試證任意三個連續(xù)整數(shù)的立方和被9整除.證明：設(shè)n為一整數(shù).要證n3+(n+1)3+(n+2)

3mod9=0mod9.由第二條模運(yùn)算法則：只需驗證r3+(r+1)3+(r+2)3mod9=0mod9,其中r為9除n的余數(shù).給定正整數(shù)n和整數(shù)a,則由帶余除法,知存在唯一的整數(shù)q,r

使得,a=qn+r且0≤r<n.定義：amodn=r.模運(yùn)算具有如下運(yùn)算法則amodn=bmodn

當(dāng)且僅當(dāng)

n|(a-b).令a

modn=c,bmodn=d,則

(a+b)modn=(c+d)modn

且abmodn=cdmodn.21三、復(fù)數(shù)1.復(fù)數(shù)的標(biāo)準(zhǔn)形式：z=a+bi,

其中i

2=-1,a和b

為兩個實數(shù)，分別稱為復(fù)數(shù)z的實部(realaxis)和虛部(imaginaryaxis).2.復(fù)數(shù)的兩極形式：其中

為z到原點的距離,也記為|a+bi|.

ReIm0rba復(fù)數(shù)22定理0.4復(fù)數(shù)運(yùn)算性質(zhì)

(1)

加法：(2)

乘法：(3)

除法：(4)逆元：對任意非零復(fù)數(shù)

a+bi,總存在復(fù)數(shù)

c+di使得:

(a+bi)(c+di)=1復(fù)數(shù)23(5)復(fù)共軛：(6)方冪：(7)根：證明:(1)-(5)可根據(jù)定義直接驗證.

(6)將在例8中給出證明

,(7)留作練習(xí)Ex.25,讀者自行完成.復(fù)數(shù)本次課到此結(jié)束謝謝！25整數(shù)性質(zhì)模運(yùn)算歸納法復(fù)數(shù)第0章預(yù)備知識(Preliminaries)第0章預(yù)備知識等價關(guān)系映射26四、歸納法設(shè)P

為一個與正整數(shù)有關(guān)的命題,要證P對任意整數(shù)都成立,只需做以下兩步：驗證P

對1

成立；

假設(shè)

P對n

成立，證明P對n+1也成立.定理0.5(第一數(shù)學(xué)歸納法)設(shè)S為一個包含

a的整數(shù)集合，且具有如下性質(zhì)：只要n≥a且n∈S,則必有n+1∈S.

那么對任意整數(shù)x≥a,都有

x∈S.

歸納法由數(shù)學(xué)歸納有兩種形式的證明，均和良序原理等價.先來看第一種.27例7:給定一把直尺，一個圓規(guī)及一個單位長度.證明對任意正整數(shù)n,

可以做出長度為的線段.關(guān)鍵點：如何尺規(guī)做直角?畫一線段，分別以兩端點為圓心,以大于線段一半為半徑畫圓，連接兩圓之交點.歸納法注意：若兩直角邊分別為1和，則斜邊為28例8:(DeMOIVRE’s定理)其中,n為任意正整數(shù),為任意實數(shù).證:(1)顯然n=1

時命題成立.(2)假設(shè)對某一個正整數(shù)n≥1

成立，即命題對整數(shù)n+1成立.得證.歸納法29設(shè)P是與整數(shù)有關(guān)的命題，若能：驗證P對整數(shù)a成立；在P對任意a≤x<n的x成立的假設(shè)下，證明P對n

也成立.

那么P

對任何滿足

m≥a

的整數(shù)m成立.定理0.6(第二數(shù)學(xué)歸納法)設(shè)S為一個包含a的整數(shù)集合,具有如下性質(zhì)：如果對任意的x滿足a≤x<n,都有x∈S,那么n∈S.

那么對任意整數(shù)x≥a,都有

x∈S.歸納法30例9:(算術(shù)基本定理的存在性部分)

任意大于1的整數(shù)n都可分解成素數(shù)乘積.證:

顯然,n=2可分解為素數(shù)乘積.設(shè)對任意整數(shù)2≤k<n,k

可分解為素數(shù)乘積.若n

是素數(shù),結(jié)論自然成立.若n不是素數(shù),則有n=ab,2≤a,b<n.由歸納假設(shè),a,b可分解為素數(shù)乘積,故n可分解為素數(shù)乘積.歸納法31例10:賭博公司只有5美元和8美元賭牌，問不能為賭資的最大數(shù)目是多少？證:5,8,10,13,15,16,18,20,21,23-26,28,29,30,…猜測為27.需證若n≥28,則n=5s+8t,其中s,t>0.n=28

時成立：假設(shè)猜測在n≥28時成立,即n=5s+8t,其中s,t>0.則必有或者s>2或者t>2.

若s>2,則n+1=5s+8t-15+16=5(s-3)+8(t+2).若t>2,則n+1=5s+8t+25-24=5(s+5)+8(t-3).故猜測對n+1也成立.歸納法最后,我們來看一道刊載于1988年美國《Discover》雜志1月期的一道題.本次課到此結(jié)束謝謝！33整數(shù)性質(zhì)模運(yùn)算歸納法復(fù)數(shù)第0章預(yù)備知識(Preliminaries)第0章預(yù)備知識等價關(guān)系映射34五、等價關(guān)系數(shù)學(xué)中，某個環(huán)境下兩個不同的對象，在另一環(huán)境中卻會被看作是等價的。比如：在通常加法意義下2+1與4+4顯然不同，但在mod5加法運(yùn)算下它們卻是相等的。等價關(guān)系為此，我們需要將“相等”適當(dāng)推廣，即“等價”。35關(guān)系:設(shè)A是一個集合,

A×A={(a,b)|a,b∈A}

的一個子集R

稱為

A的一個關(guān)系.

給定集合A的任意關(guān)系R,對A中任意元素a和

b

,如果(a,b)

∈

R，則稱a和

b符合關(guān)系R:記為

aRb.

否則稱a和

b不符合關(guān)系R.等價關(guān)系1、關(guān)系(Relation)362、等價關(guān)系(EquivalenceRelation)集合

A

上的一個關(guān)系R

稱為

等價關(guān)系，若(1)自反性：(2)對稱性：(3)傳遞性：等價關(guān)系注：(1)等價為相等的推廣，常用~,≈或≡表示等價關(guān)系R.

(2)如果~是集合A上的一個等價關(guān)系,則稱

[a]={x∈A|x~a}為A的含a的等價類.37例11:設(shè)S為平面上所有三角形組成的集合.定義：

R={(a,b)|a,b相似,a,b∈S}.則R為集合S上的一個等價關(guān)系.此時,通常用a

~

b表示aRb.等價關(guān)系例12:給定正整數(shù)n.定義:R={(a,b)|amodn=bmodn,a,b∈Z}.則根據(jù)模運(yùn)算的法則不難驗證R為集合Z上的一個等價關(guān)系.此時,通常用a≡b表示aRb.例13:在上題中,令n=7,則可知[1]={…,-20,-13,-6,1,8,15,…}和[4]={…,-17,-10,-3,4,11,18,…}為兩個等價類.通常將每個這

樣的等價類稱為模7的剩余類.383、分劃(Partition)分劃:集合S的某些子集(叫做類)構(gòu)成的集合稱為S的一個分劃,

如果S中每個元素屬于且只屬于一個子集(即所有子集的并為S,且任何兩個不同子集的交為空).等價關(guān)系39例14:集合{0},{1,2,3,…},{…,-3,-2,-1}為整數(shù)集的一個分劃.例15:非負(fù)整數(shù)集和非正整數(shù)集不是Z

的分劃.等價關(guān)系由該定理可知：整數(shù)集合Z模

n剩余類{[0],[1],[2],……,[n-1]}構(gòu)成Z

的一個分劃.定理0.7(等價類與分劃)

集合A上一個等價關(guān)系決定A的一個分劃.

集合A上任意一個分劃決定A的一個等價關(guān)系,且該分劃與該等價關(guān)系決定的分劃相同.40后半部分的證明：設(shè)是A

上的一個分劃.定義A的關(guān)系

在同一Si中.容易驗證是等價關(guān)系.設(shè)則有.(有關(guān)驗證,留作練習(xí)Ex.61)

等價關(guān)系證明:設(shè)~是集合A

上的一個等價關(guān)系，任給A中兩個元素a,b,則

或

[a]=[b].

等價類集合

是A

的一個分劃.定理0.7(等價類與分劃)

集合A上一個等價關(guān)系決定A的一個分劃.

集合A上任意一個分劃決定A的一個等價關(guān)系,且該分劃與該等價關(guān)系決定的分劃相同.本次課到此結(jié)束謝謝！42整數(shù)性質(zhì)模運(yùn)算歸納法復(fù)數(shù)第0章預(yù)備知識(Preliminaries)第0章預(yù)備知識等價關(guān)系映射43六、映射1、

映射(Function(Mapping))集合A到集合B的一個映射?是一個對應(yīng)法則,使得對A中任一元素a,在B中有唯一元素b與之對應(yīng).稱A

為?的定義域(d