SC 220: Groups and Linear Algebra: B.

Tech
Sem-III

Sep 14 2020

The cyclic group (Z n , ⊕)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

The group (Z n , ⊕)

Consider a subset of Z.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

The group (Z n , ⊕)

Consider a subset of Z.
Zn = {0, 1, 2, 3, ......, n −
1}.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

The group (Z n , ⊕)

Consider a subset of Z.
Zn = {0, 1, 2, 3, ......, n − 1}.
Let a ∈ Z.
Then a = qn + r where q ∈ Z and r ∈ Zn .
r is the remainder when a is divided by n.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

The group (Z n , ⊕)

Consider a subset of Z.
Zn = {0, 1, 2, 3, ......, n − 1}.
Let a ∈ Z.
Then a = qn + r where q ∈ Z and r ∈
Zn. r is the remainder when a is divided
by n. We say a ≡ r ( mod n).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

The group (Z n , ⊕)

Consider a subset of Z.
Zn = {0, 1, 2, 3, ......, n − 1}.
Let a ∈ Z.
Then a = qn + r where q ∈ Z and r ∈
Zn . r is the remainder when a is divided
by n. We say a ≡ r ( mod n).
This relation is an equivalence relation on Z and the elements
of Zn represents distinct equivalence classes of Z.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

The group (Z n , ⊕)

Consider a subset of Z.
Zn = {0, 1, 2, 3, ......, n − 1}.
Let a ∈ Z.
Then a = qn + r where q ∈ Z and r ∈
Zn . r is the remainder when a is divided
by n. We say a ≡ r ( mod n).
This relation is an equivalence relation on Z and the elements
of Zn represents distinct equivalence classes of Z.
Eg. Consider n = 8

SC 220: Groups and Linear Algebra: B.Tech Sem-III

The group (Z n , ⊕)

Consider a subset of Z.
Zn = {0, 1, 2, 3, ......, n − 1}.
Let a ∈ Z.
Then a = qn + r where q ∈ Z and r ∈
Zn . r is the remainder when a is divided
by n. We say a ≡ r ( mod n).
This relation is an equivalence relation on Z and the elements
of Zn represents distinct equivalence classes of Z.
Eg. Consider n = 8
11 ≡ 3( mod 8),

SC 220: Groups and Linear Algebra: B.Tech Sem-III

The group (Z n , ⊕)

Consider a subset of Z.
Zn = {0, 1, 2, 3, ......, n − 1}.
Let a ∈ Z.
Then a = qn + r where q ∈ Z and r ∈
Zn . r is the remainder when a is divided
by n. We say a ≡ r ( mod n).
This relation is an equivalence relation on Z and the elements
of Zn represents distinct equivalence classes of Z.
Eg. Consider n = 8
11 ≡ 3( mod 8), 65 ≡ 1( mod 8),

SC 220: Groups and Linear Algebra: B.Tech Sem-III

The group (Z n , ⊕)

Consider a subset of Z.
Zn = {0, 1, 2, 3, ......, n − 1}.
Let a ∈ Z.
Then a = qn + r where q ∈ Z and r ∈
Zn . r is the remainder when a is divided
by n. We say a ≡ r ( mod n).
This relation is an equivalence relation on Z and the elements
of Zn represents distinct equivalence classes of Z.
Eg. Consider n = 8
11 ≡ 3( mod 8), 65 ≡ 1( mod 8), − 30 ≡ 2( mod 8)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

The group (Z n , ⊕)

Consider a subset of Z.
Zn = {0, 1, 2, 3, ......, n − 1}.
Let a ∈ Z.
Then a = qn + r where q ∈ Z and r ∈
Zn . r is the remainder when a is divided
by n. We say a ≡ r ( mod n).
This relation is an equivalence relation on Z and the elements
of Zn represents distinct equivalence classes of Z.
Eg. Consider n = 8
11 ≡ 3( mod 8), 65 ≡ 1( mod 8), − 30 ≡ 2( mod 8)
8 ≡ 0( mod 8), 24 ≡ 0( mod 8)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Addition in Zn :

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Addition in Zn :
Let a, b ∈ Zn then ∃r ∈ Zn such that
a + b ≡ r ( mod n).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Addition in Zn :
Let a, b ∈ Zn then ∃r ∈ Zn such that
a + b ≡ r ( mod n).
Define the binary operation addition modulo n as
a⊕b=r.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Addition in Zn:
Let a, b ∈ Zn then ∃r ∈ Zn such that
a + b ≡ r ( mod n).
Define the binary operation addition modulo n as
a⊕b=r.
(Zn, ⊕) is a group.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Addition in Zn :
Let a, b ∈ Zn then ∃r ∈ Zn such that
a + b ≡ r ( mod n).
Define the binary operation addition modulo n as
a⊕b=r.
(Zn, ⊕) is a group.
0 is the identity element.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Addition in Zn :
Let a, b ∈ Zn then ∃r ∈ Zn such that
a + b ≡ r ( mod n).
Define the binary operation addition modulo n as
a⊕b=r.
(Zn, ⊕) is a group.
0 is the identity element.
For a ∈ Zn, n − a ∈ Zn is the additive inverse.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let G = (a) be a finite cyclic group of order
n.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let G = (a) be a finite cyclic group of order
n. ai ∗aj = ai⊕j ; 0 ≤ i, j < n.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let G = (a) be a finite cyclic group of order n.
ai ∗aj = ai⊕j ; 0 ≤ i, j < n.So every cyclic group of order n is
similar to (Zn, ⊕)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let G = (a) be a finite cyclic group of order n.
ai ∗aj = ai⊕j ; 0 ≤ i, j < n.So every cyclic group of order n is
similar to (Zn, ⊕)
We study a number of properties of the finite cyclic group
(Zn, ⊕) which are similar to the ones we have seen for
the infinite cyclic group (Z, +).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Lemma 6
Let d ∈ (Zn, ⊕).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Lemma 6
Let d ∈ (Zn, ⊕). Consider the subgroup (d ) of (Zn,
⊕)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Lemma 6
Let d ∈ (Zn, ⊕). Consider the subgroup (d ) of (Zn,
If d |n Then o((d )) dn
⊕)
=

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Lemma 6
Let d ∈ (Zn, ⊕). Consider the subgroup (d ) of (Zn,
If d |n Then o((d )) dn
⊕)
=
Proof
Let n =
kd .

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Lemma 6
Let d ∈ (Zn, ⊕). Consider the subgroup (d ) of (Zn,
If d |n Then o((d )) dn
⊕)
=
Proof
Let n = kd .
Then o(d ) in Zn is nd.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Lemma 6
Let d ∈ (Zn, ⊕). Consider the subgroup (d ) of (Zn,
If d |n Then o((d )) dn
⊕)
=
Proof
Let n =
kd
Then. o(d ) in Zn is nd.
Hence o((d )) = o(d ) =dn .

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proposition 4
Every subgroup H of Zn is cyclic.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proposition 4
Every subgroup H of Zn is cyclic. Furthermore, if H ƒ= {0}
then ∃d ∈ H such that o(H) = dn

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proposition 4
Every subgroup H of Zn is cyclic. Furthermore, if H =ƒ { 0 }
then ∃d ∈ H such that o(H) = dn
Proof:
If H = { 0 } then it is cyclic of order 1.
If H ƒ= { 0 } then it has a minimum positive element, say, d
.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proposition 4
Every subgroup H of Zn is cyclic. Furthermore, if H ƒ= {0}
then ∃d ∈ H such that o(H) = dn
Proof:
If H = { 0 } then it is cyclic of order 1.
If H ƒ= { 0 } then it has a minimum positive element, say,
d . Suppose n = kd + s

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proposition 4
Every subgroup H of Zn is cyclic. Furthermore, if H ƒ= {0}
then ∃d ∈ H such that o(H) = dn
Proof:
If H = { 0 } then it is cyclic of order 1.
If H ƒ= { 0 } then it has a minimum positive element, say,
d . Suppose n = kd + s with 0 ≤ s < d and 0 ≤ kd < n.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proposition 4
Every subgroup H of Zn is cyclic. Furthermore, if H ƒ= {0}
then ∃d ∈ H such that o(H) = dn
Proof:
If H = { 0 } then it is cyclic of order 1.
If H ƒ= { 0 } then it has a minimum positive element, say,
d . Suppose n = kd + s with 0 ≤ s < d and 0 ≤ kd < n.
Now kd ∈ H =⇒

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proposition 4
Every subgroup H of Zn is cyclic. Furthermore, if H ƒ= {0}
then ∃d ∈ H such that o(H) = dn
Proof:
If H = { 0 } then it is cyclic of order 1.
If H ƒ= { 0 } then it has a minimum positive element, say,
d . Suppose n = kd + s with 0 ≤ s < d and 0 ≤ kd < n.
Now kd ∈ H =⇒ (kd )−1 = n − kd = s ∈ H.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proposition 4
Every subgroup H of Zn is cyclic. Furthermore, if H ƒ= {0}
then ∃d ∈ H such that o(H) = dn
Proof:
If H = { 0 } then it is cyclic of order 1.
If H ƒ= { 0 } then it has a minimum positive element, say,
d . Suppose n = kd + s with 0 ≤ s < d and 0 ≤ kd < n.
Now kd ∈ H =⇒ (kd )−1 = n − kd = s ∈
H. Since d is the minimum positive element
in H

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proposition 4
Every subgroup H of Zn is cyclic. Furthermore, if H ƒ= {0}
then ∃d ∈ H such that o(H) = dn
Proof:
If H = { 0 } then it is cyclic of order 1.
If H ƒ= { 0 } then it has a minimum positive element, say,
d . Suppose n = kd + s with 0 ≤ s < d and 0 ≤ kd < n.
Now kd ∈ H =⇒ (kd )−1 = n − kd = s ∈
H. Since d is the minimum positive element
in H the only possibility is s = 0

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proposition 4
Every subgroup H of Zn is cyclic. Furthermore, if H ƒ= {0}
then ∃d ∈ H such that o(H) = dn
Proof:
If H = { 0 } then it is cyclic of order 1.
If H ƒ= { 0 } then it has a minimum positive element, say,
d . Suppose n = kd + s with 0 ≤ s < d and 0 ≤ kd < n.
Now kd ∈ H =⇒ (kd )−1 = n − kd = s ∈
H. Since d is the minimum positive element
in H the only possibility is s = 0 =⇒ d |
n.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proposition 4
Every subgroup H of Zn is cyclic. Furthermore, if H =ƒ { 0 }
then ∃d ∈ H such that o(H) = dn
Proof:
If H = { 0 } then it is cyclic of order 1.
If H ƒ= { 0 } then it has a minimum positive element, say,
d . Suppose n = kd + s with 0 ≤ s < d and 0 ≤ kd < n.
Now kd ∈ H =⇒ (kd )−1 = n − kd = s ∈
H. Since d is the minimum positive element
in H the only possibility is s = 0 =⇒ d |
n
∴ by lemma 6 o((d )) d
n.
= ......contd.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

....contd.
Now we will show that H =
(d ).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

....contd.
Now we will show that H =
(d ). Consider a ∈ H such that

SC 220: Groups and Linear Algebra: B.Tech Sem-III

....contd.
Now we will show that H =
(d ). Consider a ∈ H such that

a = qd + (1)
r

SC 220: Groups and Linear Algebra: B.Tech Sem-III

....contd.
Now we will show that H =
(d ). Consider a ∈ H such that

a = qd + r (1)

where 0 ≤ r < d and 0 ≤ qd < a

SC 220: Groups and Linear Algebra: B.Tech Sem-III

....contd.
Now we will show that H =
(d ). Consider a ∈ H such that

a = qd + (1)
r
where 0 ≤ r < d and 0 ≤ qd < a
Since a < n Eq.(1) can be written as

SC 220: Groups and Linear Algebra: B.Tech Sem-III

....contd.
Now we will show that H =
(d ). Consider a ∈ H such that

a = qd + (1)
r
where 0 ≤ r < d and 0 ≤ qd <
a
Since a < n Eq.(1) can be written as

a = qd ⊕ r (2)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

....contd.
Now we will show that H =
(d ). Consider a ∈ H such that

a = qd + (1)
r
where 0 ≤ r < d and 0 ≤ qd <
a
Since a < n Eq.(1) can be written as

a = qd ⊕ r (2)

. Now qd ∈ H

SC 220: Groups and Linear Algebra: B.Tech Sem-III

....contd.
Now we will show that H =
(d ). Consider a ∈ H such that

a = qd + (1)
r
where 0 ≤ r < d and 0 ≤ qd <
a
Since a < n Eq.(1) can be written as

a = qd ⊕ r (2)

. Now qd ∈ H =⇒ (qd )−1 = n − qd ∈ H.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

....contd.
Now we will show that H =
(d ). Consider a ∈ H such that

a = qd + (1)
r
where 0 ≤ r < d and 0 ≤ qd <
a
Since a < n Eq.(1) can be written as

a = qd ⊕ r (2)

. Now qd ∈ H =⇒ (qd )−1 = n − qd ∈

H. So Eq.(2) gives (qd )−1 ⊕ a = r ∈ H.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

....contd.
Now we will show that H =
(d ). Consider a ∈ H such that

a = qd + (1)
r
where 0 ≤ r < d and 0 ≤ qd <
a
Since a < n Eq.(1) can be written as

a = qd ⊕ r (2)

. Now qd ∈ H =⇒ (qd )−1 = n − qd ∈

H. So Eq.(2) gives (qd )−1 ⊕ a = r ∈ H.
But the minimum positive element in H is d

SC 220: Groups and Linear Algebra: B.Tech Sem-III

....contd.
Now we will show that H =
(d ). Consider a ∈ H such that

a = qd + (1)
r
where 0 ≤ r < d and 0 ≤ qd <
a
Since a < n Eq.(1) can be written as

a = qd ⊕ r (2)

. Now qd ∈ H =⇒ (qd )−1 = n − qd ∈

H. So Eq.(2) gives (qd )−1 ⊕ a = r ∈ H.
But the minimum positive element in H is d
∴ r = 0 and a = qd .
Every element in H is generated by d. ⇒ H = (d ) .

SC 220: Groups and Linear Algebra: B.Tech Sem-III

....contd.
Now we will show that H =
(d ). Consider a ∈ H such that

a = qd + (1)
r
where 0 ≤ r < d and 0 ≤ qd <
a
Since a < n Eq.(1) can be written as

a = qd ⊕ r (2)

. Now qd ∈ H =⇒ (qd )−1 = n − qd ∈

H. So Eq.(2) gives (qd )−1 ⊕ a = r ∈ H.
But the minimum positive element in H is d
∴ r = 0 and a = qd .
Every element in H is generated by d. ⇒ H = (d ) .
∴ o(H) = n d

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg.
Z10 = {0, 1, 2, 3, 4, 5, 6, 7,
8, 9}.
The only subgroups of Z10 are

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg.
Z10 = {0, 1, 2, 3, 4, 5, 6, 7,
8, 9}.
The only subgroups of Z10 are
{0},

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg.
Z10 = {0, 1, 2, 3, 4, 5, 6, 7,
8, 9}.
The only subgroups of Z10 are
{0}, {0, 2, 4, 6, 8} = (2),

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg.
Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
The only subgroups of Z10 are
{0}, {0, 2, 4, 6, 8} = (2), {0, 5} = (5)
and

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg.
Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
The only subgroups of Z10 are
{0}, {0, 2, 4, 6, 8} = (2), {0, 5} = (5) and Z10 =
(1).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg.
Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
The only subgroups of Z10 are
{0}, {0, 2, 4, 6, 8} = (2), {0, 5} = (5) and Z10 =
(1).
All these are cyclic subgroups.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg.
Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
The only subgroups of Z10 are
{0}, {0, 2, 4, 6, 8} = (2), {0, 5} = (5) and Z10 =
All
(1).these are cyclic subgroups.
o((2)) = 10
2 =
5,

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg.
Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
The only subgroups of Z10 are
{0}, {0, 2, 4, 6, 8} = (2), {0, 5} = (5) and Z10 =
(1). 10
o((2)) = are
All these 2 =cyclic
, o((5)) = 10
5 =
subgroups.
5 2,

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg.
Z10 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
The only subgroups of Z10 are
{0}, {0, 2, 4, 6, 8} = (2), {0, 5} = (5) and Z10 =
(1). 10
o((2)) = are
All these 2 =cyclic
, o((5)) = 10 10
5 = 2, o((1)) = 1 =
subgroups.
5 10

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Corollary:
Consider the cyclic subgroup (a) of Zn . Then (a) = (d ) where
d = g.c.d(a, n).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Corollary:
Consider the cyclic subgroup (a) of Zn . Then (a) = (d )
d = g.c.d(a, n). o((a)) dn
where
=
Proof

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Corollary:
Consider the cyclic subgroup (a) of Zn . Then (a) = (d )
d = g.c.d(a, n). o((a)) dn
where
=
Proof
Let d be the minimum positive element of (a)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Corollary:
Consider the cyclic subgroup (a) of Zn . Then (a) = (d )
d = g.c.d(a, n). o((a)) dn
where
=
Proof
Let d be the minimum positive element of (a)
Then (a) = (d ) and

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Corollary:
Consider the cyclic subgroup (a) of Zn . Then (a) = (d )
d = g.c.d(a, n). o((a)) dn
where
=
Proof
Let d be the minimum positive element of (a)
Then (a) = (d ) and d |a and d |n.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Corollary:
Consider the cyclic subgroup (a) of Zn . Then (a) = (d )
d = g.c.d(a, n). o((a)) dn
where
=
Proof
Let d be the minimum positive element of (a)
Then (a) = (d ) and d |a and d |
n. Since d ∈ (a),

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Corollary:
Consider the cyclic subgroup (a) of Zn . Then (a) = (d )
d = g.c.d(a, n). o((a)) dn
where
=
Proof
Let d be the minimum positive element of (a)
Then (a) = (d ) and d |a and d |
n. Since d ∈ (a), ∃ k ∈ Z such
that d = ka( mod n) ⇒

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Corollary:
Consider the cyclic subgroup (a) of Zn . Then (a) = (d )
d = g.c.d(a, n). o((a)) dn
where
=
Proof
Let d be the minimum positive element of (a)
Then (a) = (d ) and d |a and d |n.
Since d ∈ (a), ∃ k ∈ Z such that
d = ka( mod n) ⇒ d = ka − nq; where q ∈ Z

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Corollary:
Consider the cyclic subgroup (a) of Zn . Then (a) = (d )
d = g.c.d(a, n). o((a)) dn
where
=
Proof
Let d be the minimum positive element of (a)
Then (a) = (d ) and d |a and d |n.
Since d ∈ (a), ∃ k ∈ Z such that
d = ka( mod n) ⇒ d = ka − nq; where q ∈ Z
So if c|a and c|n then c|d .

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Corollary:
Consider the cyclic subgroup (a) of Zn . Then (a) = (d )
d = g.c.d(a, n). o((a)) dn
where
=
Proof
Let d be the minimum positive element of (a)
Then (a) = (d ) and d |a and d |n.
Since d ∈ (a), ∃ k ∈ Z such that
d = ka( mod n) ⇒ d = ka − nq; where q ∈ Z
So if c|a and c|n then c|d
. So d = g.c.d(a, n)
◆♦◆

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg. Consider the subgroup (9) of Z12
(9) = {0, 9, 6, 3} =

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg. Consider the subgroup (9) of Z12
(9) = {0, 9, 6, 3} = (3)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg. Consider the subgroup (9) of Z12
(9) = {0, 9, 6, 3} = (3)
3 is the g.c.d(9, 12).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg. Consider the subgroup (9) of Z12
(9) = {0, 9, 6, 3} = (3)
3 is the g.c.d(9, 12).

This corollary gives a way to find out the generators of Zn .

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg. Consider the subgroup (9) of Z12
(9) = {0, 9, 6, 3} = (3)
3 is the g.c.d(9, 12).

This corollary gives a way to find out the generators of Zn .

If a ∈ Zn is such that g.c.d(a, n) = 1, i.e , a and n are
relatively prime then

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg. Consider the subgroup (9) of Z12
(9) = {0, 9, 6, 3} = (3)
3 is the g.c.d(9, 12).

This corollary gives a way to find out the generators of Zn .

If a ∈ Zn is such that g.c.d(a, n) = 1, i.e , a and n are
relatively prime then
(a) = (1) = Zn

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Eg. Consider the subgroup (9) of Z12
(9) = {0, 9, 6, 3} = (3)
3 is the g.c.d(9, 12).

This corollary gives a way to find out the generators of Zn .

If a ∈ Zn is such that g.c.d(a, n) = 1, i.e , a and n are
relatively prime then
(a) = (1) = Zn
Eg.
The generators of Z12 are 1, 5, 7 and 11

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let (a) and (b) be two subgroups of Zn .

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let (a) and (b) be two subgroups of
Zn. We define the set (a) ⊕ (b) as

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let (a) and (b) be two subgroups of Zn .
We define the set (a) ⊕ (b) as

(a) ⊕ (b) = {x ⊕ y |x ∈ (a), y ∈

(b)}

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let (a) and (b) be two subgroups of Zn .
We define the set (a) ⊕ (b) as

(a) ⊕ (b) = {x ⊕ y |x ∈ (a), y ∈

(b)}

Eg.
Z14 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
13}

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let (a) and (b) be two subgroups of Zn .
We define the set (a) ⊕ (b) as

(a) ⊕ (b) = {x ⊕ y |x ∈ (a), y ∈

(b)}

Eg.
Z14 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
13}
Consider the subgroups
(2) = {0, 2, 4, 6, 8, 10, 12}

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let (a) and (b) be two subgroups of Zn .
We define the set (a) ⊕ (b) as

(a) ⊕ (b) = {x ⊕ y |x ∈ (a), y ∈

(b)}

Eg.
Z14 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
13}
Consider the subgroups
(2) = {0, 2, 4, 6, 8, 10, 12} = (4)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let (a) and (b) be two subgroups of Zn .
We define the set (a) ⊕ (b) as

(a) ⊕ (b) = {x ⊕ y |x ∈ (a), y ∈ (b)}

Eg.
Z14 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
Consider the subgroups
(2) = {0, 2, 4, 6, 8, 10, 12} = (4) = (6) = (8) = (10) =
(12)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let (a) and (b) be two subgroups of Zn .
We define the set (a) ⊕ (b) as

(a) ⊕ (b) = {x ⊕ y |x ∈ (a), y ∈ (b)}

Eg.
Z14 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
Consider the subgroups
(2) = {0, 2, 4, 6, 8, 10, 12} = (4) = (6) = (8) = (10) =
(12)
(7) = {0, 7}

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let (a) and (b) be two subgroups of Zn .
We define the set (a) ⊕ (b) as

(a) ⊕ (b) = {x ⊕ y |x ∈ (a), y ∈ (b)}

Eg.
Z14 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
Consider the subgroups
(2) = {0, 2, 4, 6, 8, 10, 12} = (4) = (6) = (8) = (10) =
(12)
(7) = {0, 7}
L
(6) ( 7 ) = {0, 2, 4, 6, 8, 10, 12, 7, 9, 11, 13, 1, 3, 5}
= Z14

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let (a) and (b) be two subgroups of Zn .
We define the set (a) ⊕ (b) as

(a) ⊕ (b) = {x ⊕ y |x ∈ (a), y ∈ (b)}

Eg.
Z14 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
Consider the subgroups
(2) = {0, 2, 4, 6, 8, 10, 12} = (4) = (6) = (8) = (10) =
(12)
(7) = {0, 7}
(6) (7) = {0, 2, 4, 6, 8, 10, 12, 7, 9, 11, 13, 1, 3,
(4)
5} = Z(8)
14 = {0, 2, 4, 6, 8, 10, 12} =
L (2)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Let (a) and (b) be two subgroups of Zn .
We define the set (a) ⊕ (b) as

(a) ⊕ (b) = {x ⊕ y |x ∈ (a), y ∈ (b)}

Eg.
Z14 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}
Consider the subgroups
(2) = {0, 2, 4, 6, 8, 10, 12} = (4) = (6) = (8) = (10) =
(12)
(7) = {0,) =
(6) 7}{0, 2, 4, 6, 8, 10, 12, 7, 9, 11, 13, 1, 3, 14
L
(7
(4) (8)5}=={0,
Z 2, 4, 6, 8, 10, 12} = (2) also =
(4)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proposition 5
Let (a) and (b) be two subgroups of (Zn, ⊕), then (a) ⊕ (b)
is also a subgroup of (Zn, ⊕).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proposition 5
Let (a) and (b) be two subgroups of (Zn, ⊕), then (a) ⊕ (b)
is also a subgroup of (Zn, ⊕). Further
(a) ⊕ (b) = (d ) = (d j ) where

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proposition 5
Let (a) and (b) be two subgroups of (Zn, ⊕), then (a) ⊕ (b)
is also a subgroup of (Zn, ⊕). Further
(a) ⊕ (b) = (d ) = (d j ) where d =g.c.d(a, b) and
d j =g.c.d(a, b, n).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proof:

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proof:
Let w1, w2 ∈ (a) ⊕ (b).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proof:
Let w1, w2 ∈ (a) ⊕ (b).
w1 = x1 ⊕ y1 and w2 = x2 ⊕ y2

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proof:
Let w1, w2 ∈ (a) ⊕ (b).
w1 = x1 ⊕ y1 and w2 = x2 ⊕ y2
where x1, x2 ∈ (a) and y1, y2 ∈
(b).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proof:
Let w1, w2 ∈ (a) ⊕ (b).
w1 = x1 ⊕ y1 and w2 = x2 ⊕ y2
where x1, x2 ∈ (a) and y1, y2 ∈ (b).

w1 ⊕ w2 = (x1 ⊕ y1) ⊕ (x2 ⊕

y2 )

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proof:
Let w1, w2 ∈ (a) ⊕ (b).
w1 = x1 ⊕ y1 and w2 = x2 ⊕ y2
where x1, x2 ∈ (a) and y1, y2 ∈ (b).

w1 ⊕ w2 = (x1 ⊕ y1) ⊕ (x2 ⊕ y2)

= (x1 ⊕ x2) ⊕ (y1 ⊕ y2)
By associativity and
commutativity of Zn

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proof:
Let w1, w2 ∈ (a) ⊕ (b).
w1 = x1 ⊕ y1 and w2 = x2 ⊕ y2
where x1, x2 ∈ (a) and y1, y2 ∈ (b).

w1 ⊕ w2 = (x1 ⊕ y1) ⊕ (x2 ⊕ y2)

= (x1 ⊕ x2) ⊕ (y1 ⊕ y2)
By associativity and
commutativity of Zn

Since x1 ⊕ x2 ∈ (a) and y1 ⊕ y2 ∈ (b)

w1 ⊕ w2 ∈ (a) ⊕ (b).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proof:
Let w1, w2 ∈ (a) ⊕ (b).
w1 = x1 ⊕ y1 and w2 = x2 ⊕ y2
where x1, x2 ∈ (a) and y1, y2 ∈ (b).

w1 ⊕ w2 = (x1 ⊕ y1) ⊕ (x2 ⊕ y2)

= (x1 ⊕ x2) ⊕ (y1 ⊕ y2)
By associativity and
commutativity of Zn

Since x1 ⊕ x2 ∈ (a) and y1 ⊕ y2 ∈ (b)

w1 ⊕ w2 ∈ (a) ⊕ (b).
(a) ⊕ (b) is a finite set and it is closed under ⊕. Therefore
by proposition 2 it is a subgroup of (Zn, ⊕)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

Proof:
Let w1, w2 ∈ (a) ⊕ (b).
w1 = x1 ⊕ y1 and w2 = x2 ⊕ y2
where x1, x2 ∈ (a) and y1, y2 ∈ (b).

w1 ⊕ w2 = (x1 ⊕ y1) ⊕ (x2 ⊕ y2)

= (x1 ⊕ x2) ⊕ (y1 ⊕ y2)
By associativity and
commutativity of Zn

Since x1 ⊕ x2 ∈ (a) and y1 ⊕ y2 ∈ (b)

w1 ⊕ w2 ∈ (a) ⊕ (b).
(a) ⊕ (b) is a finite set and it is closed under ⊕. Therefore
by proposition 2 it is a subgroup of (Zn, ⊕)
Alternatively: Let H = (a) and K = (b).
Since HK = (a) ⊕ (b) = (b) ⊕ (a) =
KH,
SC 220: Groups and Linear Algebra: B.Tech Sem-III
Proof:
Let w1, w2 ∈ (a) ⊕ (b).
w1 = x1 ⊕ y1 and w2 = x2 ⊕ y2
where x1, x2 ∈ (a) and y1, y2 ∈ (b).

w1 ⊕ w2 = (x1 ⊕ y1) ⊕ (x2 ⊕ y2)

= (x1 ⊕ x2) ⊕ (y1 ⊕ y2)
By associativity and
commutativity of Zn

Since x1 ⊕ x2 ∈ (a) and y1 ⊕ y2 ∈ (b)

w1 ⊕ w2 ∈ (a) ⊕ (b).
(a) ⊕ (b) is a finite set and it is closed under ⊕. Therefore
by proposition 2 it is a subgroup of (Zn, ⊕)
Alternatively: Let H = (a) and K = (b).
Since HK = (a) ⊕ (b) = (b) ⊕ (a) =
KH,
we have HK = (a) ⊕ (b) is a subgroup SC 220: Groups and Linear Algebra: B.Tech Sem-III
 ..........contd.
Now we show (a) ⊕ (b) =
(d )

SC 220: Groups and Linear Algebra: B.Tech Sem-III

 ..........contd.
Now we show (a) ⊕ (b) =
(d )
d =g.c.d(a, b).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

 ..........contd.
Now we show (a) ⊕ (b) =
(d )
d =g.c.d(a, b). ⇒ d |a

SC 220: Groups and Linear Algebra: B.Tech Sem-III

 ..........contd.
Now we show (a) ⊕ (b) =
(d )
d =g.c.d(a, b). ⇒ d |a
⇒ a = dq for some q ∈ Z.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

 ..........contd.
Now we show (a) ⊕ (b) =
(d )
d =g.c.d(a, b). ⇒ d |a
⇒ a = dq for some q ∈ Z.
Let x ∈ (a).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

 ..........contd.
Now we show (a) ⊕ (b) = (d )
d =g.c.d(a, b). ⇒ d |a
⇒ a = dq for some q ∈ Z.
Let x ∈ (a). Then x = ak ( mod n) for some k ∈ Z.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

 ..........contd.
Now we show (a) ⊕ (b) = (d )
d =g.c.d(a, b). ⇒ d |a
⇒ a = dq for some q ∈ Z.
Let x ∈ (a). Then x = ak ( mod n) for some k ∈ Z.
⇒ x = dqk ( mod n) ⇒ x ∈ (d )

SC 220: Groups and Linear Algebra: B.Tech Sem-III

 ..........contd.
Now we show (a) ⊕ (b) = (d )
d =g.c.d(a, b). ⇒ d |a
⇒ a = dq for some q ∈ Z.
Let x ∈ (a). Then x = ak ( mod n) for some k ∈ Z.
⇒ x = dqk ( mod n) ⇒ x ∈ (d )
∴ (a) ⊂ (d )

SC 220: Groups and Linear Algebra: B.Tech Sem-III

 ..........contd.
Now we show (a) ⊕ (b) = (d )
d =g.c.d(a, b). ⇒ d |a
⇒ a = dq for some q ∈ Z.
Let x ∈ (a). Then x = ak ( mod n) for some k ∈ Z.
⇒ x = dqk ( mod n) ⇒ x ∈ (d )
∴ (a) ⊂ (d )
Similarly (b) ⊂ (d ).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

 ..........contd.
Now we show (a) ⊕ (b) = (d )
d =g.c.d(a, b). ⇒ d |a
⇒ a = dq for some q ∈ Z.
Let x ∈ (a). Then x = ak ( mod n) for some k ∈ Z.
⇒ x = dqk ( mod n) ⇒ x ∈ (d )
∴ (a) ⊂ (d )
Similarly (b) ⊂ (d ).
By closure of (d ) under ⊕,

SC 220: Groups and Linear Algebra: B.Tech Sem-III

 ..........contd.
Now we show (a) ⊕ (b) = (d )
d =g.c.d(a, b). ⇒ d |a
⇒ a = dq for some q ∈ Z.
Let x ∈ (a). Then x = ak ( mod n) for some k ∈ Z.
⇒ x = dqk ( mod n) ⇒ x ∈ (d )
∴ (a) ⊂ (d )
Similarly (b) ⊂ (d ).
By closure of (d ) under ⊕, (a) ⊕ (b) ⊂ (d ).
.......contd.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

...........contd.
Let x ∈ (d )

SC 220: Groups and Linear Algebra: B.Tech Sem-III

...........contd.
Let x ∈ (d ) ⇒ x = dk ( mod n)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

...........contd.
Let x ∈ (d ) ⇒ x = dk ( mod n)
Since d =g.c.d(a, b),

SC 220: Groups and Linear Algebra: B.Tech Sem-III

...........contd.
Let x ∈ (d ) ⇒ x = dk ( mod n)
Since d =g.c.d(a, b), by proposition
2

SC 220: Groups and Linear Algebra: B.Tech Sem-III

...........contd.
Let x ∈ (d ) ⇒ x = dk ( mod n)
Since d =g.c.d(a, b), by proposition
2
∃ r , s ∈ Z, such that d = ar + bs.
∴ x = (ar + bs)k ( mod n)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

...........contd.
Let x ∈ (d ) ⇒ x = dk ( mod n)
Since d =g.c.d(a, b), by proposition 2
∃ r , s ∈ Z, such that d = ar + bs.
∴ x = (ar + bs)k ( mod n) = ark ( mod n) ⊕ bsk ( mod n)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

...........contd.
Let x ∈ (d ) ⇒ x = dk ( mod n)
Since d =g.c.d(a, b), by proposition 2
∃ r , s ∈ Z, such that d = ar + bs.
∴ x = (ar + bs)k ( mod n) = ark ( mod n) ⊕ bsk ( mod n)
Hence x ∈ (a) ⊕ (b)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

...........contd.
Let x ∈ (d ) ⇒ x = dk ( mod n)
Since d =g.c.d(a, b), by proposition 2
∃ r , s ∈ Z, such that d = ar + bs.
∴ x = (ar + bs)k ( mod n) = ark ( mod n) ⊕ bsk ( mod n)
Hence x ∈ (a) ⊕ (b) ⇒ (d ) ⊂ (a) ⊕ (b)

SC 220: Groups and Linear Algebra: B.Tech Sem-III

...........contd.
Let x ∈ (d ) ⇒ x = dk ( mod n)
Since d =g.c.d(a, b), by proposition 2
∃ r , s ∈ Z, such that d = ar + bs.
∴ x = (ar + bs)k ( mod n) = ark ( mod n) ⊕ bsk ( mod n)
Hence x ∈ (a) ⊕ (b) ⇒ (d ) ⊂ (a) ⊕ (b)
So (a) ⊕ (b) = (d ).
...............contd.

SC 220: Groups and Linear Algebra: B.Tech Sem-III

................contd.
By the corollary to proposition 4,

SC 220: Groups and Linear Algebra: B.Tech Sem-III

................contd.
By the corollary to proposition 4,
(d ) = (d j ) where d j =g.c.d(d,
n).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

................contd.
By the corollary to proposition 4,
(d ) = (d j ) where d j =g.c.d(d, n).
It can be shown that g.c.d(d, n) = g.c.d(a, b,
n).

SC 220: Groups and Linear Algebra: B.Tech Sem-III

................contd.
By the corollary to proposition 4,
(d ) = (d j ) where d j =g.c.d(d, n).
It can be shown that g.c.d(d, n) = g.c.d(a, b,
n). This completes the proof.
◆♦◆

SC 220: Groups and Linear Algebra: B.Tech Sem-III