refer 8.2

## Groups

### Definition 8.2.1 Group

A group is a set of elements G together with an operation ◦ which combines two elements of G. A group has the following properties.

Note:

in cryptography we use both multiplicative groups, i.e., the operation “◦” denotes multiplication, and additive groups where “◦” denotes addition. The latter notation is used for elliptic curves as we’ll see later. Roughly speaking, a group is set with one operation and the corresponding inverse operation. If the operation is called addition, the inverse operation is subtraction; if the operation is multiplication, the inverse operation is division (or multiplication with the inverse element).

#### Closure

The group operation ◦ is closed. That is, for all a,b,∈ G, it holds that a ◦ b = c ∈ G.

#### Associative

The group operation is associative 结合律 . That is, a◦(b◦c) = (a◦b)◦c for all a,b,c ∈ G.

Note: associative is non trivial

x1 x2 x3
x1   x1◦x2
x2     x2◦x3
x3

(x1◦x2)◦x3 根据闭合属性，x1◦x2 的值肯定是属于G也就是x1/x2/x3其中一个，所以 (x1◦x2)◦x3的值就落在最后一列

x1◦(x2◦x3) 同理，(x2◦x3) 的值也是属于G也就是x1/x2/x3其中一个，所以其值落在第一行

i(identity):

a->a

b->b

t(transform):

a->b

b->a

i◦t是指在t的基础上进行i操作：

a->b ->b

b->a ->a

=>

a->b

b->a

i t
i i t
t t i

i◦t◦t = (i◦t)◦t = i◦(t◦t)

#### Neutrual/Identity element

There is an element 1 ∈ G, called the neutral element (or identity element), such that a ◦ 1 = 1 ◦ a = a for all a ∈ G.

#### Inverse

For each a ∈ G there exists an element a−1 ∈ G, called the inverse of a, such that a ◦ a−1 = a−1 ◦ a = 1.

#### Commutative(Abelian Group)

A group G is abelian (or commutative) 交换律 if, furthermore, a ◦ b = b ◦ a for all a,b ∈ G.

take above example, commutative means that in the table it’s symmetric down the diagonal line

### Example: To illustrate the definition of groups

• (Z,+) is a group, i.e., the set of integers Z = {. . . ,−2,−1,0,1,2, . . .} together with the usual addition forms an abelian group, where e = 0 is the identity element and −a is the inverse of an element a ∈ Z.

• 加法模

The set of integers Zm = {-m+1, . . . , -1,0,1, . . . ,m−1} and the operation addition modulo m form a group with the neutral element 0. Every element a has an inverse −a such that a+(−a) =0 mod m.

• 乘法模

Note that this set Zm does not form a group with the operation multiplication because most elements a do not have an inverse such that aa−1 =1 mod m.

• (Z without 0, ·) is not a group, i.e., the set of integers Z (without the element 0) and the usual multiplication does not form a group since there exists no inverse a−1for an element a ∈ Z with the exception of the elements −1 and 1. -1+1=0而0不存在，破坏了group 闭合的定义

• (C, ·) is a group, i.e., the set of complex numbers u+iv with u,v ∈ R and i2 =−1 together with the complex multiplication defined by (u1+iv1) · (u2+iv2) = (u1u2−v1v2)+i(u1v2+v1u2) forms an abelian group. The identity element of this group is e = 1, and the inverse a−1 of an element a = u+iv ∈ C is given by a−1 = (u−iv)/(u2+v2).

• (Zn*, ·): is defined as the set of positive integers smaller than n which are relatively prime to n. Thus,

the cardinality of  Zn*equals Euler’s phi function evaluated for n, i.e.,

 Zn* =Φ(n). For instance,

the group Z9* has a cardinality ofΦ(9)=32−31 =6. the group consist of the six elements {1,2,4,5,7,8}.

However, all of these groups do not play a significant role in cryptography because we need groups with a finite number of elements. Let us now consider the group Zn which is very important for many cryptographic schemes such as：

• DHKE,

• Elgamal encryption,
• digital signature algorithm
• and many others.

### 构造Group(Set=>Group)

n ∈ N = {1, 2, 3, 4, 5, 6, ……….}

Set集合 S1 S2 …….. Sn

n=1，S1 = {1}

n=2，S2 = {1,2}

#### 构造1：Set Permutation (Symmetric Group)

n=2

i(identity):

1->1

2->2

t(transform):

1->2

2->1

i◦t是指在t的基础上进行i操作：

1->2 ->2

2->1 ->1

=>

1->2

2->1

i t
i i t
t t i

#### 构造2：模运算 Theorem 8.2.1

The set Zn which consists of all integers i=0,1, . . . ,n−1 for which gcd(i,n) = 1 forms an abelian group under multiplication modulo n. The identity element is e = 1.

Example 8.3. If we choose n = 9, Zn consists of the elements {1,2,4,5,7,8}.

Multiplication table for Z9

× mod 9 1 2 4 5 7 8
1 1 2 4 5 7 8
2 2 4 8 1 5 7
4 4 8 7 2 1 5
5 5 1 2 7 8 4
7 7 5 1 8 4 2
8 8 7 5 4 2 1

S={1 2 4 5 7 8}

permutation1: S*1 mod 9 结果映射 1 2 4 5 7 8

permutation2: S*2 mod 9 结果映射 2 4 8 1 5 7

。。。。。

#### Group的序 Size/Order

1,2,3…….n 映射到 1,2,3…….n

 ~~Sn的序 Order = Sn = n(n-1)(n-2)…..1 = n!~~

## Symmetric Groups

In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operations is the composition of functions. In particular, the finite symmetric group Sn defined over a finite set of n symbols consists of the permutations that can be performed on the n symbols.

S3

i t12 t13 t23 σ σ2
1->1
2->2
3->3
1->2
2->1
3->3
1->3
2->2
3->1
1->1
2->3
3->2
1->2
2->3
3->1
1->3
2->1
3->2
i t12 t13 t23 σ σ2
i i t12 t12 t23 σ σ2
t12 t12   σ2
t13 t13 σ
t23 t23
σ σ
σ2 σ2

t12 ◦ t13 = σ2

t13 ◦ t12 = σ

## Cyclic Groups

Definition 8.2.3 Order of an element The order ord(a) of an element a of a group (G,◦) is the smallest positive integer k such that ak = a ◦ a ◦. . . ◦ a (k times)= 1, where 1 is the identity element of G.

Definition 8.2.4 Cyclic Group A group G which contains an element α with maximum order ord(α) = |G| is said to be cyclic. Elements with maximum order are called primitive elements or generators.

n ∈ N = {1, 2, 3, 4, 5, 6, ……….n}

1->1 2->2 ………….n->n 用i表示

1->2 2->3 ……….n->1 用σ 表示

1->3 2->4………..n-1->1 n->2 用σ2 表示

……

1->n 2->1 ……….n->n-1 用σn-1 表示

1) closure, x,y ∈ Cn x◦y ∈ Cn

2) Associativity

3) Identity: i 旋转0次

4) Inverse ∀ g ∈ Cn, ∃ g-1∈ Cn, s.t. g◦g-1=g-1◦g=i

5) 并且还满足commutative，即Cyclic Group必然是Abelian Group

 容易得到， Cn 的序=n 也就是所有的Cyclic Permutation总共有n种可能，可以联想之所以set Permutation是n阶乘，而这里是n，主要是这里1 2 3。。。。n这些元素是联动的，也就是当1旋转到了2，2必然对应3，而set Permutation中可以自由选择

C4

i σ σ2 σ3
1->1
2->2
3->3
4->4
1->2
2->3
3->4
4->1
1->3
2->4
3->1
4->2
1->4
2->1
3->2
4->3
i σ σ2 σ3
i i σ σ2 σ3
σ σ σ2 σ3 i
σ2 σ2 σ3 i σ
σ3 σ3 i σ σ2

example 2: a = 3 is not a primitive element of Z11* = {1,2,3,4,5,6,7,8,9,10}.,

a = 3 only generate partial of Z11* {3,9,5,4,1}

a1 = 3 a2 = a · a = 3 · 3 = 9 a3 = a2 · a = 9 · 3 = 27 ≡ 5 mod 11 a4 = a3 · a = 5 · 3 = 15 ≡ 4 mod 11 a5 = a4 · a = 4 · 3 = 12 ≡ 1 mod 11

We see that from this point on, the powers of a run through the sequence {3,9,5,4,1} indefinitely.

a6 = a5 · a ≡ 1 · a ≡ 3 mod 11 a7 = a5 · a2 ≡ 1 · a2 ≡ 9 mod 11 a8 = a5 · a3 ≡ 1 · a3 ≡ 5 mod 11 a9 = a5 · a4 ≡ 1 · a4≡ 4 mod 11 a10 = a5 · a5 ≡ 1 · 1 ≡ 1 mod 11 a11 = a10 · a ≡ 1 · a ≡ 3 mod 11

example 3: a = 2 is a primitive element of Z11* = {1,2,3,4,5,6,7,8,9,10}.,

a = 2 generate the whole Z11*

a = 2 a6 ≡ 9 mod 11 a2 = 4 a7 ≡ 7 mod 11 a3 = 8 a8 ≡ 3 mod 11 a4 ≡ 5 mod 11 a9≡ 6 mod 11 a5 ≡ 10 mod 11 a10 ≡ 1 mod 11

 From the last result it follows that ord(a) = 10 = Z11* .

This implies that a = 2 is a primitive element and Z11* is cyclic

Theorem 8.2.4 Let G be a finite cyclic group. Then it holds that

1.  The number of primitive elements of G is Φ( G ).
2.  If G is prime, then all elements a <> 1 ∈ G are primitive.
 很容易理解，G是Cyclic group，说明存在一个Cyclic set Permutation，由后面的Cayley’s theorem可以知道每个元素本身就代表一种Cyclic set Permutation，比如1代表G->1G即旋转0度，2代表G->2G即旋转360/ G 度，3代表G->3G即旋转2*360/ G 度，依次类推，总之每个元素都代表旋转某个角度，但是:

Theorem 8.2.5 Cyclic Subgroup Theorem Let (G,◦) be a cyclic group. Then every element a ∈ G withord(a) = s is the primitive element of a cyclic subgroup with s elements.

 Z11* ={x mod 11 x=1,2….10} ,

Z11* = {1,2,3,4,5,6,7,8,9,10}.

 Z11* = 10 不是prime，Φ(10) = (5−1)(2−1) = 4, 刚好对应下面只有2 6 7 8 可以生成整个group

x=1, <x> ={1} ord(1) =1

x=2, <x> ={1,2,3,4,5,6,7,8,9,10} ord(2) =10

x=3, <x> ={3,9,5,4,1} ord(3) =5

x=4, <x> ={4,5,9,3,1} ord(4) =5

x=5, <x> ={5,3,4,9,1} ord(5) =5

x=6, <x> ={1,2,3,4,5,6,7,8,9,10} ord(6) =10

x=7, <x> ={1,2,3,4,5,6,7,8,9,10} ord(7) =10

x=8, <x> ={1,2,3,4,5,6,7,8,9,10} ord(8) =10

x=9, <x> ={9,4,3,5,1} ord(9) =5

x=10, <x> ={10,1} ord(10) =2

## Dihedral Groups

n ∈ N = {1, 2, 3, 4, 5, 6, ……….n}

 Dn =n(cyclic permutation)+n(flipping) = 2n

D1=S1, D2=S2, D3=S3

Dn不是abelian group

## Klein 4 Group

n {1, 2, 3, 4}

V = Klein 4 Group = {i, t12, t34, D}4

i t12 t34 D
1->1
2->2
3->3
4->4
1->2
2->1
3->3
4->4
1->1
2->2
3->4
4->3
1->2
2->1
3->4
4->3
i t12 t34 D
i i t12 t34 D
t12 t12 i D t34
t34 t34 D i t12
D D t34 t12 i

## Group Isomorphisms 同构

G = S2 = {i, t}

G’= {+1, -1}

G和G’ 两者除了符号不同，性质相同，可以relabeling

i<->+1

t<->-1

G&G’ are isomorphic if exists:

φ: G<->G’ φ is bijective

for ∀ x,y ∈ G, φ(x ◦ y) = φ(x) ◦ φ(y)

G y ….

x   x ◦ y

G’ φ(y)

φ(x)   φ(x) ◦ φ(y)

Isomorphism Class:

taking all groups that are isomorphic to one another and sticking them into a great big class, all of them are just the equivalent algebraic structure but with difference symbols used to denote the different elements of the group

G:

(R, +) 实数是Filed，不过这里只考虑其在加法结构上的Abelian Group结构

G’:

 (R+, *) R+ = {x ∈ R x > 0 } 正实数在乘法结构上是Abelian Group

φ: G->G’

x,y ∈ G, ◦ 是 +， x ◦ y = x + y

φ(x),φ(y) ∈ G’, ◦ 是 *, φ(x) = ex, φ(y) = ey

for ∀ x,y ∈ G,

φ(x ◦ y) = φ(x + y) = ex+y= exey = φ(x)φ(y) = φ(x) ◦ φ(y)

## Subgroups

H ⊂ G 或 H < G , every subgroup is a subset

closure for H suddenly becomes non-trivial, because it’s hard to say that for ∀ x,y ∈ H, x ◦ y also ∈ H not outside of H

H需要包含G的identity

two trivial sub group：identity & the entire group

S3= { i, t12, t13, t23, σ, σ2 }

C3 = { i, σ, σ2 }

C3 ⊂ S3

H = { i, t12 } (isomorphic to S2)

H ⊂ S3

Integer Z= {0, 1, -1, 2, -2, ……….}

 aZ = {za z ∈ Z } = { 0, a, -a, 2a, -2a, …….}

aZ ⊂ Z

0Z = {0} 1Z = Z 刚好是Z的two trivia sub group

closure： 利用ring的分配律（因为Integer是ring）：za+z’a = (z+z’)a = z’‘a, z’‘=z+z’ ∈ Z, z’‘a ∈ aZ

b存在inverse -b，b+b=2b…………从而构造出

{0, b, -b, 2b, -2b, ……} 如果任何一个元素不存在与H中，那么H就不是闭合的，就不是group，所以bZ ⊂ H

let a ∈ H but not in bZ, so:

if a<b, contradict to b is the smallest integers;

if a>b, then a = zb + r, z ∈ Z and b>r>0 (if r=b then a=(z+1)b, contradict to a not in bz)

=> r = a + (-zb) , because a ∈ H, -zb also ∈ H, so we have r ∈ H, contradict to b is the smallest integers

aZ isomorphic to Z

 aZ = {za z ∈ Z }

φ: aZ -> Z

for ∀ x,y ∈ G, φ(x) = x/a

φ(x ◦ y) = φ(x + y) = φ(za+z’a) = φ((z+z’)a) = z+z’

φ(x) ◦ φ(y) = φ(x) + φ(y) = φ(za) + φ(z’a) = z+z’

H1,H2 < G ,H1 ∩ H2 < G

 H1 ∩ H2 = { g ∈ G g∈H1,g∈H2 }

## Cyclic Groups and subgroups

### finite & infinite Cyclic group

n ∈ N = {1, 2, 3, 4, 5, 6, ……….n}

Cyclic Permutation就是rotate旋转圆盘（每次旋转360/n），所以

1->1 2->2 ………….n->n 用i表示

1->2 2->3 ……….n->1 用σ 表示

1->3 2->4………..n-1->1 n->2 用σ2 表示

……

1->n 2->1 ……….n->n-1 用σn-1 表示

1->2 2->3 ………. 由于是整个自然数，无法得到自然数的最后一个数让其指向1，所以无法实现Permutation，

….. -3->-2 -2->-1 -1->0 0->1 1->2 2->3 …………….. 现在随便找一个Integer 都能找到其对应的map

….-2->-3 -1->-2 0->-1 1->0 2->1 3->2…………

identity：0

{ 0, 1, -1, 2, -2,…… } 神奇的发现产生的这个infinite Cyclic group跟我们考虑的整个Integer Z是完全一样的

### Cyclic Subgroup

for cyclic group G, x ∈ G (x is not identity element), <x> called Cyclic subgroup generated by x

<x> = {e, x, x2,x3…………. x-1, x-2……} 根据group的性质，肯定包含identity,e= x0，然后根据闭合性质，x跟自己compose成 x2（参考前面Cyclic Permutation的例子，相当于旋转两次），接着生成 x3等，并且每个元素都存在逆

closure 闭合：∀ a,b ∈ Z (<x> 元素的次幂是Integer)

x ◦ xb = xa+b

xa = x ◦ x ……..◦ x 表示x compose自己a次，所以xa ◦ xb就是x compose with自己a+b次，所以是满足闭合

inverse显然存在，

<2> = { 0, 2, 4, 6…….., -2, -4, -6……….} = 2Z（前面subgroup举例的aZ）

<x> isomorphic to (Z,+)

<x> = {e, x, x2,x3…………. x-1, x-2……}

φ: <x> ->(Z,+) , φ(xn) = n

for ∀ a,b ∈ <x>,

φ(a ◦ b) = φ(xm ◦ xn) = φ(xm+n) = m+n

φ(a) ◦ φ(b) = φ(xm) + φ(xn) = m + n φ(a ◦ b)= φ(a) ◦ φ(b) 得证

finite Group

<x> = {e, x, x2,x3………….}

if <x> is finite group, then must exist m∈N is the smallest that give an entry that already had(start cyclic), so that<x> = {e, x, x2, x3, ……xm-1 }, and it must be xm = e

Prove:

suppose xm = xn ∈N and n<m

(x-1)n xm = (x-1)n xn

=> xm-n = e this contradict to m is the smallest that give an entry that already had

closure: xa ◦ xb = xa+b if a+b<m显然属于<x>, 等于m则 xm = e ，大于m比如介于(m,2m)则 xa ◦ xb = xm(xr)=xr r<m

inverse: 根据 xm = e => x1 ◦ xm-1 = e 找到complementary power即可

Theorem 8.2.7 Let G be a finite cyclic group of order n and let α be a generator of G. Then for every integer k that divides n there exists exactly one cyclic subgroup H of G of order k. This subgroup is generated by αn/k. H consists exactly of the elements a ∈ G which satisfy the condition ak = 1. There are no other subgroups.

 这个太容易证明了，首先cyclic group G =n， α 是generator，因此 an = 1.

cyclic subgroup H of G of order k，assume generator为 b，则 bk = 1.

b属于G，因此b=ax => (ax)k = 1 => (ax)k = an => x=n/k

Example 8.10. We again consider the cyclic group Z11*.We saw earlier that α = 8 is a primitive element in the group. If we want to have a generator β for the subgroup of order 2, we compute: β =αn/k = 810/2 = 85 = 32768 ≡ 10 mod 11. We can now verify that the element 10 in fact generates the subgroup with two elements: β1 = 10, β2 = 100 ≡ 1 mod 11, β3 ≡ 10 mod 11, etc. Remark: Of course, there are smarter ways of computing 85 mod 11, e.g., through 85 = 82 82 8 ≡ (−2)(−2)8 ≡ 32 ≡ 10 mod 11.

Cyclic group both the finite and infinite cyclic groups what they contain basically is they need to contain an element x ∈ C such that the subgroup group generated by x <x> is actually equal to the entire group

<1> = { 0, +1, +2, +3……., -1, -2, -3,……….}

## Cayley’s theorem

fundamentally the group is a set of symbols with composition law defined on it, so that raises an interesting question:

we know we can use the concept of set permutation of some sets to be able to build a group but is it the case that if you have a group, is it always some set for which you can view the elements of the group as representing set permutations of that set, basically this is the great motivation question for cayley’s theorem, the answer is yes

### 引入

so the questions now becomes is it the case that we can always think of a group as being a set of symbols where these symbols are representing set permutations of some set.

G={……..}

a ∈ G,

 aG = {a◦g g ∈ G}
<—G—> every elements in G

a a◦g
….
 Ga = {g◦a g ∈ G}
a
<–   g◦a
G every elements in G   g◦a
–>   g◦a

for aG and Ga, every elements appear once and only once,

Prove:

assume g<>g’ but a◦g = a◦g’

<—   G every elements in G —>

a   a◦g a◦g’
….

=> a-1◦a◦g = a-1◦a◦g’

=> g = g’ contradict to g<>g’

for 任意 g ∈ G，只要可以找到ax=g, x ∈ G不就可以了么

=> x=a-1g，所以对于任意g都可以找到x=a-1g 从而让ax=g 得证

### 凱萊定理

In group theory, Cayley’s theorem, named in honour of Arthur Cayley, states that every group G is isomorphic to a subgroup of the symmetric group acting on G. This can be understood as an example of the group action of G on the elements of G. The theorem can be obtained by explicitly constructing the representation within the representation of the symmetric group of permutation matrices, which is sometimes known as the regular representation.

A permutation of a set G is any bijective function taking G onto G. The set of all permutations of G forms a group under function composition, called the symmetric group on G, and written as Sym(G).

for group G={e…..}

let’s just take the the symbols from the Group G (not taking the composition law, only the symbols), so we got a Set

S={e……}

this is the SET that we’re going to think of every element of the group as representing a set permutation of and the composition law is then going to represent the composition of those set permutations

take any g ∈ S, a ∈ G,

set permutation is bijective map from the SET to itself,

we define **set permutation: a(g) **

and because g ∈ S, and it’s the same symbol from group G, so we can have:

a(g) = a ◦ g，前面已经证明了 aG=G，every elements appear once and only once，所以必然是双射

then we can define a new composition law based on this set permutation, it will be the same composition as the Group G

<———G———->
e <———G———->

a <———aG———->

eG 就像之前set Permutation的i

aG 就像之前set Permutation的其他双射 比如之前研究过的t12 ，σ

(a◦b)(g) = a(b(g))

(a◦b)(g) = a(b(g)) 不成立，因为

(a◦b)(g) = g◦(a◦b) 而 a(b(g)) = a(g◦b) = (g◦b)◦a = g◦(b◦a) 但是我们知道对于group a◦b并不一定等于b◦a，只有abelian group才有这个属性

## Parity of a permutation

t12 (1 2) t123 (1 2 3) t132 (1 3 2) t13,24 (1 3)(2 4) (1 3 4)(2 5) σ2
1->2
2->1
3->3
4->4
1->2
2->3
3->1
4->4
1->3
2->1
3->2
4->4
1->3
2->4
3->1
4->2
1->3
2->5
3->4
4->1
5->2
1->3
2->1
3->2
4->4

t12 (1 2) :

​ 2-cycle 意思是3 4不变，单看1和2就是类似Cyclic Permutation的两个元素的cycle rotate

t123 (1 2 3)

​ 3-cycle 同理，4不变，此时是按 1 2 3的顺序进行的Cyclic Permutation的三个元素的一次rotate

t132 (1 3 2)

​ 3-cycle 同理，只不过顺序变成了 1 3 2 进行的一次rotate

t13,24 (1 3)(2 4)

​ two 2-cycle

(1 2 3)=(1 3)(1 2)

(1 2)(1 2) 这种完全一样的就互相抵消

(1 3 2) = (2 3)(1 2) = (1 3)( 2 3) 这种是有一个重合的就有多种写法

(1 2)(3 4)=(3 4)(1 2) 这种没有重合的就满足communitative交换

(1 3)(1 2) is the inverse of (1 2)(1 3)

can only have even or odd decompositions

(1 2)(1 3)(1 3)(1 2) = e 很简单 (1 3)(1 3) = e 抵消

a = tn tn-1…..t1

a-1 = t1t2…..tn

a = tn……….t1 n = even

a = sm……..s1 m = odd

a-1 = s1…..sm

a-1 a = s1……smtn……..t1 =e identity必须是even number of transpositions，如果是odd无法互相抵消

## Group Homomorphisms 同态

φ: G->G’ φ doesn’t have to be bijective

for ∀ x,y ∈ G, φ(x ◦ y) = φ(x) ◦ φ(y)

1) 不需要满足 surjective 满射，即：

for ∀ g’ ∈ G’ ∃ g ∈ G, s.t. φ(g) = g’

2）不需要满足injective 单射

 for ∀ g’ ∈ Im(φ) Im(φ)={φ(g) g ∈ G},

∃ only one g ∈ G, s.t. φ(g) = g’

Prove: φ(eG) = eG’ eG代表G的e eG’是G’的e

we know that:

x ∈ G, x ◦ x = x => x=e only solution for x compose with itself equal to itself is the identity

so, to prove φ(eG) = eG’ we just need to prove that φ(eG) ◦ φ(eG) = eG’

φ(eG) ◦ φ(eG) = φ(eG ◦ eG) and eG ◦ eG = eG

=> φ(eG) ◦ φ(eG) = φ(eG) and because φ(eG) is element in G’,

so we got the only solution is eG’

Prove:

a, a-1 ∈ G, (a, a-1 can be the same element)

=> φ(a) inverse is φ(a-1)

or write as: φ(a-1) = InverseOf(φ(a)) 或写作 (φ(a))-1

φ(a) ◦ φ(a-1) = φ(a ◦ a-1) = φ(eG) = eG’

Prove:

 **Im(φ) < G’ Im(φ)={φ(g) g ∈ G}** , means that we can reduce a non-surjective homomorphism to surjective homomorphism

if the homomorphisms is surjective, then Im(φ) = G’ , else Im(φ) is a proper subset of G’,

so we konw Im(φ) is a subset of G’, how to prove Im(φ) is a subgroup of G’,仍然是看group的性质：

1) closure ∀ g1,g2 ∈ Im(φ) , g1◦ g2 ∈ Im(φ)

prove: if g1,g2 ∈ Im(φ), means exist φ(a)=g1, φ(b)=g2 (a b can be equal, hormomorphism no need to be injective)

g1◦ g2 = φ(a) ◦ φ(b) = φ(a ◦ b) ∈ Im(φ) 得证

2) associativity 继承的性质

3) Identity

φ(eG) = eG’ eG’ ∈ Im(φ)

4) Inverses a’ ∈ Im(φ) , (a’)-1 ∈ Im(φ)

we konw (a’)-1 = φ(a-1) so we got (a’)-1 ∈ Im(φ) 得证

there is no point in considering non-subjective homomorphisms, because you can always reduce it into thining in terms of a subjective homomorphims,

Example:

φ: (Z, +) -> S2

Z={0,1,-1,2,-2………}

S2={+1,-1} +1代表identity，-1代表transpose

φ(x)= +1 if x is even =-1 if x is odd

Prove: (Z, +) -> S2 ∀ a,b ∈ Z φ(a+b)=φ(a)φ(b)

case 1: a,b are even, φ(a)=φ(b)=1, a+b is even , φ(a+b)=1=φ(a)φ(b) 其他情况同理

 Kernel(φ) = { g ∈ G φ(g)=eG’}

if it’s isomorphism,means it’s bijective, then eG is the only element

Prove: Kernel(φ) < G subgroup:

1) closure, any a,b ∈ kernel(φ), φ(a◦b)=eG’ φ(a)◦φ(b)=eG’ ◦ eG’ = eG’ 得证

2) associativity 和 identity都很显然

3) Inverse a ∈ kernel(φ) prove a-1 ∈ kernel(φ) 即证明 φ(a-1)=eG’ :

φ(a-1) = InverseOf(φ(a)) 或写作 (φ(a) )-1 = InverseOf(eG’) =eG’

conjugate element

a,g ∈ G, the conjugate of g by a: aga-1

if G is abelian, aga-1 = aa-1g = g

### Normal subgroup 正规子群:

H<G, ∀ h ∈ H ∀ g ∈ G, ghg-1∈ H, means that H has to be stable under conjugation by any element in G

Prove: H= Kernel(φ) ∀ h ∈ Kernel(φ), ∀ g ∈ G, ghg-1 ∈ Kernel(φ)，即证明 φ(ghg-1) = eG’

φ(ghg-1) = φ(gh) ◦ φ(g-1) = φ(g) ◦ φ(h) ◦ φ(g-1) =φ(g) ◦ eG’◦ φ(g-1) =φ(g) ◦ φ(g-1)

φ(g) ◦ φ(g-1) = φ(g ◦ g-1) = φ(eG) = eG’

## Cosets + Lagranges

G={……..}

a ∈ G,

 aG = {a◦g g ∈ G}
 Ga = {g◦a g ∈ G}

aG == Ga == G, every elements in the group appear once and only once

Cosets:

a ∈ G, subgroup H<G ,

 left coset of H under a: aH = {a◦h h ∈ H}

right coset of H under a: Ha

a ∈ aH, a ∈ Ha， 因为subgroup H必然包含identity e，left cosets和right cosets必然不包含identity e，因为下面会证明cosets跟H元素完全不同，所以叫cosets而不是group

if a ∈ H，跟前面的Cayley’s theorem讲的内容一样，aH=Ha=H (aH=Ha 还有几种情况：G是abelian group；或者H是normal subgroup)

if a ∉ H, aH Ha are free of H (distinct from H), Prove by contradiction:

 aH = {a◦h h ∈ H} , h’ = a◦h, assume h’ ∈ H

h’ = a◦h=> h’◦h-1 = a , h-1 ∈ H (h ∈ group H, exist inverse), so h’◦h-1 ∈ H (closure), so a ∈ H, contradict to a ∉ H得证

note: 当然很容易知道，aH的元素不仅distinct from H，各自也是不同的，也是利用反证，比如假设存在不同的h1 h2使得ah1=ah2，两边取a的逆就得到反证，因此aH的元素个数跟H的元素个数相同，即order相同

if H is a Normal subgroup of G: ∀ a ∈ G, left cosets equal to right cosets:aH=Ha，即 aH ⊂ Ha AND Ha ⊂ aH

Prove: a◦h ∈ aH, h ∈ H, to show ∃ h’ ∈ H, s.t. h’a = ah => h’ = aha-1 ,

because H is a normal subgroup of G, by the definition of normal subgroup:

H<G, ∀ h ∈ H ∀ g ∈ G, ghg-1∈ H, means that H has to be stable under conjugation by any element in G

so h’ = aha-1 is true 得证

Properties of Coset

a◦h ∈ aH, (a◦h)H = aH

 (a◦h)H = {(a◦h)◦h’ h’ ∈ H} = {a◦(h◦h’) h’ ∈ H} 再次使用 Cayley’s theorem，{h◦h’ h’ ∈ H} = hH =H
 => (a◦h)H ={a◦(h◦h’) h’ ∈ H} ={a◦h’’ h’’ ∈ H}

Example:

G=(Z, +)

 subgroup一节讲过 H=5Z={ 5z z∈Z} = {0, 5, -5, 10, -10…….}

because (Z, +) is abelian group, left coset is the same as right coset

a = 1

aH = 1+H = 1+5Z = {1, 6, -4, 11, -9, ……..}

Partition of set, split SET into N partition, P = { subset1, subset2, …..,subsetN}

H<G,

if H not G, then there must be some elements outside of H but inside of G,

a ∉ H, 从前面结论知道 element in aH totally distinct from H, then:

H union aH 可能等于 G，否则就存在

b ∉ H union aH，that bH totally distinct from (H union aH)，我们已经知道同理aH，bH totally distinct from H，但是怎么证明 bH totally distinct from aH，prove by contradiction:

 aH = {a◦h h ∈ H}
 bH = {b◦h h ∈ H}

assume exist b◦h1 = a◦h2, h1,h2∈H

=> b = a◦h2◦h1-1 ,h2◦h1-1 ∈ H, so b ∈ aH，跟前面的前提b ∉ H union aH矛盾，得证

 如果H是finite group，H的order H =m, 即H有m个元素，那么所有的cosets都跟H有相同的order，因为all elements in aH are distinct

### Lagranges Theorem

G is finite group / has an order(number of elements in group)

 G = n H n ∈ N,

OR |H| must be divide by |G|

n实际上就是前面的 Partition of G = { H, aH,bH, ………} partition的数量，因为前面知道aH，bH，nH都跟H的order一样

example：

 G = Prime number=P = 2, 3, 5, 7…………
 其 subgroup H =1 or G

take some non-identity element x from G, x≠ eG，前面讲的Cyclic subgroup提到的，

infinite Cyclic group: <x> = {e, x, x2,x3…………. x-1, x-2……}

finite cyclic group: <x> = {e, x, x2, x3, ……xm-1 } xm = e

 对于 order为prime number=P 的finite group G来说，从non-identity element x生成的finite Cyclic group = {e, x, x2, x3, ……xm-1 } xm = e，m就是G的order = P，因为我们前面有结论其 subgroup H =1 or G ，然后我们取出的是non-identity element x，所以 的 order就是等于 G ，所以m=P= G ,xP=e (xP=e is a generalization of Fermat’s Little Theorem for all cyclic groups)，换句话说就是non-identity element x生成的finite Cyclic group 就是整个 G，所以G is isomorphic to a finite cyclic group 即 CP

Note: 网络上很多说法不严谨，比如直接说素数阶群必为循环群 https://blog.csdn.net/qq_25847123/article/details/100572099

 Z11* ={x mod 11 x=1,2….10} ,

Z11* = {1,2,3,4,5,6,7,8,9,10}.

 Z11* = 10

x=1, <x> ={1} ord(1) =1

x=2, <x> ={1,2,3,4,5,6,7,8,9,10} ord(2) =10

x=3, <x> ={3,9,5,4,1} ord(3) =5

x=4, <x> ={4,5,9,3,1} ord(4) =5

x=5, <x> ={5,3,4,9,1} ord(5) =5

x=6, <x> ={1,2,3,4,5,6,7,8,9,10} ord(6) =10

x=7, <x> ={1,2,3,4,5,6,7,8,9,10} ord(7) =10

x=8, <x> ={1,2,3,4,5,6,7,8,9,10} ord(8) =10

x=9, <x> ={9,4,3,5,1} ord(9) =5

x=10, <x> ={10,1} ord(10) =2

## Quotient Groups

N < G (N is a subgroup of G and N is a normal subgroup 正规子群，conjunction stable：

∀ n ∈ N ∀ g ∈ G gng-1 ∈ N),

we call G/N: Quotient Group G over N or Group G module group N

if H is a Normal subgroup of G: ∀ a ∈ G, left cosets equal to right cosets: aN=Na，意味着我们对large group G进行 Partition分区的话，就只有一种方式或一种结果，因为left cosets和right cosets相等，

G/N={ {N}, {aN}, {bN}, ….. }

G/N = {e¯, a¯, b¯………..}

a¯ ◦ b¯ 相当于两个cosets进行组合计算，这里的◦定义为：

a¯ ◦ b¯ = a ◦ b，变回了G这个group元素a b的composition

a¯ ◦ b¯ = a◦n ◦ b◦n’ ，现在要证明a◦n ◦ b◦n’ 一定是属于(a ◦ b)¯ 即a ◦ b的cosets {abN}，再转换一下就是说一定存在 n’’ ∈ N，从而让

a◦n ◦ b◦n’= a◦b◦n’’

1. closure

很显然，我们定义的composition就是说两个cosets运算得到另一个cosets，G是由所有cosets partition组合的，所以闭合

2. associativity

也挺显然的，因为根据定义，本来就是借助G的compose，写出来就是：

(a¯ ◦ b¯)◦ c¯ = (a ◦ b)¯◦ c¯ = ((a ◦ b)◦ c)¯

a¯ ◦( b¯◦ c¯) =a¯ ◦ (b ◦ c)¯ = (a ◦ (b◦ c))¯

((a ◦ b)◦ c = a ◦ (b◦ c) 所以对应的cosets当然也是一样的了，即((a ◦ b)◦ c)¯= (a ◦ (b◦ c))¯，所以

(a¯ ◦ b¯)◦ c¯ = a¯ ◦( b¯◦ c¯)

3. identity

e¯ ◦ a¯ = a¯ ◦ e¯ = a¯

同样是利用定义

e¯ ◦ a¯ = (e ◦ a)¯ = a¯ 同理，得证

4. inverses exists

∀ a¯ ∈ G/N，∃ a¯-1 s.t a¯ ◦ a¯-1 = a¯-1◦ a¯ =e¯

仍然是利用定义，对于a¯即aN来说，representative代表性的元素取 a◦e即a，因为

a∈ G，所以a◦a-1 = a-1◦a =e ，自然我们根据定义

a¯ ◦ a-1¯ = (a◦a-1)¯ = e¯

当然 a-1 可能跟a在同一个cosets中，即a¯ 自己是自己的inverse，为什么取representative a◦e即a，a¯ 中其他元素呢，我们前面已经证明过了how do we know whichever representative we take within these cosets doesn’t matter:

试着证明下吧

a◦n1 ◦ b◦n2 = a◦b◦b-1◦n1 ◦ b◦n2 = a◦b◦(b-1◦n1 ◦ b)◦n2，而 b-1◦n ◦ b 对于normal group N来说就等于another element in N 比如n3,

所以如果b是a的逆，则a◦b=e，从而a◦n1 ◦ b◦n2 = a◦b◦(b-1◦n1 ◦ b)◦n2 = e◦n3◦n2 = n4，n4∈N即 n4∈ e¯ 得证

### 例子 Z/3Z

Integer Z= {0, 1, -1, 2, -2, ……….}

 3Z = {3z z ∈ Z } = { 0, 3, -3, 6, -6, …….} = 0¯
 1+3Z ={1+x x ∈ 3Z } = { 1, 4, -2, 7, -5, …….} = 1¯
 2+3Z ={2+x x ∈ 3Z } = { 2, 5, -1, 8, -4, …….} = 2¯

note: 画一个数轴比较容易理解

Z/3Z = { 0¯, 1¯, 2¯}

Z/3Z isomorphic to C3，根据前面 Lagrange theorem知道，Z/3Z的order=3 prime，因此由non-identity元素生成的finite cyclic group，比如<1¯> 首先包含identity 0¯和1¯，然后1¯+1¯=2¯， 1¯+1¯+1¯=0¯终止，因此<1¯> = { 0¯, 1¯, 2¯}

### 1st isomorphism theorem

in previous section we know that there is no point in considering non-subjective homomorphisms, because you can always reduce it into thining in terms of a subjective homomorphims:

φ: G->G’ (G’ here must be subjective:for ∀ g’ ∈ G’ ∃ g ∈ G, s.t. φ(g) = g’, if G’ is not subjective, we must turn it into Im(φ))

for ∀ x,y ∈ G, φ(x ◦ y) = φ(x) ◦ φ(y)

G’ is isomorphic to the quotient group of the domain group over/by the kernel of the homomorphism:

G’ is isomorphic to G/ker(φ)

 remind: Kernel(φ) = { g ∈ G φ(g)=eG’} and all kernel group is normal subgroup

G/ker(φ) means partition up G into cosets

Prove: for all the elements in coset a¯=a◦ker(φ), will be mapped on the same elements in G’

=> for all the elements in coset a¯=a◦ker(φ) will be mapped on the same elements as element a

=> φ: G->G’ , so a mapped on to φ(a), all the other elements in coset a¯=a◦ker(φ) will be mapped on to φ(a)

for n∈ker(φ), a◦n is arbitrary element of a¯=a◦ker(φ), so

according to the law of homomorphims, φ(a◦n) = φ(a) ◦ φ(n) and because n∈ker(φ), based on the definition of kernel group, φ(n)=eG’, so that φ(a◦n) = φ(a) ◦ eG’ = φ(a)

Prove: element in a¯=a◦ker(φ) and b¯=b◦ker(φ) must be mapped on to different elements in the co-domain group G’,

prove by contradiction: take representatives a and b from a¯and b¯, let’s assume that φ(a)=φ(b),

compose φ(a) ◦ φ(b-1)=φ(b) ◦ φ(b-1), => φ(a◦b-1) = φ(b◦b-1) = φ(eG) = eG’ ,it means that a◦b-1 is the element of ker(φ),

a◦b-1 = n, and n∈ker(φ) => a=n◦b means a is an element in the right cosets of the kernel of the homomorphism by b , and for normal subgroup, left cosets equal to right cosets, so that a ∈ b¯=b◦ker(φ) , contradict to the partition of G

G’ is isomorphic to G/ker(φ)

a¯∈ G/ker(φ)，因为前面证明了结论：

within the same cosets of the kernel of the homomorphism(cosets: ker(φ), a◦ker(φ) ,b◦ker(φ) …) are going to be mapped on to the same elements in G’(the co-domain by this homomorphims φ)

then Prove it’s bijective:

1) surjective

2) injective

if we elements in two different cosets of the kernel of the homomorphism(cosets: ker(φ), a◦ker(φ) ,b◦ker(φ) …) , they have to be mapped on to differenet elements in the co-domain group G’

finally prove it obey the property of isomorphism:

∀ a¯, b¯ ∈ G/ker(φ), prove F(a¯◦ b¯) = F(a¯) ◦ F(b¯)

F(a¯◦ b¯) = F((a◦ b)¯) = φ(a◦b) = φ(a) ◦ φ(b)

F(a¯) ◦ F(b¯) = φ(a) ◦ φ(b)

todo:

Z*p Multiplicative group of integers modulo n / 整数模n乘法群

https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n