Today, to wrap things up, we will use Lagrange’s Theorem to prove that if is an element of the group , the order of evenly divides the order of .
So we have a group and an element . In order to apply Lagrange’s Theorem we need a subgroup. Where are we going to get one of those? We will have to make one using .
Suppose , that is, is the smallest natural number such that . Then consider the set
We will denote this set by . Clearly is a subset of . But I claim it is actually a subgroup!
To prove this, let’s first introduce the notation . This fits nicely: for example, notice that for positive and , we have ; this property continues to hold even when or are if we define . (As an aside, notice this also fits nicely with the notation for the inverse of —and we can extend it to .) With this notation, our set is just . Now, let’s show that is a subgroup of :
- It is obviously nonempty.
- It is closed under the group operation. Generally speaking, . If then all is well. On the other hand, if ends up greater than , we can always subtract until we are left with something less than , since . For example, if , then . In general, we can say that . You might notice that this is very much like the group we have been using as an example—in fact, when the group is isomorphic to (that is, in some sense they are really “the same” group); more generally, if then is isommorphic to , since powers of are added .
- It has inverses: the inverse of is , since . (This makes sense even when .)
This subgroup is called the cyclic subgroup generated by . In any group, we can generate a subgroup from each element in this way (though the same cyclic subgroup may be generated by multiple distinct elements). For example, in the group , the element generates the trivial one-element subgroup; generates the subgroup ; and both generate the subgroup ; and , , , and all generate the entire group , as you can check.
One more important thing to note is that every element of is distinct: remember, if then —but is the smallest power of that is equal to the identity. So this group really does have distinct elements.
Now we have a subgroup of , and Lagrange’s Theorem tells us that its order must be a divisor of the size of . But the order of is the same as the order of , that is, . So the order of any element must divide the order of the whole group.
And that concludes MaBloWriMo! This month of posting every day has been a lot of fun—I’m very glad I took up the challenge! I have these grand visions of stuff I want to write about, but often get bogged down writing long, monolithic posts, or sometimes I am just intimidated by the thought of it and never even start. This month, it was freeing to realize that the world would not end if I just post things in smaller chunks, perhaps without quite so much advance planning or editing. Posting frequently also meant I could maintain a lot more momentum—writing the individual posts went pretty quickly, since everything was still fresh in my head. Paradoxically, it seems that upping the posting frequency actually made things easier.
So I certainly can’t keep writing a post per day. But going forward I have decided to commit to two posts per week—I think that will be manageable while still taking advantage of the momentum generated by more frequent posting. I’m excited—I’ve got a bunch of ideas for things I want to write about, some new, and some that have been on the list for years. A small sampling: I want to explain the million-dollar P vs NP problem; write about the proof of the four-color theorem; finish my long-languishing series of posts on a certain combinatorial proof; and write some addenda to my series on hyperbinary numbers. I hope you enjoy—and please do continue to send ideas of things you might like me to write about!