Order of an element in a group

In summary: So, I'm not sure what to do with this information...In summary, the conversation discusses how to prove a property about the order of an element in an arbitrary finite group. It is stated that if the group is finite, then the element's order is the smallest natural number that satisfies a certain equation. The conversation includes some thoughts on how to approach the problem, including using the closure of the group and the fact that there are repeated elements in the sequence of powers of the element. A hint is given to use the fact that any integer can be written as a multiple of the order plus a remainder.
  • #1
Bashyboy
1,421
5
Hello everyone,

I am working with an arbitrary finite group ##G##, and I am trying to prove a certain property about the order of an arbitrary element ##g \in G##. Supposedly, if we are dealing with a such a group, then ##o(g)##, which is the cardinality of the set ##| \langle g \rangle |##, is the smallest natural number ##r## such that ##g^r = e##.

Here is some of my thoughts:

If ##G## is a finite group, then there are only a finite number of elements ##g## can generate, meaning that ##\langle g \rangle## is a finite set. Let this set be

##\langle g \rangle = \{g^{-m}, g^{-m+1},...,g^{-2}, g^{-1}. g^0, g^1, g^2,...g^m \}##.

The cardinality of this set is ##2(m+1)##. If I understand the problem correctly, I need to demonstrate that ##g^{2(m+1)} = e##. Is that right?

If this is the case, could anyone provide a hint as to the next step?
 
Physics news on Phys.org
  • #2
The cardinality of that set is 2m+1, which is always odd, but that's moot since you can't assert that the set has that form. Consider ##\mathbb{Z}_2## for example: ##\langle 0 \rangle = \{0\}## while ##\langle 1 \rangle = \{0, 1\}##.
 
  • #3
I didn't say that the cardinality was always odd; I said it was ##2(m+1) = 2m + 2##. So, could you offer any hints?
 
  • #4
##g^1, \dots, g^m## is m elements, and ##g^{-1},\dots,g^{-m}## is m elements. Then you have ##g^0## left over. How did you get 2(m+1)?

In any case, either way, your assumption for the form of the set leads to the conclusion that the cardinality of ##\langle g \rangle## is always even or always odd, independent of ##g##. That's obviously not true. I gave you a simple counter-example. You have to fix that first before you can go on.
 
Last edited:
  • #5
vela said:
...depending on whether you can count correctly...

I find that slightly rude. At any rate, I realize that you gave a counter-example, and I concede to its truth.

vela said:
You have to fix that first before you can go on.

What exactly are referring to that needs to be fixed?
 
  • #6
Well, I still have not been able to figure out how to begin. Could anyone possibly proffer a hint?
 
  • #7
Okay, here are some ideas: The previous problem that I worked on was to show that, if ##g## was an element in the finite group ##G##, then there is a natural number ##m## such that ##g^m = e##, where ##e## is ##G##'s identity.

This is how I proved that problem (Note, this is a rough draft, and so it contains my intuition of the problem and the actual proof):

Because of closure, we know that, if ##g \in G##, then any finite sequence of ##\star## operating on ##g## will be in ##G##; that is, ##g^n \in G~~~\forall n \in \mathbb{Z}##. We also know that ##g^n \in \langle g \rangle##, because by definition this set ##\langle g \rangle## contains all of the finite sequences of ##\star## operating on ##g##.

There are two cases, either ##g## generates all of the elements of ##G##, ##\langle g \rangle = G##; or ##g## generates some of the elements of ##G##, ##\langle g \rangle \subset G##. In either case, we see that ##\langle g \rangle## is finite. This can also be argued as follows: because ##G## has closure, ##g \star g = g^2## gets mapped to some element in ##G##; ##g \star g \star g = g^3## gets mapped to some (other?) element in ##G##. Eventually, this process will terminate, because ##g## will have generated all of the elements it can, which is either some of the elements of ##G## or all of them. Basically, ##g## will eventually run out of elements it can generate. Therefore, there must be a "last" finite sequence (or last power) of ##g## which generates the "last" element of ##G##, to which we could give the same ##g^n##.

Now, because ##\langle g \rangle## contains all of the finite sequences of ##\star## acting on ##g##, then it must also contain ##g^k##, where ##k \notin \{1,2,3...,n \}##. Because there are no more "new" elements to generate, ##g^k## must generate one of the elements that has already be generated by one of the powers ##\{1,2,3,4,...,n\}##. Thus, ##g^k## must equal one of the ##g^i##, where ##i \in \{1,2,3,4...,n\}##.

##
g^k = g^i \iff
##

##
g^k \star g^{-i} = e \iff
##

##
g^{k-i} = e
##

So, in addition to ##g^0 = e##, we have ##g^{k-i} = e##, where ##k-j > 0 \in \{1,2,3,4...,n\}##. Thus, the mapping repeats for certain integer exponents.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

So, we see that the powers of the elements in ##\langle g \rangle## are distinct, and for certain integer powers repetition occurs. I know that I need to use these two ideas for the current problem, but I cannot figure this out. Clearly I am actually attempting at solving this problem, and not merely asking someone else to do it for me. Could someone help me?
 
  • #8
You want to show there is a natural number such that ##g^m=e##. You know that there must be repeat elements in the sequence ##g^1, g^2, g^3, g^4 ...##. So suppose ##g^i=g^j## with ##i<j##. Now what?
 
  • #9
Hi, Dick. I have already shown that there exists a natural number ##m## such that ##g^m = e## (refer to post #7). Now I am trying to prove the theorem given in my first post, that the order of the element ##g## (the cardinality of ##\langle g \rangle##) is the smallest positive integer that satisfies ##g^r = e##.
 
  • #10
Bashyboy said:
Hi, Dick. I have already shown that there exists a natural number ##m## such that ##g^m = e## (refer to post #7). Now I am trying to prove the theorem given in my first post, that the order of the element ##g## (the cardinality of ##\langle g \rangle##) is the smallest positive integer that satisfies ##g^r = e##.

Ok, here's a hint. You know that for any integer n that n=jr+k for some integers j and k with 0<=k<r.
 
  • #11
OKay, so I could write ##g^n = g^{jr + k}##...I have actually tried this already, but I couldn't figure out what to do with it. I tried rearranging things, but I wasn't sure what I could infer.

For instance, I wrote ##g^{n-k} = g^{jr}###, but this didn't seem very helpful. Wouldn't ##n-k \in \{1,2,3,4,...,n-1\}##? What about ##jr##?
 
  • #12
Bashyboy said:
OKay, so I could write ##g^n = g^{jr + k}##...I have actually tried this already, but I couldn't figure out what to do with it. I tried rearranging things, but I wasn't sure what I could infer.

For instance, I wrote ##g^{n-k} = g^{jr}###, but this didn't seem very helpful. Wouldn't ##n-k \in \{1,2,3,4,...,n-1\}##? What about ##jr##?

You want to use that to show every ##g^n## is equal to ##g^k## for some k in {0,1,2,3,...,r-1}. What is ##g^{jr}##?
 
  • #13
Wait? Why do we care about the set ##\{0,1,2,3,...,r-1\}##. Aren't we interested in the set ##\{0,1,2,3,...,n-1\}##? Would either ##j## or ##r## be in ##\{0,1,2,3,...,n-1\}##. Would writing either ##(g^r)^j## or ##(g^j)^r## be helpful?
 
  • #14
Bashyboy said:
Wait? Why do we care about the set ##\{0,1,2,3,...,r-1\}##. Aren't we interested in the set ##\{0,1,2,3,...,n-1\}##? Would either ##j## or ##r## be in ##\{0,1,2,3,...,n-1\}##. Would writing either ##(g^r)^j## or ##(g^j)^r## be helpful?

If you can show every power of g is equal to some ##g^k## for k in ##\{0,1,2,3,...,r-1\}##, then haven't you taken a step to showing ##<g>## contains r elements? And yes, writing the exponents like that is useful. Try it...
 
  • #15
Oh, okay. Just a minor confusion. I denoted the set ##\langle g \rangle## as ##\{g^0, g^1,...,g^{n-1} \}##, so wouldn't that mean there are ##n## elements, and therefore ##n## distinct powers of ##g##? These powers of ##g## are contained in the set ##\{0,1,2,3,...,n-1\}##? But you are denoting the set as ##\{0,1,2,3,...,r-1\}##?
 
  • #16
Bashyboy said:
Oh, okay. Just a minor confusion. I denoted the set ##\langle g \rangle## as ##\{g^0, g^1,...,g^{n-1} \}##, so wouldn't that mean there are ##n## elements, and therefore ##n## distinct powers of ##g##? These powers of ##g## are contained in the set ##\{0,1,2,3,...,n-1\}##? But you are denoting the set as ##\{0,1,2,3,...,r-1\}##?

Put that way, your job is to show n=r. I would forget about the 'n' stuff. It's not very clearly defined. Let's just finish this, ok?
 
  • #17
What do you mean by, "forget about the 'n' stuff?" Are we to not begin with ##n=jr+k##? I am terribly sorry, but I just having a difficult time trying to finish this proof. I have been working on it for many days.
 
  • #18
Bashyboy said:
What do you mean by, "forget about the 'n' stuff?" Are we to not begin with ##n=jr+k##? I am terribly sorry, but I just having a difficult time trying to finish this proof. I have been working on it for many days.

That n wasn't meant to have anything to do with the group order. It was supposed to mean 'any integer'. Sorry. Now let's start again. Let's call ##G_r=\{g^0, g^1, ... g^{r-1}\}## where r is the order of g. You want to show ##G_r=<g>##, yes? Let ##g^a## be any element of <g>. Can you show it's in ##G_r##? Use that ##a=jr+k## for some j and k, as before.
 
  • #19
I don't think the problem is asking me to show if ##g## generates the group ##G_r##. We want to show that the order of ##g## satisfies ##g^{order} = e##
 
  • #20
Bashyboy said:
I don't think the problem is asking me to show if ##g## generates the group ##G_r##. We want to show that the order of ##g## satisfies ##g^{order} = e##

Sorry again. I didn't say that quite right. r is supposed to be the smallest natural number such that ##g^r=e##. Now if you could show ##<g>=G_r## and that ##G_r## has r elements, wouldn't that solve the problem? The problem isn't asking you to prove it, I'm suggesting you prove it as a way to solve the problem.
 
  • #21
Ah, so we want to start out with the supposition that ##r## is the smallest natural number such that ##g^r = e##; and then show that this natural number just so happens to be the order of ##g##? So, do I basically need to show that there are ##r## distinct elements in ##\langle g \rangle##?
 
  • #22
Bashyboy said:
Ah, so we want to start out with the supposition that ##r## is the smallest natural number such that ##g^r = e##; and then show that this natural number just so happens to be the order of ##g##? So, do I basically need to show that there are ##r## distinct elements in ##\langle g \rangle##?

Yes, exactly. I suggest you attack it by showing ##G_r=\langle g \rangle##.
 
  • #23
Okay, so clearly ##G_r## is a subset of ##\langle g \rangle##, because ##\langle g \rangle## contains all of the finite sequences of ##\star## acting on ##g##, and ##G_r## contains some of those finite sequences.

As we said ##\langle g \rangle## contains all of the finite sequences of ##g##; thus, ##g^a \in \langle g \rangle##. By the division algorithm, we can relate the integers ##a## and ##r## as follows: ##a = jr + k##, where ##0 \le k \le r-1##. Therefore,

##g^a = g^{jr + k} \iff##

##g^a = g^{jr} g^k \iff##

##g^a = (g^r)^j g^k \iff##

But we assumed that ##r## was the smallest natural such that ##g^r = e##; thus,

##g^a = e^j g^k \iff##

##g^a = g^k##

Because ##k## can only be an integer between ##0## and ##r-1## (inclusive), so, too, can only a be one of those integers. Therefore, ##\langle g \rangle## consists of the ##g##'s whose exponent is ##\{0,1,2,3,4,...,r-1\}##. This shows that ##\langle g \rangle = G_r##

Is this correct?
 
  • #24
Bashyboy said:
Okay, so clearly ##G_r## is a subset of ##\langle g \rangle##, because ##\langle g \rangle## contains all of the finite sequences of ##\star## acting on ##g##, and ##G_r## contains some of those finite sequences.

As we said ##\langle g \rangle## contains all of the finite sequences of ##g##; thus, ##g^a \in \langle g \rangle##. By the division algorithm, we can relate the integers ##a## and ##r## as follows: ##a = jr + k##, where ##0 \le k \le r-1##. Therefore,

##g^a = g^{jr + k} \iff##

##g^a = g^{jr} g^k \iff##

##g^a = (g^r)^j g^k \iff##

But we assumed that ##r## was the smallest natural such that ##g^r = e##; thus,

##g^a = e^j g^k \iff##

##g^a = g^k##

Because ##k## can only be an integer between ##0## and ##r-1## (inclusive), so, too, can only a be one of those integers. Therefore, ##\langle g \rangle## consists of the ##g##'s whose exponent is ##\{0,1,2,3,4,...,r-1\}##. This shows that ##\langle g \rangle = G_r##

Is this correct?

Yes, now just one more thing. Can you show ##G_r## has r distinct elements? It's written like it does, but some of those might be duplicates. Why are they all different?
 
  • #25
Wouldn't it just follow from the fact that all of ##\langle g \rangle##'s elements are distinct, which I in post #7?
 
  • #26
Bashyboy said:
Wouldn't it just follow from the fact that all of ##\langle g \rangle##'s elements are distinct, which I in post #7?

No. Give me a proof they are distinct. Suppose ##g^i=g^j## with i<j<r. Then what?
 
  • #27
So, we are suppose the opposite, that they are not distinct, hoping to find some contradiction?

##g^i = g^j \iff##

##e = g^{j-i}##, where ##0 < j-i < r \iff 0 < j-i \le r - 1##.

I don't see the contradiction.
 
  • #28
Bashyboy said:
So, we are suppose the opposite, that they are not distinct, hoping to find some contradiction?

##g^i = g^j \iff##

##e = g^{j-i}##, where ##0 < j-i < r \iff 0 < j-i \le r - 1##.

I don't see the contradiction.

Look at the definition of r. It's supposed to be the SMALLEST something.
 
  • #29
Oh, good heavens! Of course, so ##j-i## is an integer smaller than ##r##, which also results in ##g^{something}## being ##e##. Therefore, a contradiction.
 
  • #30
I am sorry to rehash this again, but I am having trouble with one argument I made:

Bashyboy said:
##g^a=e^jg^k⟺g^a = e^j g^k \iff##

##g^a=g^kg^a = g^k##

Because ##k## can only be an integer between ##0## and ##r−1## (inclusive), so, too, can only ##a## be one of those integers. Therefore, ##\langle g \rangle## consists of the ##g##'s whose exponent is ##\{0,1,2,3,4,...,r-1\}## This shows that ##\langle g \rangle = G_r##

I don't see why this implies that ##a## and ##k## have to have the same exponent. Isn't it possible that ##k > a##, yet ##g^k## and #g^a## get mapped to the same element?
 
  • #31
Bashyboy said:
I am sorry to rehash this again, but I am having trouble with one argument I made:
I don't see why this implies that ##a## and ##k## have to have the same exponent. Isn't it possible that ##k > a##, yet ##g^k## and #g^a## get mapped to the same element?

Correct. I didn't read closely enough. ##g^k=g^a## doesn't mean k and a are the same. Just the powers of g are the same. Omit that statement and the rest is fine.
 
  • #32
I am not sure how I can conclude ##\langle g \rangle## and ##G_r## are the same set, then. Haven't I only demonstrated that ##G_r## is a subset?
 
  • #33
Bashyboy said:
I am not sure how I can conclude ##\langle g \rangle## and ##G_r## are the same set, then. Haven't I only demonstrated that ##G_r## is a subset?

Haven't you shown that for any a, ##g^a=g^k## for some k in {0,1,...,r-1}? Isn't that enough?
 
  • #34
Oh, and so this forces them to be equal, and it forces the exponents of ##\langle g \rangle##, without any repetition, to be {0,1,2,3...,r-1}. Is that right?
 
  • #35
Bashyboy said:
Oh, and so this forces them to be equal, and it forces the exponents of ##\langle g \rangle##, without any repetition, to be {0,1,2,3...,r-1}. Is that right?

What do you mean 'without repetition'? ##g^a## is in ##G_r## for any a. So ##\langle g \rangle## is contained in ##G_r##. Isn't that clear?
 
  • Like
Likes Bashyboy

Related to Order of an element in a group

What is the definition of "order of an element in a group"?

The order of an element in a group refers to the number of times the element must be combined with itself using the group's operation to result in the identity element.

How is the order of an element in a group determined?

The order of an element can be determined by finding the smallest positive integer n such that the element raised to the power of n results in the identity element.

What is the significance of the order of an element in a group?

The order of an element in a group can provide important information about the structure of the group and its subgroups. It can also be used to classify groups and determine their properties.

Can the order of an element in a group be infinite?

Yes, the order of an element in a group can be infinite if the element has an infinite number of powers that result in the identity element.

How does the order of an element in a group relate to the order of the group itself?

The order of an element in a group must be a factor of the order of the group. This means that the order of the group is a multiple of the order of any of its elements.

Similar threads

Prove that every subset ##B## of ##A=\{1,...,n\}## is finite
Replies
4
Views
753
Normal subgroup generated by a subset A
Replies
15
Views
2K
Prove ##1 + a=s(a)=a+1## for ##a \in \mathbb{N}##
Replies
1
Views
828
Minimize integral using orthogonal basis
Replies
2
Views
698
Prove ##a + b = b + a## using Peano postulates
Replies
3
Views
1K
Prove ##a \cdot 1 = a = 1 \cdot a## for ##a \in \mathbb{N}##
Replies
1
Views
858
Characterizing subgroups of a cyclic group
Replies
9
Views
1K
Some conclusions give that |G| = nm
Replies
4
Views
947
Show that given conditions, element is in center of group G
Replies
1
Views
1K
Prove ##(a+b)\cdot c=a\cdot c+b\cdot c## using Peano postulates
Replies
3
Views
915

Hot Threads

Recent Insights

Back
Top