复旦大学：《离散数学》PPT教学课件（赵一鸣）23/28

6.3.2 Cyclic groups 1. Order of an element Definition 13: Let G be a group with an identity element e. We say that a is of order n if an=e, and for any (<m<n, amte. We say that the order of a is infinite if an*e for any positive integer n. Example: groupl(l, -1,i-i; x1 i4-=1 (-i)2=-1,(-i)3=i,(-i)4=1

6.3.2 Cyclic groups 1.Order of an element Definition 13: Let G be a group with an identity element e. We say that a is of order n if a n =e, and for any 0<m<n, a me. We say that the order of a is infinite if a n e for any positive integer n. Example:group[{1,-1,i.-i};], i 2=-1,i3=-i, i 4=1 (-i)2=-1, (-i)3=i, (-i)4=1

Theorem 6.14: Let a is an element of the group G, and let its order be n. Then a= e for n∈ Ziff nn. Example: Let the order of the element a of a group g be n. Then the order of ar is n/d, where d=( n) is maximum common factor of r and n Proof:(ar)/d=e, Let p be the order of ar. pn/d, n/dp p=n/d

Theorem 6.14: Let a is an element of the group G, and let its order be n. Then a m=e for mZ iff n|m. Example: Let the order of the element a of a group G be n. Then the order of a r is n/d, where d=(r,n) is maximum common factor of r and n. Proof: (a r ) n/d=e, Let p be the order of a r . p|n/d, n/d|p p=n/d

2. CV yclic groups Definition 14: The group G is called a cyclic group if there exists gEG such that h= gk for any h∈G, where k∈ Z We say that g is a generator of G We denoted by g-g Example: group{1,-1,-i};×,1=,-1=i2,=, i and -i are generators of G. Z;+

2. Cyclic groups Definition 14: The group G is called a cyclic group if there exists gG such that h=gk for any hG , where kZ.We say that g is a generator of G. We denoted by G=(g). Example:group[{1,-1,i.-i};],1=i0 ,-1=i2 ,-i=i3 , i and –i are generators of G. [Z;+]

Example: Let the order of group g be n If there exists gEG such that g is of order n,then G is a cyclic group, and G is generated by g. Proof:

Example：Let the order of group G be n. If there exists gG such that g is of order n，then G is a cyclic group, and G is generated by g. Proof:

Theorem 6.15: Let G; be a cyclic group, and let g be a generator of G. Then the following results hold (1)If the order of g is infinite, then G; Z;+ (2)If the order of g is n, then G; =lZn; eI Proof:(1)G={gk∈Z}, q:G→>Z,(gk)=k (2)G={e,g,g2,g} q:G→>Zm,q(g)=k

Theorem 6.15: Let [G; *] be a cyclic group, and let g be a generator of G. Then the following results hold. (1)If the order of g is infinite, then [G;*] [Z;+] (2)If the order of g is n, then [G;*][ Zn ;] Proof:(1)G={gk |kZ}, :G→Z, (gk )=k (2)G={e,g,g2 ,g n-1 }, :G→Zn , (gk )=[k]

6.4 Subgroups, Normal subgroups and Quotient groups 6.4.1 Subgroups Definition 15: A subgroup ofa group(G; *)is a nonempty subset H ofG such that w as a group operation on H. Example: IZ; is a subgroup of the group R;升 G and e are called trivial subgroups ofG other subgroups are called proper subgroups of G

6.4 Subgroups, Normal subgroups and Quotient groups 6.4.1 Subgroups Definition 15: A subgroup of a group (G; *) is a nonempty subset H of G such that * is a group operation on H. Example : [Z;+] is a subgroup of the group [R; +]. G and {e} are called trivial subgroups of G, other subgroups are called proper subgroups of G

Theorem 6.16: Let G; be a group, and h be a nonempty subset of G. Then H is a subgroup of G, iff (1) for anyx,y∈H,xy∈H,;and (2) for anyuE,x1∈H Proof: IfH is a subgroup of G, then(1) and (2) hold O and(2) hold e∈H Associative law inverse

Theorem 6.16: Let [G;·] be a group, and H be a nonempty subset of G. Then H is a subgroup of G, iff (1) for any x, y H, x·yH; and (2) for any xH, x -1 H. Proof: If H is a subgroup of G, then (1) and (2) hold. (1) and (2) hold eH Associative Law inverse

Theorem 6.17: Let G; be a group, and h be a nonempty subset of G. Then H is a subgroup of G, iff a b-∈ H for va,b∈H Example: Let H, and H2: be subgroups of the group G;, Then H0H2; is also a subgroup of g;. IH1∪H2;] Example:eG={(x;y)xy∈ R with x≠0},and consider the binary operation o introduced by (x, y)o(zw)=(XZ, Xw +y for (x, y), (z W)EG. Let H=(, l yER) Is h a subgroup of g? Why?

Theorem 6.17: Let [G;·] be a group, and H be a nonempty subset of G. Then H is a subgroup of G, iff a·b-1H for a,b H. Example: Let [H1 ;·] and [H2 ;·] be subgroups of the group [G;·] ， Then [H1∩H2 ;·] is also a subgroup of [G;·] [H1∪H2 ;·] ? Example:Let G ={ (x; y)| x,yR with x 0} , and consider the binary operation ● introduced by (x, y) ● (z,w) = (xz, xw + y) for (x, y), (z, w) G. Let H ={(1, y)| yR}. Is H a subgroup of G? Why?

6.4.2 Coset Let H;* is a subgroup of the group IG;*. We define a relation R on G, So that arb iff for a*b1∈ H for va,b∈G.The relation is called congruence relation on the subgroup H; *. We denoted by a=b(modH)。 Theorem 6.18: Congruence relation on the subgroup H; of the group G is an equivalence relation

6.4.2 Coset Let [H;] is a subgroup of the group [G;]. We define a relation R on G, so that aRb iff for ab -1H for a,bG. The relation is called congruence relation on the subgroup [H;]. We denoted by ab(mod H)。 Theorem 6.18 ：Congruence relation on the subgroup [H;] of the group G is an equivalence relation

la=XXEG, and x=a(mod =XXEG, and x*a1∈H} Let h=x*a-I. Then x=h*a, Thus a]={h*ah∈H Ha=h*aheh is called right coset of the subgroup h aH=fa*h heH is called left coset of the subgroup H Let [ H; be a subgroup of the group g;* anda∈G.Then (1)b∈ Ha iff b*a∈H (2 beah iff a1*b∈H

[a]={x|xG, and xa(mod H)}={x|xG, and xa -1H} Let h=xa -1 . Then x=ha，Thus [a]={ha|hH} Ha={ha|hH} is called right coset of the subgroup H aH={ah|hH} is called left coset of the subgroup H Let [H;] be a subgroup of the group [G;], and aG. Then (1)bHa iff ba -1H (2)baH iff a-1bH