Group Theory Computational Exercise: Order of an Element of a Group

Group Theory Computational Exercise: Order of an Element of a Group

 

7/2/17 Robleh Wais

Summary:

Undergraduate mathematics majors that take a course in Group Theory study the properties of objects known as groups. Groups have four defining axioms.

         A group is a set G that is closed under a binary operation (like + or *)

         The set G has an identity element e, such that element a*e= a

         The members of set G are associative, that is, for three members a, b, and c the following equality holds: (a*b)*c = a*(b*c)

         For every a in G, there exists an element a^-1 such that a* a^-1= e (Inverse Identity)

 

In number theory, a subdivision of mathematics associated with Group Theory, groups are composed of integers that have an even more intriguing property, called the order of an element. This property is an integer that represents a count of successive exponentiations of an integer member in a group until it terminates in the identity element of the group. It is performed on a modulus of a group. Below, I illustrate several examples of this computation and give some details on how to calculate the order of an element in a group correctly.

The first step is to enumerate the elements of the group depending on the modulus chosen. The enumeration is accomplished by listing the elements of the group in ascending order that are relatively prime and less than the given number. Relatively prime means that none of the elements have more than 1 or themselves as a divisor.

 Example U(10) = (1,3,7,9)

Note: If you are unsure of the elements of a group under modulo you can find them by performing the operations below for each element less than N, the group cardinality. If the number does not eventually come to 1, the identity element is not a part of the group. In the case below, the numbers 2,4,6,8 are not part of the group U(10). The numbers 2 and 5 are not part of the group because they don't satisfy the condition of being a number less than the group cardinality and relatively prime to it. Since 2 divides 10 evenly there is no remainder, so it's not relatively prime to 10.

To find the order of these elements calculate successive exponentiations of that element until the identity element is reached, i.e.,1. The calculation is based on the modulus of the group. In the above case, the mod is 10. Add the exponentiations and the sum is the order of that element in the modulus group.

What is the order of the elements in U(10) above?

Let's compute each element except 1, which is a trivial case. The order of 3 in mod 10 is

3¹= 3, 3² = 1.So, the order of 3 is 2, the sum of each exponentiation performed.

The order of 7 in mod 10 is

7¹=7, 7²=9, 7³=3, 7⁴=1 So, the order of 7 is 4

 

The order of 9 in mod 10 is

9¹=9, 9²=1. The order of 9 is 2

 We can practice this with other groups. Let's choose another group at random, find its elements, and then calculate the order of each element in the group.

How 'bout an easy one?

U(6)= (1, 5). 2, and 3 are out because they evenly divide 6, and 4 is out because it is not relatively prime with 6 since 2 divides 6 and 4.

Again, 1 is trivial so we'll skip it.

The order of 5 in mod 6 is

5¹=1, the order is 1 since 6-5=1

Now for a more expansive group, we'll tackle U(21). We can find which elements are in the group by simply trying those we are not sure of after we eliminate the obvious ones. Anything that divides 21 evenly is not in the group. So, 3 and 7 are out. Of course, 1 is trivial. We can start with the following and eliminate anything for which successive exponentiations do not result in the identity element. The mod is 21.

U(21)=(2,4,5,8,10 not all elements are listed here)

The calculation of the order of 2 mod 21 is

2¹=2, 2²=4, 2³=8, 2⁴=16, 2⁵=11, 2⁶=1

The order of 2 mod 21 is 6

Is 4 in the group? Let's find out

4¹=4, 4²=16, 4³=1 It is, and the order mod 21 is 3

Note: a computational trick is to compute the power over the mod, divide by the mod, drop the remainder, and multiply the result by the mod. Then subtract this result from the original mod if you get one, you're finished. Let's see this in action above with 4.

4³= 64/21=3.0476. drop the remainder it is 3. 3*21=63. 64-63=1

This applies after you've exceeded the value of the modulus number.

Let's try 5.

5¹=5, 5²=3, 5³=20, 5⁴=16, 5⁵=17, 5⁶=1 (using the technique shown above 5⁶=15625/21=744.0476 ≈744*21=15624; 15625-15624=1)

The order of 5 mod 21 is 6

Let's try 6

This computation never results in the identity element, and thus 6 is not in the group. And it is true because 6 and 21 have more than 1 as prime divisors; they share 3. The same is true for 9, 12, 14, 15 and 18. These numbers share other divisors with 21. For instance, 14 has 7 as a divisor. Try the computation above on any of these elements, and it will never reduce to the identity element 1. What is left in our group after these realizations?

U(21)= (2,4,5, 8,10,11,13,16,17,19,20)

All the above numbers should reduce to the identity element after successive exponentiations of each element. But, since you don't believe me, and I don't believe me we'll do them all.

Alrighty?

 

8¹=8, 8²=1. The order of 8 mod 21 is 2

 

10¹=10, 10²=16, 10³=13, 10⁴=4, 10⁵=19, 10⁶= 1 The order of 10 mod 21 is 6

So far, so good

11¹=11, 11²=16, 11³=8, 11⁴=4, 11⁵=2, 11⁶=1. The order of 11 mod 21 is 6

13¹=13 13²=1 The order of 13 mod 21 is 2

16¹=16, 16²=4, 16³=1 The order of 16 mod 21 is 3

17¹=17, 17²=16, 17³=20, 17⁴=4, 17⁵=5, 17⁶=1 The order of 17 mod 21 is 6

 

19¹=19, 19²=4, 19³=3, 19⁴=16, 19⁵=10, 19⁶=1 The order of 19 mod 21 is 6

 

20¹=20, 20²=1 The order of 20 mod 21 is 2

There you have it, a relatively large collection of ordinal elements. There are no more elements of order in this group, and just as obviously, this is a finite group. We can build a subset collection of elemental ordinals for U(21). Here they are:

U(21)_ordinals = (2,3,6). Notice that this set is composed of only 3 members. Since the members occur repeatedly in the ordinal calculations, only their unique occurrences have been kept.

Now there is a lot more I could say about this result. What does it imply? What if we don't remove the ordinals that occurred repetitively? Are there any cyclic implications in these calculations? But I'll leave all these questions for another essay.

Return to Portal List of Articles

The Existential Concept The Existential Concept

Here is a short musical piece I wrote as an interpretation of the reversal of the Norm on a Banach Space. Reverse Norm Song

Graph Theory and mapping the reversed letters of common English words has become a new interest to me.

Read the short intro below, 

and maybe you will be intrigued too. Reversed English Words And Graph Theory

How the RSA Algorithm Works

RSA Algorithm