第十八章环与域 18.1环的定义及其性质 环的定义 环的性质 特殊的环 有限域 182子环、理想、商环、环同态 子环定义及判别 理想、商环、环同态
1 18.1 环的定义及其性质 环的定义 环的性质 特殊的环 有限域 18.2 子环、理想、商环、环同态 子环定义及判别 理想、商环、环同态 第十八章 环与域
环的定义 定义:设代数系统满足 构成Abel群 构成半群 对+运算满足分配律 符号说明:0,1,x,x,mx,x,xy, 实例: 数环Z,Q,RC关于普通数的加法与乘法
2 定义：设代数系统满足 构成 Abel 群 构成半群 ⋅对+运算满足分配律 符号说明：0, 1, -x, x-1, nx, xn, x-y, 实例： 数环 Z,Q,R,C 关于普通数的加法与乘法 环的定义
环的性质 1.0=0a=0 2.(a)b=a(-b)=(ab) 3.(a)-b)=ab 4. a(b-c)=ab-ac, (b-c)a= ba-ca 5.∑∑b=∑∑ 6.(nab=a(nb)=n(ab)
3 1． a0 = 0a = 0 2． (-a)b = a(-b) = -(ab) 3． (-a)(-b) = ab 4． a(b-c) = ab-ac, (b-c)a = ba-ca 5． ∑ ∑ ∑ ∑ = = = = =⎟⎟⎠⎞ ⎜⎜⎝⎛⎟⎟⎠⎞ ⎜⎜⎝⎛ ni mj i j mj j ni i a b a b 1 1 1 1 6． (na)b = a(nb) = n(ab) 环的性质
特殊的环 交换环、含幺环 无零因子环mb=0→a=0或b=0 实例:数环,Z为无零因子环当且仅当P为素数 定理:R是环,R为无零因子环R中乘法有消去律. 除环:{R}>1,构成群 域|R>1,交换的除环或者每个R中元素都有逆元的整环 实例:H ba/ab∈R}为除环,不是域 Z是域
4 交换环、含幺环 无零因子环 ab=0 ⇒ a=0 或 b=0 实例：数环, Zp 为无零因子环当且仅当 p 为素数. 定理：R 是环，R 为无零因子环 ⇔ R 中乘法有消去律. 除环：|R|>1, 构成群 域 |R|>1, 交换的除环或者每个 R*中元素都有逆元的整环 实例： ⎭⎬⎫ ⎩⎨⎧ ∈ ⎟⎟⎠⎞ ⎜⎜⎝⎛ − = a b R b a a b H | , 为除环，不是域 Zp 是域 特殊的环
例题 例1p,q为不等的素数,证明无p阶的整环 证:假设R为p阶的整环, 则为p阶的Abel群 存在p阶元a,q阶元b 所以a+b=P,为循环群, 令c=a+b.生成元 R={0,c,2c,…,(p1e} 取 pc, y-=gc, 则 xy=(pc)(gc)=pgc =0 xy为零因子
5 例 1 p,q 为不等的素数，证明无 pq 阶的整环. 证：假设 R 为 pq 阶的整环， 则为 pq 阶的 Abel 群. 存在 p 阶元 a，q 阶元 b. 所以 |a+b|=pq, 为循环群， 令 c=a+b 为生成元. R={ 0, c, 2c, … , (pq-1)c } 取 x=pc, y=qc, 则 xy=(pc)(qc) = pqc2 =0 x,y 为零因子. 例题
有限域 定义:F为域,鬥有限 实例:ZmP为素数 Z为整环,有限半群, 无零元,适合消去律,构成Abel群 结论:有限的整环都是域 有限域的特征 F为有限域,1在中的阶为域F的特征 的特征为p
6 定义：F 为域，|F|有限 实例：Zp, p 为素数 Zp 为整环，有限半群， 无零元，适合消去律，构成 Abel 群 结论：有限的整环都是域 有限域的特征 F 为有限域，1 在中的阶为域 F 的特征. Zp的特征为 p. 有限域
有限域的性质 设F为有限域,则存在素数p使得F=p, 证明思想: A=={0,1,…,p-1 Ax1={0,x,2x,…,(p-1x},xieF 若F=Ax1则结束;否则丑x2∈F-Ax,x2=0, Axi+Ax2=a1x+2x2 a1, 2EA 可以证明Ax1+Ax2中的元素两两不同, 因此|Ax1+x2|2, 照此处理,x+42+4p,直到穷尽所有的元素
7 设 F 为有限域，则存在素数 p 使得|F|=pn, 证明思想: A=={ 0, 1, … , p−1 } Ax1 = { 0, x1, 2x1, …, (p−1)x1}，x1∈F* |Ax1| = p 若 F=Ax1 则结束；否则 ∃x2∈F−Ax1, x2≠0, Ax1+Ax2 ={ a1x1+a2x2 | a1,a2∈A} 可以证明 Ax1+Ax2 中的元素两两不同， 因此|Ax1+Ax2|=p2 , 照此处理，|Ax1+Ax2+Ax3|=p3, 直到穷尽所有的元素 有限域的性质
有限域应用—素数测试问题 Fermat小定理:如果n为素数,则对所有的正整数 a≠0(modm)有a=l(modn) 测试素数的算法: 令a=2,检测=1(modn)? 如果回答“是”,输出“素数”;否则输出“合数” 分析: 时间T(m)=0og3n) 问题: 该算法只对a=2进行测试,如果n为合数且输出为“素 数”,则称n为基2伪素数.例如341满足上述条件,但 是341是合数
8 Fermat 小定理：如果 n 为素数，则对所有的正整数 a ≠ 0(modn) 有 an−1≡1(mod n) 测试素数的算法： 令 a=2, 检测 an−1≡1(mod n)? 如果回答“是”，输出“素数”；否则输出“合数”. 分析： 时间 T(n)=O(log3n) 问题： 该算法只对 a=2 进行测试, 如果 n 为合数且输出为“素 数”，则称 n 为基 2 伪素数. 例如 341 满足上述条件，但 是 341 是合数. 有限域应用----素数测试问题
素数测试的随机算法 改进方法: 随机选取2-n2中的数,进行测试.例如取a=3,则 34(mod34)=56,341不是素数 新问题: Fermat小定理的条件只是必要条件,满足条件的可能是合 数.对所有与n互素的正整数a,都满足上述条件的合数n 称为 Carmichael数,如561,1105,1729,2465等 Carmichael数非常少,小于103的只有255个 可以证明:如果n为合数,但不是 Carmichael数,采用随机 选取2n-2中的数进行测试,测试n为合数的概率至少为 1/2.但是这个算法不能解决 Carmichael数的问题
9 素数测试的随机算法 改进方法： 随机选取 2-- n-2 中的数，进行测试. 例如取 a=3，则 3340(mod 341) ≡ 56，341 不是素数. 新问题： Fermat 小定理的条件只是必要条件，满足条件的可能是合 数. 对所有与 n 互素的正整数 a，都满足上述条件的合数 n 称为 Carmichael 数，如 561，1105，1729，2465 等. Carmichael 数非常少，小于 10 8的只有 255 个. 可以证明：如果 n 为合数，但不是 Carmichael 数，采用随机 选取 2— n-2 中的数进行测试，测试 n 为合数的概率至少为 1/2. 但是这个算法不能解决 Carmichael 数的问题
素数测试的另一个条件 定理2如果n为素数,则方程x2=1(modm的根只有两个, 即x1,x=-1(或x=n-1) 证明x(modn)=1台x2-1=0(mdm) (x+1)x-1=0mod 分x+1=0或x1=0(域中没有零因子) 台x=-1或r=1 称过的根为非平凡的 根据定理2,如果方程有非平凡的根,则n为合数例如: x(mod5)≡1分x=1或x=4 x(mod12)三1台=1或x=5或x=7或x=ll 5和7是非平凡的根
10 素数测试的另一个条件 定理 2 如果 n 为素数，则方程 x 2 ≡ 1(mod n )的根只有两个， 即 x=1，x = − 1（或 x = n − 1 ） 证明 x2(mod n ) ≡1 ⇔ x 2 − 1 ≡0(mod n) ⇔ (x+1)(x−1) ≡0(mod n) ⇔ x+1 ≡0 或 x− 1 ≡0 （域中没有零因子） ⇔ x = −1 或 x=1 称 x±≠ 1 的根为非平凡的. 根据定理 2，如果方程有非平凡的根，则 n 为合数. 例如: x 2(mod 5) ≡ 1 ⇔ x=1 或 x=4 x 2(mod 12) ≡1 ⇔ x=1 或 x=5 或 x=7 或 x=11 5 和 7 是非平凡的根