Order of an element in a group

[Bashyboy]

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?

 

[vela]

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\}$.

 

[Bashyboy]

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?

 

[vela]

$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.

 

[Bashyboy]

...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.

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

What exactly are referring to that needs to be fixed?

 

[Bashyboy]

Well, I still have not been able to figure out how to begin. Could anyone possibly proffer a hint?

 

[Bashyboy]

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?

 

[Dick]

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?

 

[Bashyboy]

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$.

 

[Dick]

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.

 

[Bashyboy]

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$?

 

[Dick]

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}$?

 

[Bashyboy]

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?

 

[Dick]

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...

 

[Bashyboy]

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\}$?

 

[Dick]

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?

 

[Bashyboy]

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.

 

[Dick]

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.

 

[Bashyboy]

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$

 

[Dick]

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.

 

[Bashyboy]

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$?

 

[Dick]

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$.

 

[Bashyboy]

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?

 

[Dick]

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?

 

[Bashyboy]

Wouldn't it just follow from the fact that all of $\langle g \rangle$'s elements are distinct, which I in post #7?

 

[Dick]

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?

 

[Bashyboy]

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.

 

[Dick]

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.

 

[Bashyboy]

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.

 

[Bashyboy]

I am sorry to rehash this again, but I am having trouble with one argument I made:

$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?

 

[Dick]

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.

 

[Bashyboy]

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?

 

[Dick]

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?

 

[Bashyboy]

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?

 

[Dick]

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?