DHARM88 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCEl Consider another example of group (X, ×), i.e. X = {1, ω, ω^2 }, where ω is cube root of
unity. Then group is cyclic with the generator g = [ω] because, the elements of X are
expressed in ω^3 , ω, ω^2 respectively for 1, ω, and ω^2. Further, the inverse element of
ω i.e., ω^2 is also the generator. Therefore, g = [ω] and [ω^2 ].
Example 4.9. Show that group (I, +) is a cyclic group. Find its generator (where I is the set of
integers)
Sol. Since, the set I = {......– 2, – 1, 0, 1, 2, ......}. The elements of I can be generated from on
of the element ‘1’ i.e., n = 1 + 1 + ......+ 1 (n times) = n. g. Since + is closed operation on
generator g, so we can write as, g + g + ....... + g (n times) = n. g, where,
(1)^0 = 0 (identity element),
(1)^1 = 1, (1 itself)
(1)^2 = 1 + 1 = 2,
(1)^3 = 1 + 1 + 1 = 3, and so on.
Similarly,
(1)–1 = [(1)^1 ]–1 = [1]–1 = – 1,
(1)–2 = [(1)^2 ]–1 = [2]–1 = – 2, and so on.
Therefore, g = [1] and also [– 1].
Example 4.10. Show that group X = ({1, 2, 3, 4, 5, 6}, × 7 ) is a cyclic group, where × 7 is a
multiplication modulo 7 operator.
Sol. Since the elements of the group X are generated from the element 3 and 5, and there
generations are shown below.
(3)^0 = 1 (identity element), Also, (5)^0 = 1 (identity element),
(3)^1 = 3, (generator itself) (5)^1 = 5, (generator itself)
(3)^2 = 3 × 7 3 = 2, (5)^2 = 5 × 7 5 = 4,
(3)^3 = 3 × 7 3 × 7 3 = 6, (5)^3 = 5 × 7 5 × 7 5 = 6,
(3)^4 = 3 × 7 3 × 7 3 × 7 3 = 4, (5)^4 = 5 × 7 5 × 7 5 × 7 5 = 2,
(3)^5 = 3 × 7 3 × 7 3 × 7 3 × 7 3 = 5 (5)^5 = 5 × 7 5 × 7 5 × 7 5 × 7 5 = 3
Therefore, g = [3] and [5].
(here 5 is the inverse element of 3)
Facts
l We can denote the cyclic group X generated by g as,
X = <g>
l A cyclic group X = <g> of order m can be define as, i.e., it consists of the powers,
X = <g> = {g^0 , g, g^2 , ......., gm–1}, where gm = ê;
l Every subgroup of a cyclic group is cyclic.
l If a is the generator of the cyclic group X then inverse element of a is also the gen-
erator of X.4.10 Cosets.................................................................................................................................
For a group (X, ) let (Y, ) is a subgroup of X (i.e. Y ⊆ X), then we define the cosets of Y for
any arbitrary x ∈ X are,
(Left coset) x Y = {x y/y ∈ Y}, and
(Right coset) Y x = {y x/y ∈ Y}