1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Another proof involving orders of groups. Please help me make this proof air-tight.

  1. Jun 24, 2012 #1
    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=ak for some integer k. Suppose the order of a is n. Hence, an=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=an=aqk+r=aqkar=e.
    From (2), we observe that an=aqkar. Multiplying on the right by a-r, we obtain,
    (3) ana-r=aqk. Then, we have,
    (4) an-r=aqk=e.
    Since an-r=e and 0≤r<n, we must have that r=0. With r=0, from (4), we get,
    (5) an=aqk=(ak)q=bq=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
     
  2. jcsd
  3. Jun 25, 2012 #2
    Re: Another proof involving orders of groups. Please help me make this proof air-tigh

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

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

    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. [itex]b=a^2[/itex], [itex]b^2=a^4[/itex], [itex]b^3=a^6=a[/itex] and so on... We loop around and get back to the identity at [itex] b^5=a^{10}=(a^5)^2=e^2=e[/itex]. 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, [itex]<b>=<a^1>[/itex]. 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 [itex]b=a^2[/itex], [itex]b^2=a^4[/itex], [itex]b^3=a^6[/itex], [b^4=a^8=e], so b is of order 4, and we have that [itex] <b>=<a^2>[/itex]. n=8 and k=2 are not coprime; their gcd is 2.

    That's probably suggestive enough :P
     
  4. Jun 25, 2012 #3
    Re: Another proof involving orders of groups. Please help me make this proof air-tigh

    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=ak. 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?
     
  5. Jun 25, 2012 #4
    Re: Another proof involving orders of groups. Please help me make this proof air-tigh

    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 [itex] b=a^8[/itex]. Computing powers, we get [itex] b^2=a^{16}=a^6[/itex], [itex]b^3=a^{24}=a^4[/itex], [itex]b^4=a^{32}=a^2[/itex], [itex]b^5=a^{40}=(a^{10})^4=e^4=e[/itex]. So the order of b is 5.

    Note that in computing the powers of b, we managed to get [itex] a^8,a^6,a^4,a^2[/itex]and [itex] e[/itex]. So in fact, we can write [itex]<b>=<a^2>[/itex] 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 [itex] <b>=<a^d> [/itex], 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 [itex]<b>=<a^d>[/itex]. Then show that n/d is the smallest positive integer with the property that [itex] b^j=e [/itex] 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 [itex] (a^d)^ja^{dj}=e [/itex] (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?
     
    Last edited: Jun 25, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Another proof involving orders of groups. Please help me make this proof air-tight.
Loading...