DHARM90 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCEHence, from the theorem we obtain that, if X is finite group and g ∈ X then O(X) is
divisors of O(g).
Example 4.11. If X be a finite group of order n, then for every x ∈ X, xn = ê.
Sol. Since, O(X) = n. let m = O(g), and from the conclusion of the previous theorem,
O(g)/O(X) = m/n,
Putting n = m. k, since m = O(g), and we have, gm = ê
So, gn = gm.k = (gm)k = ê
Thus gn = ê, for all g ∈ X.
Hence, g satisfies the equation xn = ê.
Example 4.12. If X = < g > is a cyclic group of order m, then show that
O(gk) = m/gcd(k, m), where gcd(k, m) = greatest common divisor of k and m.
Sol. Let Y = < gk >, then O(gk) = O(Y)
Putting, j = gcd(k, m)
Claim, Y = < gk > = < gj >
Since, for j/k and j/m we can write k = j. k′ and m = j. m′
So, gk = gjk′ = (gj).k′ ∈ < gj >
Thus, < gk > ⊂ < gj >
In order to prove the reverse inclusion, we use the fact that gcd of two numbers can be
expressed into the linear combination of these two numbers, i.e.
j = pk + qm (where p and q are integers)
so we have gj = gpk+qm = gpk. gqm = gpk. êq = gpk (since gm = ê)
so, gj = (gp)k ∈ < gk >
Therefore, < gj > ⊂ < gk >
Hence, claim is proved. It resulted,
Y = {ê, gj, g^2 j,......gjm′}, m = j. m′⇒m′ = m/j
⇒ O(Y) = m′ = m/j = m/gcd(k, m)
4.11 Group Mapping..................................................................................................................
Suppose there are algebraic systems of the same types, defined on X and Y, e.g., groups, rings,
etc. A mapping f : X Y which preserves all operations is called homomorphism.
Let (X, ) and (Y, ) are two groups, then a mapping f : X → Y such that for any x 1 ,
x 2 ∈X
f(x 1 x 2 ) = f(x 1 ) f(x 2 )
is called a group homomorphism from (X, ) to (Y, ).
l If group homomorphism f is surjective then, f is called epimorphism.
l If group homomorphism f is injective then, f is called monomorphism.
l If group homomorphism f is bijective then, f is called isomorphism.
We can also have, if Y = X, then a mapping
g : X → X
is called an automorphism of X if it is also isomorphism, otherwise it is called endomorphism
of X.