离散数学－代数结构 南京大学计算机科学与技术系

Presentation on theme: "离散数学－代数结构 南京大学计算机科学与技术系"— Presentation transcript:

1 离散数学－代数结构 南京大学计算机科学与技术系
循环群与群同构 离散数学－代数结构 南京大学计算机科学与技术系

2 循环群与群同构 循环群与生成元 循环群的子群 群的同构与同态 无限循环群的同构群 有限循环群的同构群 (循环)群的直积

3 循环群与生成元 定义（循环群） 𝐺,∗ 为循环群（cyclic group）是指： ∃𝒂∈𝑮 𝑮= 𝒂
∃𝒂∈𝑮 𝑮= 𝒂 这里， 𝒂 = 𝒂 𝒏 𝒏∈ℤ ，𝑎称为𝐺之生成元（generator）

4 循环群与生成元（续） 定义（有限循环群）：若循环群𝐺的生成元𝑎的阶为𝑛，则称𝐺为有限循环群，即𝑛阶循环群。
𝑮= 𝒂 𝟎 , 𝒂 𝟏 , 𝒂 𝟐 ,⋯, 𝒂 𝒏−𝟏 ，其中 𝑎 0 为单位元。 定义（无限循环群）：若循环群𝐺的生成元𝑎为无限阶元，则称𝐺为无限循环群。 𝑮= 𝒂 𝟎 , 𝒂 ±𝟏 , 𝒂 ±𝟐 ,⋯ ，其中 𝑎 0 为单位元。

5 循环群与生成元（续） 例1：无限循环群 ℤ,+ ℤ,+ 是循环群，恰有2个生成元：1和−1
∵𝑛为ℤ之生成元⇔ℤ= 𝑛 ⇔ ∃𝑘∈ℤ 𝑛 𝑘 =1⇔ ∃𝑘∈ℤ 𝑘⋅𝑛=1 ⇔𝑛∈ 1,−1 ∴1和−1均是其生成元

6 循环群与生成元（续） 例2：有限循环群 模6剩余加群 ℤ 6 , ⊕ 6 是循环群，恰有2个生成元：1 和 5
模6剩余加群 ℤ 6 , ⊕ 6 是循环群，恰有2个生成元：1 和 5 5 0 =0， 5 1 =5， 5 2 =4， 5 3 =3， 5 4 =2， 5 5 =1.

7 循环群与生成元（续） 例3：非循环群 Klein四元群(𝑉,∗)不是循环群，因为对任何𝑥∈𝑉， 𝑥 = 𝑒,𝑥 ：

8 无限循环群的生成元 命题：若𝑎是无限循环群的生成元，则 𝑎 −1 也是该无限循环群的生成元
设群𝐺= 𝑎 = 𝑎 𝑘 𝑎∈𝐺,𝑘∈ℤ ， 𝑎 𝑘 = 𝑎 −1 −𝑘 ，令𝑝=−𝑘，则𝐺= (𝑎 −1 𝑝 𝑝∈ℤ ，故𝐺= 𝑎 −1

9 无限循环群的生成元（续） 命题：无限循环群有且只有2个生成元
证明：∵设群𝐺= 𝑎 = 𝑎 𝑘 𝑎∈𝐺,𝑘∈ℤ ，若𝑏亦为𝐺的生成元，则：(∃𝑚,𝑡∈ℤ)( 𝑎 𝑚 =𝑏∧ 𝑏 𝑡 =𝑎)，故𝑎= 𝑏 𝑡 = 𝑎 𝑚 𝑡 = 𝑎 𝑚𝑡 ，由消去律， 𝑎 𝑚𝑡−1 =𝑒 ∵𝑎是无限阶元 ∴𝑚𝑡−1=0⇒ 𝑚=𝑡=1 ∨ 𝑚=𝑡=−1 ，故有𝑏=𝑎或者𝑏= 𝑎 −1

10 有限循环群的生成元 命题：设有限群𝐺= 𝑎 ，且 𝑎 =𝑛，则对任意不大于𝑛的正整数𝑟，𝑮= 𝒂 𝒓 ⇔ 𝐠𝐜𝐝 𝒏,𝒓 =𝟏
命题：设有限群𝐺= 𝑎 ，且 𝑎 =𝑛，则对任意不大于𝑛的正整数𝑟，𝑮= 𝒂 𝒓 ⇔ 𝐠𝐜𝐝 𝒏,𝒓 =𝟏 “⇐”：设 gcd 𝑛,𝑟 =1，则(∃𝑢,𝑣∈ℤ)(𝑢𝑟+𝑣𝑛=1)，因此𝑎= 𝑎 𝑢𝑟+𝑣𝑛 = 𝑎 𝑟 𝑢 𝑎 𝑛 𝑣 = 𝑎 𝑟 𝑢 。故而𝐺中任意元素 𝑎 𝑘 可表为 𝑎 𝑟 𝑢𝑘 ，故有𝐺= 𝑎 𝑟 ； “⇒”：设 𝑎 𝑟 是𝐺的生成元，令 gcd 𝑛,𝑟 =𝑑且𝑟=𝑑𝑡，则 𝑎 𝑛 𝑡 = 𝑎 𝑛 𝑟/𝑑 = 𝑎 𝑟 𝑛/𝑑 =𝑒，故 𝑎 𝑟 (𝑛/𝑑) ，但 𝑎 𝑟 =𝑛故𝑛| 𝑛 𝑑 ⇒𝑑=1，故有 gcd 𝑛,𝑟 =1即𝑛与𝑟互质

11 有限循环群的生成元（续） 𝑛阶循环群𝐺的生成元的个数恰好等于不大于𝑛且与𝑛互质的正整数的个数，即Euler函数𝜑(𝑛)，其生成元集为：
𝑖 0<𝑖≤𝑛∧gcd 𝑖,𝑛 =1

12 有限循环群的生成元（续）

13 循环群的子群 命题：设𝐺= 𝑎 为循环群 ⑴ 𝐺的子群为循环群 ⑵ 若 𝑎 =∞，则𝐺的子群除 𝑒 外皆为无限循环群 自然成立 幂

14 循环群的子群（续） 命题：对𝑛的每个因子𝑑，𝑛阶循环群𝐺中恰有一个𝑑阶子群 证明： 令𝐻= 𝑎 𝑛/𝑑 ，显然𝐻是𝐺的𝑑阶子群
令𝐻= 𝑎 𝑛/𝑑 ，显然𝐻是𝐺的𝑑阶子群 若令 𝐻 1 = 𝑎 𝑚 亦为𝑑阶子群，则 𝑎 𝑚 𝑑 = 𝑎 𝑚𝑑 =𝑒，故有𝑛|𝑚𝑑，即 𝑛 𝑑 |𝑚，因此 𝑎 𝑚 = 𝑎 𝑛 𝑑 𝑘 ∈𝐻，即 𝐻 1 ⊆𝐻，但 𝐻 1 ≈𝐻，故有 𝐻 1 =𝐻

15 循环群的子群（续）

16 群同构与同构映射 定义（群同构）：群 𝐺 1 ,∘ 与 𝐺 2 ,∗ 同构( 𝐺 1 ≅ 𝐺 2 )当且仅当存在双射函数𝑓: 𝐺 1 → 𝐺 2 ，满足： ∀𝒙,𝒚∈ 𝑮 𝟏 ，𝒇 𝒙∘𝒚 =𝒇 𝒙 ∗𝒇(𝒚) 例： 正实数乘群 ℝ + ,⋅ 和实数加群 ℝ,+ ，同构映射𝑓: ℝ + →ℝ:𝑓 𝑥 = ln 𝑥

17 群同构与同构映射（续） ? 任意两个三阶群同构 1a 2b 3c a b c 1 2 3 *  a b c 1 2 3 a b c
*  a b c 1 2 3 a b c ? b c c a a b

18 群同构与同构映射（续） 2个不同构的四阶群 1 2 3 4 1 2 3 4 Klein四元群 四元循环群

19 同态与同态映射 定义（群同态）：群 𝐺 1 ,∘ 与 𝐺 2 ,∗ 同态( 𝐺 1 ~ 𝐺 2 )当且仅当存在函数𝑓: 𝐺 1 → 𝐺 2 ，满足： ∀𝒙,𝒚∈ 𝑮 𝟏 ，𝒇 𝒙∘𝒚 =𝒇 𝒙 ∗𝒇(𝒚) 如果上述映射是满射，则称为满同态；如映射是单射，则称为单同态；若 𝐺 1 = 𝐺 2 ，则称𝜑为自同态

20 同态与同态映射（续）

21 同态与同态映射（续） 例：整数加系统 ℤ,+ 与模3剩余加系统 ℤ 3 , ⊕ 3 同态，同态映射为
例：整数加系统 ℤ,+ 与模3剩余加系统 ℤ 3 , ⊕ 3 同态，同态映射为 𝑓:ℤ→ ℤ 3 ，𝑓 3𝑘+𝑟 =𝑟，𝑘∈ℤ 该态射亦为满同态 趣味问题：由1, 2, ⋯,1000这一千个自然数按照任意的组合进行加减，能否得到1001？

22 同态与同态映射（续） 趣味问题：由1, 2, ⋯,1000这一千个自然数按照任意的组合进行加减，能否得到1001？
定义系统（奇偶加群）： 𝑒,𝑜 ,∗ ，运算表如下：

23 无限循环群的同构群 定理：设 𝐺,∗ 为无限循环群，则 𝑮,∗ ≅ ℤ,+ 证明： 𝑎 =∞，令𝑓:ℤ→𝐺如下：𝑓 𝑛 = 𝑎 𝑛 ，
∵𝑓 𝑛+𝑚 = 𝑎 𝑛+𝑚 = 𝑎 𝑛 ∗ 𝑎 𝑚 =𝑓 𝑛 ∗𝑓 𝑚 ∴𝑓为同态；又 ∵𝑓 𝑛 =𝑓 𝑚 ⇒ 𝑎 𝑛 = 𝑎 𝑚 ⇒ 𝑎 |𝑛−𝑚| =𝑒⇒ 𝑛−𝑚 =0⇒𝑛=𝑚∴𝑓为1-1，onto易见，从而 𝐺,∗ ≅ ℤ,+

24 有限循环群的同构群 定理：设 𝐺,∗ 为有限循环群，则 𝑮,∗ ≅ ℤ 𝒏 , ⊕ 𝒏
定理：设 𝐺,∗ 为有限循环群，则 𝑮,∗ ≅ ℤ 𝒏 , ⊕ 𝒏 证明： 𝑎 =𝑛>0从而𝐺={ 𝑎 0 , 𝑎 1 ,⋯, 𝑎 𝑛−1 }，令𝑓: ℤ 𝑛 →𝐺如下：𝑓 𝑖 = 𝑎 𝑖 (𝑖=0,1,⋯,𝑛−1)，由于𝑓 𝑖 ⊕ 𝑛 𝑗 = 𝑎 𝑖 ⊕ 𝑛 𝑗 = 𝑎 𝑖 ∗ 𝑎 𝑗 =𝑓 𝑖 ∗𝑓(𝑗)，故𝑓为同态。又由于𝑓 𝑖 =𝑓 𝑗 ⇒ 𝑎 𝑖 = 𝑎 𝑗 ⇒ 𝑎 |𝑖−𝑗| =𝑒⇒𝑛| 𝑖−𝑗 ⇒𝑖≡𝑗 mod 𝑛 ⇒𝑖=𝑗，故𝑓为单射，𝑓的满射性易见，因此 𝐺,∗ ≅ ℤ 𝑛 , ⊕ 𝑛

25 循环群的同构群 推论：循环群皆为阿贝尔群 定理：设 𝐺,∗ 为无限循环群，则 𝑮,∗ ≅ ℤ,+
定理：设 𝐺,∗ 为有限循环群，则 𝑮,∗ ≅ ℤ 𝒏 , ⊕ 𝒏 推论：循环群皆为阿贝尔群

26 群的直积 给定两个群: (S, ⃘), (T,*), 定义笛卡儿乘积ST上 的运算⊗如下： (ST, ⊗)是群
<s1,t1> ⊗ <s2,t2> = <s1 ⃘s2, t1*t2> (ST, ⊗)是群 结合律： <(r1 ⃘s1) ⃘t1, (r2*s2)*t2> = <r1 ⃘(s1 ⃘t1), r2*(s2*t2)> 单位元素：<1S, 1T> 逆元素：<s, t> 的逆元素是 <s-1, t-1> (其中： s, s-1S, t, t-1T)

27 循环群的直积 CmCn≅Cmn iff m与n互质。其中Ck表示k阶循环群。 若m与n互质，只需证明CmCn含有阶为mn的元素。
(a,b)mn = e, 其中a,b分别是Cm和Cn的生成元素。 若(a,b)k = e, k必是m,n的公倍数，因m与n互质，故k 是mn的倍数。所以，(a,b)的阶是mn。 若CmCn≅Cmn，则CmCn是循环群，设其生成元是(s,t), 则(s,t)的阶是mn, 若gcd(m,n)=k>1, 则(s,t)mn/k =e, 这与(s,t)的 阶是mn矛盾。 注意：sm=e1, tn=e2,

28 欧拉函数(phi) 如果m与n互质，则 φ(m)φ(n) =φ(mn). 

29 欧拉函数(phi) Cn中元素按其阶分类，d阶元素共有φ(d)个，d|n. (Euler定理）若正整数a与n互质，则
小于n且与n互质的正整数及乘法（模n ）构成一个群

30 作业 p. 231 30—35 pp. 204 25—28