Colourings of the n GonFinite symmetric groupsGenerators of the symmetric groupSubgroups of Cyclic Groups

Subgroups of Cyclic Groups

Another useful result describes the cycle structure of a power of a cycle:
Lemma: For each natural number m the power (i1 ...ir)m consists of exactly gcd (r,m) disjoint cyclic factors, they all are of length r/ gcd (r,m).

Proof: Let l denote the length of the cyclic factor of (i1 ...ir )m containing i1. This cycle is

(i1 i bar (m+1) i bar (2m+1) ...i bar ((l-1)m+1)),
where bar (k) denotes the residue class of k modulo r. Correspondingly the cyclic factor containing i2 (if r>1) must be (i2 ...i bar ((l-1)m+2)), so that all the cyclic factors of (i1...ir)m have the same length l. Thus l is the order of (i1 ...ir)m, an element of the group á(i1 ...ir) ñ which is of order r. Hence r divides l ·m and r/ gcd (r,m) divides l ·(m/ gcd (r,m)) and therefore also l. But
(i1 ...ir)m ·(r/ gcd (r,m))=(i1 ...ir)r ·(m/ gcd (r,m))=1,
so that also l must divide r/ gcd (r,m), which proves that in fact l=r/ gcd (r,m).

An easy application of the lemma above gives

Corollary: The elements of order d in the group generated by the cycle (1 ...n) are the powers (1 ...n)i, where i is of the form (n ·j)/(d), and 1 £j<d is relatively prime to d.

A direct consequence of this is

Corollary: The group Cm := á(1 ...m) ñ contains, for each divisor d of m exactly one subgroup U of order d. Furthermore, this subgroup contains f(d) elements consisting of d-cycles only, if f(-) denotes the Euler function
f(d):= | {i Îd | gcd (d,i)=1 } | .
These f(d) elements form the set of generators of U.

As finite cyclic groups of the same order are isomorphic, they have the same properties:

Corollary: A finite cyclic group G has, for each divisor d of its order | G | , exactly one subgroup U of order d. Furthermore, this subgroup contains f(d) generators, and so, G has exactly f(d) elements of this particular order. Moreover
åd | n f(d)=n.

harald.fripertinger@kfunigraz.ac.at,
last changed: August 28, 2001

Colourings of the n GonFinite symmetric groupsGenerators of the symmetric groupSubgroups of Cyclic Groups