Proof of Order of b is a Factor of the Order of a in Cyclic Groups

[jmjlt88]

Proposition: If G= <a> and b ϵ G, then the order of b is a factor of the order of a.
Proof:
Let G be a group generated by a. That is, G=<a>. Let b ϵ G. Since G is cyclic, the element b can be written as some power of a. That is, b=a^k for some integer k. Suppose the order of a is n. Hence, aⁿ=e. We wish to show that the order of b is a factor of n. First, we shall divide n by k using the Division Algorithm. That is,
(1) n=qk+r for some integer q and 0≤r<n.
Then, we have,
(2) e=aⁿ=a^qk+r=a^qka^r=e.
From (2), we observe that aⁿ=a^qka^r. Multiplying on the right by a^-r, we obtain,
(3) aⁿa^-r=a^qk. Then, we have,
(4) a^n-r=a^qk=e.
Since a^n-r=e and 0≤r<n, we must have that r=0. With r=0, from (4), we get,
(5) aⁿ=a^qk=(a^k)^q=b^q=e.
Hence, the order of b is q and by (5), n=qk. That is, q|n and we have that the order of b is a factor of the order of a.
QED

 

[christoff]

I'm not sure how you got line (4)... Why does a^{qk}=e ? You end up concluding that the order of b is q by this reasoning, but here is a contradictory example.

Consider G=C_5, where b=a^2 as in your problem. Then n=5, k=2, so division algorithm gives us n=5=2\times 2 + 1 = 2k+1. You would conclude that the order of b is q=2, but b^2=a^4\neq e.

Back to the problem. You're trying to prove that the order of b is a factor of n. Why did the above example go wrong? Because k doesn't divide n... Let's do some calculations. b=a^2, b^2=a^4, b^3=a^6=a and so on... We loop around and get back to the identity at b^5=a^{10}=(a^5)^2=e^2=e. So in fact, the order of b is 5.

How does this help us? Both b and a are of order 5, so in fact, we aren't cheating when we say that the cyclic group generated by b is the same as that generated by a. More suggestively, &lt;b&gt;=&lt;a^1&gt;. In this example, we had n=5 and k=2. n and k are coprime, so their gcd is 1.

Another quick example. Let's say n=8 and k=2. So b=a^2, b^2=a^4, b^3=a^6, [b^4=a^8=e], so b is of order 4, and we have that &lt;b&gt;=&lt;a^2&gt;. n=8 and k=2 are not coprime; their gcd is 2.

That's probably suggestive enough :P

 

[jmjlt88]

Thank you Christoff!

I'll get back to you later with the revised solution. But, for now, let me make sure I understand it intuitively.

So, we let b=a^k. Now, k can either divide n, the order of a, or n and k can be relatively prime. If they are relatively prime, then the order of b and the order of a are the same [...but how can I justify this statement?]. Or else, k divides n and a logical progression similar to the above may work. Do I have the right idea?

 

[christoff]

Indeed, if k divides n, then the division algorithm immediately gives you r=0, so your proof is fine. But there's another scenario that can come up. What if k doesn't divide n, but they are NOT coprime?

Let's try n=10 and k=8. So we are interested in the order of b=a^8. Computing powers, we get b^2=a^{16}=a^6, b^3=a^{24}=a^4, b^4=a^{32}=a^2, b^5=a^{40}=(a^{10})^4=e^4=e. So the order of b is 5.

Note that in computing the powers of b, we managed to get a^8,a^6,a^4,a^2and e. So in fact, we can write &lt;b&gt;=&lt;a^2&gt; since taking powers up to the fifth of a^2 will get you all of these elements. Notice that gcd(8,10)=2, and further, that the order of b is 10/2=5.

I claim that if gcd(n,k)=d, then &lt;b&gt;=&lt;a^d&gt;, and that the order of b is n/d, which of course divides n (which you were supposed to prove).

To prove this, you will first need to prove the two-sided inclusion &lt;b&gt;=&lt;a^d&gt;. Then show that n/d is the smallest positive integer with the property that b^j=e for some integer j. This second statement is a bit trickier, so here's another way of going about it...

The order of b is EQUAL to the order of the cyclic subgroup generated by it (if you haven't seen this, prove it. It isn't too difficult). So the order of b will be the smallest integer j such that (a^d)^ja^{dj}=e (by the nice little equality <b>=<a^d>). But n is the smallest integer such that a^n=e. Remember that d=gcd{n,k)...

Got it?