離散數(shù)學(xué)II課件：6_7環(huán)同態(tài)

1、環(huán)在密碼學(xué)中的應(yīng)用,設(shè)(Z26,+26)為模26的整數(shù)加法群，+26為模26的加法運(yùn)算，該群可用來(lái)對(duì)移位密碼體制(Caesar cipher)的原理進(jìn)行簡(jiǎn)單刻畫(huà)。設(shè)移位密碼體制中有： 明文； IREADABOOK 密文：LUFDGDERRN 密鑰：K=3 其中密文L由明文I在英文字母表內(nèi)循環(huán)后移3位得到，其他類同。注意，這里循環(huán)后移3位指明文X 變?yōu)槊芪腁,R變?yōu)槊芪腢等等，這一加密法則可概括為群(Z26,+26)中的表達(dá)式 y=x+263,x,yZ26 (1),這里 x為明文，y為密文，字母ABCDXYZ分別對(duì)應(yīng)0，1，2，3,23，24，25。加密明文時(shí)，先將明文字母串變換為Z26上的數(shù)字

2、串，再按上述表達(dá)式每次一個(gè)字符地將明文數(shù)字串變換為密文數(shù)字串，最后將密文數(shù)字串變換為密文字母串。式（1）可更簡(jiǎn)潔地寫(xiě)為 Y=x+3mod26, x,yZ26 (2),環(huán)在密碼學(xué)中的應(yīng)用,環(huán)在密碼學(xué)中的應(yīng)用(仿射密碼),由前面的知識(shí)我們知道(Z26,+26,26)為環(huán)。仿射密碼(Affine cipher)可由該環(huán)刻畫(huà)。仿射密碼體制的加密變換為 y=(a26x)+26b, x,yZ26 （3） 其中,a與b為參數(shù)且a與26互質(zhì)，而x為明文，y為密文，與上例一樣，字母ABCDXYZ分別對(duì)應(yīng)0，1，2，3,23，24，25。加密明文時(shí)，先將明文字母串變換為Z26上的數(shù)字串，再按上述表達(dá)式每次一個(gè)字符

3、地將明文數(shù)字串變換為密文數(shù)字串，最后將密文數(shù)字串變換為密文字母串。式（3）可更簡(jiǎn)潔地寫(xiě)為 Y=ax+bmod26,x,yZ26 (7),6.7 環(huán) 同 態(tài),6.7.1 理想 6.7.2 環(huán) 中 合 同 關(guān) 系 6.7.3 環(huán) 同 態(tài) 與 同 構(gòu) 6.7.4 單純環(huán)與極大理想,6.7.1 理想,定義. 設(shè)R是一個(gè)環(huán)，R的一個(gè)子集N說(shuō)是R的一個(gè)理想子環(huán)，簡(jiǎn)稱理想，如果 （1）N非空； （2）若aN,bN,則a-bN; （3） 若aN,R,則 aN,aN。 平凡理想：0，R,理想的例,設(shè)R為實(shí)數(shù)域上的二階正方矩陣環(huán)， 形如 的所有元素組成的子集為 N，則N為R的子環(huán)，但不是R的理想。 比如，取x=

4、R，a= N，則 xa = N。,理想的例,設(shè)R=（Z,+,*)是整數(shù)環(huán)，則nZ是R的理想，其中n為自然數(shù)，容易看出(nZ,+)是Abel群。任取kZ，有knz nZ和nzk nZ。即knZnZ和nZk nZ，所以nZ是R的理想。,結(jié)論1. 理想一定是子環(huán),但子環(huán)未必是理想。 結(jié)論2. 任意體R只有平凡理想。 證明： 任取R的理想N，若N=0，則得證。否則，往證N=R。 因N 0，故存在aN，且a 0。 于是有a的逆元素a-1R。由N為理想知，有 a-1 aN，即R中的1N。 從而對(duì)R中任意元素x，都有x = 1xN。 因此，R N。故N=R。,例子,設(shè)R是含1的交換環(huán)，且10，則R是域當(dāng)且僅

5、當(dāng)R只含平凡理想。 證明：必要性證明如結(jié)論2。 充分性，任取xR,x0 ,則易證D=Rx=rxrR是R的理想，從而有Rx=R,這就證明了存在yR，使得yx=1,y是x的逆元。即R是交換體（域）。,結(jié)論3. 設(shè)R是有壹的交換環(huán)，aR，則 aR=ar | rR是R的理想，而且包含a。 證明： (1)aR非空，因?yàn)?=a0aR，a=a1aR。 (2)若xaR，yaR，則存在r1，r2R， 使得x=ar1，y=ar2，故 x-y = a（r1-r2） aR (3) 若zaR，rR，則存在r3R，使得 z = ar3， 故 zr = ar3r = a(r3r)aR，rz = rar3 =a(r r3)a

6、R。 因此，aR是含a的理想。,定義. 設(shè)R是有壹的交換環(huán)，aR，則aR稱為由a生成的主理想，記為（a）。 (a)=aR=R在什么條件下成立?什么條件下不成立為什么? 結(jié)論4. 環(huán)R的主理想（a）是R中包含a的理想中最?。ㄔ诩习P(guān)系下）的理想。 證明：設(shè)N是R中包含a的任一理想，往證（a） N。 任取x(a)，即xaR，則存在rR，使得x=ar。由aN， rR，N是理想知，arN，即xN。所以，（a） N。,主理想結(jié)論,6.7.2 環(huán) 中 合 同 關(guān) 系,定義. 設(shè)R是一個(gè)環(huán)，N是一理想。對(duì)于a，bR，如果 a-b=nN，或a=b+n，nN， 則稱a和b模N合同，記為 ab (mod N)

7、。 N的一個(gè)剩余類:N的一個(gè)陪集。 含a的剩余類:a+N. 例 設(shè)環(huán)R=(Z,+, )是整數(shù)環(huán)，4Z=4kkZ是R的理想，0+N=,-4,0,4,8,1+N=,-3, 1,5,9,都是N的剩余類。 例. 設(shè)R為整數(shù)環(huán)I，N=（m）=mI，則 ab（mod N），即a-bmI或ma-b，即 ab（mod m）。,定理6.7.1 在環(huán)R中，對(duì)于模N，有 (1)反身性：aa; (2)對(duì)稱性：若ab，則ba; (3)傳遞性：若ab，bc，則ac; (4)加法同態(tài)性：若ab,cd,則acbd。 (5)乘法同態(tài)性：若ab，cd，則acbd。,環(huán)中合同關(guān)系的性質(zhì),(1)至(3)在群中已證，不過(guò)是加法群R模加

8、法子群N的合同性。 （4）因?yàn)閍b,cd,故a+N = b+N,c+N = d+N,于是 ac+N = a+N（c+N）= b+N（d+N）= bd+N, 即acbd。 （5）因?yàn)閍 b，cd，故a = b+n1，c = d+n2，n1N，n2N。于是 ac =bd+ bn2 + n1d + n1n2。 但N是一個(gè)理想，故bn2N，n1dN，n1n2N， 因而bn2 + n1d + n1n2N，故acbd.,證明,定義. 設(shè)R是一個(gè)環(huán),S是有加、乘兩種運(yùn)算的系統(tǒng)，稱R到S中的映射是環(huán)R到S中的同態(tài)映射，如果 (a+b)=(a)+(b)，(ab)=(a)(b)。 若R到R上有一個(gè)同態(tài)映射,則稱R

9、與R同態(tài),記為 RR。 定義. 若是環(huán)R到系統(tǒng)R上的一對(duì)一的同態(tài)映射，則稱是R到R上的同構(gòu)映射或同構(gòu)對(duì)應(yīng)。 若R到R上有一個(gè)同構(gòu)映射，則稱R與R同構(gòu)，記為R R。,6.7.3 環(huán)同態(tài)與同構(gòu),定理6.7.2 設(shè)R是一個(gè)環(huán),S是一個(gè)有加法和乘法 的運(yùn)算系統(tǒng).若是R到S中的一個(gè)同態(tài)映射,則 R的映象R=（R）也是一個(gè)環(huán)， (0)就是R的零0， (-a)=-(a)。 若R有壹而R不只有一個(gè)元素，則 R有壹而且（1）就是R的壹1； 若aR有逆，則（a）在R中有逆而且 （a-1）就是（a）-1。,設(shè)是環(huán)R到R上的同態(tài)映射，R的 零0的逆映象-1(0)叫的核。 -1(0)=x x R ,(x)=0,環(huán)的同態(tài)

10、核,定理6.7.3 同態(tài)映射的核N是R的一個(gè)理想。設(shè) a是R的任意元素，則a的逆映象 -1(a)=aR(a)=a是N的一個(gè)剩余類.。 證明：因?yàn)槭荝的加法群到R的加法群上面 的同態(tài)映射,所以的核N=-1(0)是R的子群， 且a的逆映象-1(a)是模N的一個(gè)剩余類。 再證N做成理想，若aN，R，則 (a)=(a)()=0()=0， 故aN，同樣可證aN。,環(huán)的第一同態(tài)定理,設(shè)R是環(huán)，N是R的理想，對(duì)R的關(guān)于N的 剩余類引進(jìn)運(yùn)算，規(guī)定： （a+N）+（b+N）（a+b）N （a+N）（b+N ） = ab+N,剩余類的加、乘,定理6.7.4 按照剩余類的加法和乘法，R對(duì) 于理想N的所有剩余類的集合

11、RN是一個(gè)環(huán)，RN叫做R對(duì)于N的剩余環(huán) （商環(huán)） 規(guī)定（a）= a+N，則是R到RN上的一個(gè)同態(tài)映射，其核為N。 證明：分析，由群中已證的結(jié)果，模N的所有剩余類的加法作成一個(gè)加法群，就是R對(duì)于N的商群R/N，如果規(guī)定(a)= a+N，則是加法群R到到商群RN上的一個(gè)同態(tài)映射，其核為N。那么要想證明是環(huán)R到R/N上的同態(tài)映射，必須有(ab)=(a)(b)成立，而根據(jù)剩余類乘法的定義(ab)=ab+N=(a+N)(b+N)=(a)(b)。,環(huán)的第二同態(tài)定理,例子 設(shè)環(huán)R=(Z,+, )是整數(shù)環(huán)，4Z=4kkZ是R的理想，商環(huán)(Z/4Z,)稱為模4的剩余類環(huán)，其中Z/4Z=0+4Z,1+4Z,2+4

12、Z,3+4Z= , , , 且 = , = 。并且模4的剩余類環(huán)和模4的整數(shù)環(huán)是同構(gòu)的。 定理6.7.5 若是環(huán)R到R上的一個(gè)同態(tài)映 射，其核為N，則R與RN同構(gòu)： R RN。 證明：設(shè)a是R的任意元素，則-1(a)是N 的一個(gè)剩余類。規(guī)定R到RN上的映射 ：a -1(a) 。 則是R到RN上的對(duì)應(yīng)的加群同 態(tài)映射。,環(huán)的第三同態(tài)定理,只需證明乘同態(tài)，即若a，bR，往證（ab）=（a）（b） 由a,bR,有a,b R,使得(a)=a, (b)=b, 于是，(ab)= -1(ab） = -1(a) (b) = -1(ab)=ab+N (a)(b)= -1(a) -1(b) = -1(a) ) -

13、1( (b) =(a+N)(b+N)= ab+N 故是R到RN上的一個(gè)同構(gòu)對(duì)應(yīng)。,證明,設(shè)環(huán)R同態(tài)于R:RR,同態(tài)核為N,于是 R與N之間的子環(huán)與R的子環(huán)一一對(duì)應(yīng)， 大環(huán)對(duì)應(yīng)大環(huán)，小環(huán)對(duì)應(yīng)小環(huán)， 理想對(duì)應(yīng)理想。 R與（0）間無(wú)理想 iff R與N間無(wú)理想。 例 設(shè)環(huán)R1=(Z,+,)是整數(shù)環(huán)， 到R2=(Z8, , ) 是模8的整數(shù)環(huán)。令:ZZ8, (x)=x(mod8), xZ,則是R1到R2的同態(tài)映射，N=8Z是同態(tài)核，我們可以看到R1包含著N的理想是：,定理6.7.6,例子,N1=R1=Z, N2=2Z=2k kZ, N3=4Z= 4k kZ, N4=8Z= 8k kZ。 R2的理想是：

14、 Z8,0,2,4,6,0,4,0。 令A(yù)1=Z,2Z,4Z,8Z, A2=Z8,0,2,4,6,0,4,0并定義f:A1A2,f(Z)=Z8,f(2Z)= 0,2,4,6,f(4Z)= 0,4,f(8Z)= 0。則f是A1和A2之間存在一一對(duì)應(yīng)關(guān)系。,定義.如果環(huán)R除自己和（0）外沒(méi)有別的理想,則稱R為單純環(huán)。 例. 設(shè)R是模5的整數(shù)環(huán):0，1，2，3，4。任取R的理想N,則從加法角度看,N是R的子群，故由Lagrange定理,|N|R|。而|R|=5,所以|N|只能為1或5,亦即,N 或?yàn)?0),或?yàn)镽,因此，R是單純環(huán)。,6.7.4 單純環(huán)與極大理想,定義. 環(huán)R的一個(gè)理想N說(shuō)是一個(gè)極大

15、理想，如果N R，而R與N之間沒(méi)有別的理想。 例. 設(shè)R是模12的整數(shù)環(huán)：0,1,2,11。 設(shè)N1=6R=0，6,則N1是主理想,但非極大理想:有R的理想N2=2R=0,2,4,6,8,10,且N N2 R。 N2是R的極大理想。 若取N3=3R=0,3,6,9,則N3也是R的極大理想。 可見(jiàn)，極大理想不唯一。,極大理想,定理6.7.7 若N R，則N是R的極大理想必要而且只要RN是單純環(huán)。 證明：因RRN，所以， N是R的極大理想iff R與N之間沒(méi)有別的理想 iff RN與（0）間無(wú)理想 iff RN是單純環(huán)。 例. 由上例,N2是R的極大理想,故 R/N2= N2 ,1+N2為單純環(huán).N1不是極大理想,則 R/N1=N1,1+N1,2+N1,3+N1,4+N1,5+N1不是單 純環(huán)。,極大理想與單純環(huán)的關(guān)系,定理6.7.8 任意有壹的交換的單純環(huán)R是一個(gè)域。 證明： 只需證明R中任意非零元素有逆。 任取aR，a0?？碼R=（a），因?yàn)閍0， 又aaR。故aR（0）。但R為單純環(huán)，故 aR=R。今R有壹，故必有R中之元素b適合ab=1， 即a在R中有逆b。,單純環(huán)與域的關(guān)系,定理6.7.9 任意域F是有壹的交換的單純環(huán)。 證明： 取F的任意理想N(0)，往證N=F。 由N(0)知，有aN，a0，于是有a-1F。 因?yàn)镹是F的理想，故aa-1N，即1N，因