現(xiàn)代編碼理論：第二章 代數(shù)基礎

第二章代數(shù)基礎一、整數(shù)的一些基本性質基本概念素數(shù)合數(shù)因數(shù)（約數(shù)）素因數(shù)公約數(shù)最大公約數(shù)（greatestcommondivisor)

a,b的最大公約數(shù)記為GCD(a,b)或(a,b)最小公倍數(shù)(leastcommonmultiple）

a,b的最小公倍數(shù)記為LCM(a,b)或[a,b]整數(shù)的初等運算及性質加、減、乘、除定理1。任何正整數(shù)a均可唯一地分解為素因數(shù)的積。

a=p1r1p2r2……pnrn(p1、p2、

……pn素數(shù)，

r1、r2、……、rn為正整數(shù)）《水滸》天罡星：36＝22×32地煞星：72＝23×32好漢：108＝22×32+23×32=22×32（1＋2）＝22×333.歐幾里德除法（求最大公約數(shù)）定理2（歐幾里德除法）：設b是正整數(shù)，則任意大于b的正整數(shù)a可唯一地表示為：

a=qb+r0r<b

解釋：兩個正整數(shù)相除，商和余數(shù)是唯一的。定理3：a、b為正整數(shù)，且a>b,設a=bq+r,則(a,b)=(b,r)。

解釋：利用歐幾里德除法求最大公約數(shù)。

例2.1.

求(150,42) 150=342+24 42=24+18 24=18+6 18=36 (150,42)=(42,24)=(24,18)=(18,6)=6

求（a,b,c)=((a,b),c)4.歐幾里德算法定理4：給定任意a、b，(a,b)=Aa+Bb,(A、B為整數(shù)）。

解釋：兩個正整數(shù)的最大公約數(shù)可表示為它們的線性組合。如何求？

(150,42) 150=342+24 42=24+18 24=18+6 18=36 (150,42)=(42,24)=(24,18)=(18,6)=6（150，42）=24-18=24-（42-24）=224-42 =2(150-342)-42 =2(150-342)-42 =2150-7425.最小公倍數(shù)(1)法1（利用定理1）：把a、b分解為素因子，取不同素因子最高次冪的積。[198，240，360]198=23211240=2435360=23325[198，240，360]=2432115=7920法2. I.求兩個正整數(shù)的GCM

定理5：若a、b為正整數(shù)，[a,b]=ab/(a,b) 5.最小公倍數(shù)(2)求：[24871,3468]II.求兩個以上正整數(shù)的GCM [a,b,c]=[[a,b],c]求：[198,240,360]6.同余和剩余類同余(余數(shù)相同）：a、b、m為正整數(shù)，由歐幾理德除法，a,b可唯一地表示為：

a=q1m+r1 b=q2m+r2

若r1=r2,則稱a,b關于模m同余，記為ab(modm)6.同余和剩余類(2)模m的剩余類（同余）：全體整數(shù)按模m同余的分為一類，共有m類，稱為模m的同余或剩余類，記為：或{0}，{1}，…,{m-1}定義：{a}+={a+b}{a}.={a.b}定理6：若a1

b1(modm),a2

b2(modm),則 （1）a1+a2b1+b2(modm); (2)a1.a2b1.b2(modm).

a1a2b1b2a1+a2b1+b2同余二、代數(shù)系統(tǒng)1.映射：A->B單射、滿射、雙射（一一對應映射）

2.變換：A=B的映射（到自身的映射）

單變換、滿變換、一一變換(置換)、恒等變換（aA:(a)=a)

3.同態(tài)與同構同態(tài)：若映射：A->B滿足條件：a1,a2A:(a1a2)=(a1)*(a2) ，則稱為A到B的同態(tài)映射，其中,*分別為集合A和B的運算。稱A與B同態(tài)。同構：若同態(tài)映射為雙射（課本有錯），則稱為同構映射，稱A與B同構。a1a2(a1)a1a2AB(a2)(a1)*(a2)a3ba1a2(a1)a1a2AB(a2)(a1)*(a2)同態(tài)同構三、群Group只有一種運算的代數(shù)系統(tǒng)定義：設G是非空集合，并在G定義了一種代數(shù)運算“”

，若下述公理成立，則稱G為群，記為(G,）：(1)滿足封閉性：a,bG:abG;(2)結合律成立：a,bG:（ab）c

=a(bc);(3)存在恒等元：eG:aG:ae

=ea=a;(4)每一元素存在逆元：

aG:

a-1G:aa-1=a-1

a=e.群的階：|G|有限群：|G|<無限群：

|G|=阿貝爾群、交換群：

a,b

G:

ab=b

a.例：全體整數(shù)對于加法構成群，對乘法不構成群。全體偶數(shù)對于加法構成群，對乘法不構成群。

全體實數(shù)R對于加法構成群，對乘法不構成群，但R-{0}對乘法構成群。恒等元為01.群的定義（2）全體矩陣對矩陣加法構成群，恒等元為零矩陣。滿秩矩陣對矩陣乘法構成群，恒等元為單位矩陣。模m的同余全體{0}，{1}，…,{m-1}在模m加法運算下構成群。-{n}={m-n}A={1,2,3}置換1,2,3定義為：定義為置換的復合，即1

2(a)=1(2(a)),則S={1,2,3}對構成群，稱為置換群。3!=6,定義，則S3={1,2,3,4,5,6}對構成群，稱為對稱群（定義2.2.11) 歷史上人們很早就已經(jīng)知道了一元一次和一元二次方程的求解方法。關于三次方程，我國在公元七世紀，也已經(jīng)得到了一般的近似解法，這在唐朝數(shù)學家王孝通所編的《緝古算經(jīng)》就有敘述。到了十三世紀，宋代數(shù)學家秦九韶在他所著的《數(shù)書九章》的“正負開方術”里，充分研究了數(shù)字高次方程的求正根法，也就是說，秦九韶那時候已得到了高次方程的一般解法。

在西方，直到十六世紀初的文藝復興時期，才由意大利的數(shù)學家發(fā)現(xiàn)一元三次方程解的公式——卡當公式。在數(shù)學史上，相傳這個公式是意大利數(shù)學家塔塔里亞首先得到的,后來被米蘭地區(qū)的數(shù)學家卡爾達諾(1501～1576年)騙到了這個三次方程的解的公式，并發(fā)表在自己的著作里。所以現(xiàn)在人們還是叫這個公式為卡爾達諾公式(或稱卡當公式)，其實，它應該叫塔塔里亞公式。

三次方程被解出來后，一般的四次方程很快就被意大利的費拉里(1522～1560年)解出。這就很自然的促使數(shù)學家們繼續(xù)努力尋求五次及五次以上的高次方程的解法。遺憾的是這個問題雖然耗費了許多數(shù)學家的時間和精力，但一直持續(xù)了長達三個多世紀，都沒有解決。法國數(shù)學家拉格朗日更是稱這一問題是在“向人類的智慧挑戰(zhàn)”。

1770年，拉格朗日精心分析了二次、三次、四次方程根式解的結構之后，提出了方程的預解式概念，并且還進一步看出預解式和方程的各個根在排列置換下的形式不變性有關，這時他認識到求解一般五次方程的代數(shù)方法可能不存在。此后，挪威數(shù)學家阿貝爾利用置換群的理論，給出了高于四次的一般代數(shù)方程不存在代數(shù)解的證明。

伽羅華通過改進數(shù)學大師拉格朗日的思想，即設法繞過拉氏預解式，但又從拉格朗日那里繼承了問題轉化的思想，即把預解式的構成同置換群聯(lián)系起來的思想，并在阿貝爾研究的基礎上，進一步發(fā)展了他的思想，把全部問題轉化或歸結為置換群及其子群結構的分析。

這個理論的大意是：每個方程對應于一個域，即含有方程全部根的域，稱為這方程的伽羅華域，這個域對應一個群，即這個方程根的置換群，稱為這方程的伽羅華群。伽羅華域的子域和伽羅華群的子群有一一對應關系,這樣，伽羅華把代數(shù)方程可解性問題轉化為與方程相關的置換群及其子群性質的分析問題，這就是伽羅華工作的重大突破。對于任一個取有理數(shù)值的關于根的多項式函數(shù)，伽羅華群中的每個置換都使該函數(shù)的值不變。反過來，如果伽羅華群中的每個置換都使一個根的多項式函數(shù)的值不變，則這多項式函數(shù)的值是有理的。因此一個方程的伽羅華群完全體現(xiàn)了他的根（整體）的對稱性。伽羅華的工作主要基于兩篇論文──“關于方程根式解的條件”和“用根式求解的本原方程”。在這些論文中，伽羅華將其理論應用于代數(shù)方程的可解性問題，由此引入了群論的一系列重要概念。在《關于方程代數(shù)解法論文的分析》中，伽羅華提出了一個重要定理（未加證明）：一個素數(shù)次方程可用根式求解的充要條件是這個方程的每個根都是其中兩個根的有理函數(shù)。伽羅華用它判別特殊類型方程的根式解問題。2.群的性質定理7：群(G,）具有如下性質：(1)恒等元是唯一的，每個元素的逆元也是唯一的。（定理2.2.1)(2)a,bG:(ab)-1=b-1a-1。（定理2.2.2)(3)a,bG:方程ax=b有唯一解x=a-1b;方程ya=b有唯一解y=ba-1

。 （定理2.2.3)(4)消去律成立：ax=ayx=y。3.半群與弱群半群：無恒等元，當然也無逆元（定義2.2.9）弱群（Monoid群，類群）：有恒等元，無逆元（定義2.2.10）4.子群（1）定義：群(G,）的非空子集H對于構成群，稱H為G的子群。

G,{e}:假子群，平凡子群

HG且H{e}:真子群（2）定理8：群(G,）的非空子集H為子群的充要條件：i.a,bH:abH(對H的封閉性），且

ii.aH:a-1H(逆元也在H內(nèi)）?；騛,bH:ab-1H。5.有限群的陪集群G:e,g1,g2,…子群H:h1=e,h2,h3,…若g1H,則用g1構成一個集合g1H:g1,g1

h2,g1

h3,…。叫H的左陪集若g2H且g2g1H，用g2構成第2個左陪集g2H:g2,g2

h2,g2

h3,…。G={{0},{1},…{8}}對模9加構成群H={{0},{3},{6}}對模9加構成子群{1}+H={{1},{4},{7}}{2}+H={{2},{5},{8}}定理9（陪集的性質）兩個陪集g1H，g2H滿足：

i.g1Hg2H

g1Hg2H=

ii.g1Hg2H

g1H=g2H陪集之間不會相交,可見，有限群G可以按H劃分為有限個不交的陪集，個數(shù)為|G|/|H|問題：陪集是從什么概念抽象出來的？5.有限群的陪集(2)(2)拉格朗日（Lagranges)定理：子群的階一定是群的階的因子6.正規(guī)子群（不變子群）定義：設H為G的子群，若aG:aH=Ha,稱H是G的正規(guī)子群。定理10：子群(H,)為(G,)的正規(guī)子群的充要條件： aG，hH:a-1haH(定理2.4.4)(3)定理11（子群的性質）：設(H,)為(G,)的正規(guī)子群，定義G的兩個陪集aH和bH的運算*為：（aH）*（bH）=（ab)H，則正規(guī)子群的陪集對*構成群。G={{0},{1},…{8}}對模9加構成群，H={{0},{3},{6}}對模9加構成子群{1}+H={{1},{4},{7}}，{2}+H={{2},{5},{8}}（{1}+H)+H={1}+H({1}+H)+({2}+H)=H7.商群G={{0},{1},…{8}}對模9加構成群H={{0},{3},{6}}對模9加構成子群{1}+H={{1},{4},{7}}{2}+H={{2},{5},{8}}（{1}+H)+H={1}+H({2}+H)+H={2}+H({1}+H)+({2}+H)=H{H,{1}+H,{2}+H}對+構成群。商群是構成新群的方法之一。定義：群G的正規(guī)子群H的全體陪集構成的群稱為G關于H的商群，記為G/H。四、環(huán)與域1.環(huán)定義：非空集合R中，定義了兩種代數(shù)運算“+”和“*”，若滿足下述公理，則稱R構成一個環(huán)，記為（R,+,*)。R在+下構成阿貝爾群； (2) 運算*滿足封閉性：a,bR:a*bR;(3)運算*結合律成立：a,bR:(a*b）*c

=a*(b*c);(4)*對+的分配律成立：a,b,cR:a*(b+c)=a*b+a*c且(b+c)*a=b*a+c*a可見，R在*下為半群，不一定有恒等元，當然也不一定有逆元。若有恒等元（這時為弱群），稱為有單位元環(huán)。若每個非零元素有逆元，但對乘法不可換，則稱為除環(huán)（商域、斜域、Skew域）全體整數(shù)對于整數(shù)加法和乘法構成環(huán)。全體偶數(shù)對于整數(shù)加法和乘法構成環(huán)。 m的全體剩余類對剩余類加和乘構成環(huán)，稱為剩余類環(huán)，記為Zm.（可擴展到商群，見定理4.1.2）由于有分配律，環(huán)的兩個運算地位不是一樣的由于有分配律，運算＋的單位元0與任何一個元素進行*運算，結果都為0，即：

aR:a*0=0*a=0設a*0=bR,a*0=a*(0+0)=a*0+a*0,則b=b+b,b+(-b)=b+b+(-b),得，b=0,即a*0=02.域域：乘法可換，有乘法單位元，非零元素對乘法有逆元的環(huán)定義：非空集合F中，定義了兩種代數(shù)運算“+”和“*”，若滿足下述公理，則稱F構成一個域，記為（F,+,*)。(1)F在+下構成阿貝爾群； (2)F-{0}在*下構成阿貝爾群；(3)*對+的分配律成立：a,b,cR:a*(b+c)=a*b+a*c且(b+c)*a=b*a+c*a 若每個非零元素有逆元，但對乘法不可換，則稱為除環(huán)（商域、斜域、Skew域） 有理數(shù)、實數(shù)、復數(shù)對普通加法和乘法構成域，分別稱為有理數(shù)域、實數(shù)域、復數(shù)域。q階有限域，記為GF(q),或Fq六、線性空間1.線性空間（矢量空間）的定義若域(F,+,)上的n重數(shù)組（a1,a2,…,ai,…,an),aiF的集合V滿足下述條件，稱V是F上的一個n維線性空間，記為定義運算為矢量加，則（V,)構成阿貝爾群；vV稱矢量，cF稱標量或純量，定義運算c*v，c*vV,稱*為矢量的數(shù)乘；分配律成立，即u,vV,c,dF:c*(u

v)=c*u

c*v且(c+d)*v=c*v

d*v;結合率成立，即vV,c,dF:(cd)*v=c*(d*v)。如不引起混淆，*、可省略，+、統(tǒng)一記為+例，GF(2)上的n重數(shù)組全體，定義為各位相加，定義*為標乘，則構成一線性空間。六、線性空間22.子空間若V1V且V1滿足線性空間的條件,稱V1為V的子空間.3.線性組合域F的矢量v1,v2,…,vk的線性組合定義為u=b1*v1+b2*v2+…+bi*vi+…+bk*vk,biF4.定理12(定理2.6.1)線性空間V中矢量v1,v2,…,vk的所有線性組合的集合S是V的子空間.5.線性相關設v1,v2,…,vk是線性空間V中的一組非全零矢量,當且僅當存在有一組不全為零的標量c1,c2,…,ck(ciF;i=1,2,…,k)使c1*v1+c2*v2+…+ck*vk=0成立,則稱這組矢量線性相關,否則稱矢量線性無關(或線性獨立).六、線性空間3GF(2)上的三重(010),(100),(001)線性無關,但(010),(100),(110)線性相關.6.定理13(定理2.6.2,線性相關的充要條件)非零矢量v1,v2,…,vk線性相關的充要條件是存在矢量vi(i=1,2,…,k)可以表示為其余矢量的線性組合.7.張成線性空間V中每一個矢量可以由矢量集S的矢量線性組合生成,則稱S張成了V.當S內(nèi)的矢量線性獨立時，S稱為V的基底.8.