billy-wehring.com

*Note that it’s assumed the reader is familiar with groups and subgroups. *

This article was initially written for a friend of mine when we were both taking abstract algebra 1 together. I hope you find it beneficial!

Have you ever seen a movie where the ending was so amazing that you left the theater feeling excited, energetic, and like you could do anything? For me, those movies are Avengers Endgame and Interstellar. Now I’m not saying that this blog will be like that, but…. it will be! I know that’s a bold statement! (pun intended)

Let me ask you some questions:

When can we guarantee that a group is cyclic? Can we tell whether a subset cannot be a subgroup solely from how many elements it contains? Can we predict the possible orders of elements in a group using, again, solely how many elements the group contains?

We will answer these questions with little effort. Little in the sense that we will prove one thing that leads to the rest. And the way we do so will make the answers soooo transparently obvious that you will wonder why they seem difficult now!

Wait, there’s more! Just like any ‘good’ infomercial…

We will (in another article) develop tools to learn when two groups are secretly the same group G. At that point, we will also develop a way to construct groups that are identical in structure to G. And it all starts with this topic!

Everything above uses this one thing called a COSET!

What’s A Coset?

We will not motivate this definition at all. Mostly, because I am not sure why someone would even think to come up with this other than curiosity at its finest. Well… I have one idea… it comes from number theory…

Definition: (Left/Right Cosets) Let $G$ be a group and $H$ be a subgroup of $G$. Fix an element $g\in G$. We define the left coset of $H$ with representative $g$ to be the set:

$gH: = \{gh\;:\;h\in H\}.$

Likewise, the right coset of $H$ with representative $g$ is the set,

$Hg: = \{hg\;:\;h\in H\}.$

In plain English, find some subgroup $H= \{ e,\;h_1,\;h_2\;\cdots,\;h_n \}$ of some group $G$. Then, fix some $g\in G$. Lastly, multiply all the elements of $H$ with $g$ on the left (or right) to get $gH$ (or $Hg$).

$Hg= \{ eg,\;h_1g,\;h_2g\;\cdots,\;h_ng \} = \{ g,\;h_1g,\;h_2g,\;\cdots,h_ng\}$

For a special case, since $e\in G$ we have $He:= \{ he\;:\;h\in H\} = \{h :h\in H\} = H.$ So any subgroup is a right (and left) coset of that subgroup!

Now I hear you asking: “Why on Earth would we care about a coset?” I thought the same thing, but trust me, the payoff is amazing!

Note: A coset is not necessarily a group/subgroup. A coset is generally a set, just a set. If cosets were able to sing, they’d sing, “I’m just a set. Yes, I’m only a set...” (for those of you who remember School House Rock you get the joke).

Little Lemma

Before we begin, it would be useful to know when two cosets are the same. Meaning, for $a,b\in G$ when is $Ha=Hb?$ This definitely happens when $a=b$, but can it happen when $a\neq b?$ Yes, in general $Ha=Hb$ when $a\in Hb.$

Little Lemma: If $a\in Hb$, then $Ha=Hb$.

Proof: (Click to see proof)

Proof: Let $a\in Hb$. Do you recall how to prove when two sets are the same? We will show (i) $Ha\subseteq Hb$ and (ii) $Hb\subseteq Ha$. This can only happen if $Ha= Hb$.¹

(i) Let’s consider some $x\in Ha$ and show that $x\in Hb$ too.² Since $x\in Ha$, by the definition of a coset, $x$ is of the form:

$x = h_{xa}a$,

for some $h_{xa}\in H.$ Recall, $a\in Hb$ so $a$ has a similar form,

$a = h_{a}b$ ,

where $h_a \in H$ . We can combine these two expressions and deduce:

$x = h_{xa}a =h_{xa}(h_a b) =\underbrace{(h_{xa} h_a)}_{\in H} b \in Hb.$

Since $x$ has the form of: (element from $H$)$b$, we concluded that $x\in Hb$. Thus, $Ha\subseteq Hb$. On to step two.

(ii) Consider another $y\in Hb$. Then, $y = h_{yb}b$ where $h_{yb}\in H$. We already know that $a = h_a b$, which implies

$h_a^{-1}a = h_a^{-1}(h_ab) = ( h_a^{-1}h_a)b =eb = b$

Cleanly written: $b = h_a^{-1}a$. Thus, we conclude,

$y=h_{yb}b = h_{yb}(h_a^{-1}a) = \underbrace{(h_{yb}h_a^{-1})}_{\in H}a \in Ha$.

Since $y$ has the form of: (element from $H$)$a$, we concluded that $y\in Ha$. Therefore, $Hb\subseteq Ha$.

Since (i) $Ha\subseteq Hb$ and (ii) $Hb\subseteq Ha$ we conclude $Ha=Hb$.

$\square$

We’re done! We will use this tool a lot!

Positively Partitioning

We claim that cosets partition all the elements of $G$. This means that every element in $G$ is in one and only one coset. We can picture this by blocking off sections of a group $G$. Each element falls into one of these coset partitions:

Positively Partitioning: Cosets of a subgroup $H$ of a group $G$, partition the set $G$.

Proof: (Click to see proof)

Proof: Since we need every element in $G$ to be in one and only one coset, we have to show two things: (1) two cosets $Ha$ and $H b$ are either equal or disjoint, and (2) every element falls into some coset. To this end, let $Ha$ and $Hb$ be two cosets of $H$. If they are disjoint, then we’re done! So, we will assume they are not disjoint and show they are equal sets.

Since $Ha$ and $Hb$ aren’t disjoint there is some $x\in Ha$ and $x\in Hb$. Then, we know by our Little Lemma that $Ha = Hx$ and $Hb = Hx$. In other words, $Ha = Hx = Hb$.

Almost there, we just need to explain why every element in $G$ is in a coset. Well, isn’t $x\in G$ in the coset $Hx$? Yup! We can see this since $e\in H$ the element $ex = x \in Hx.$

Therefore, cosets partition the set $G$.

$\square$

Cool Correspondence between $Ha$ and $H$.

A fact about cosets, is that there are as many elements in any coset $Ha$ as in the subgroup $H$. This may seem obvious since the elements of $Ha$ are the elements of $H$ multiplied on the right by $a$. Indeed, this is the way to think about it.

There is a more mathy way to state this correspondence:

There is a one-to-one correspondence between elements of $H$ and the elements of $Ha$.

Proof: (Click to see proof)

Proof: Recall that to show a one-to-one correspondence between sets we must find a bijection.³ The first one you might think of, the one that maps $x\mapsto hx$, is one that works.

Let $f: H \rightarrow Ha$ be defined by $f(h) = ha$. We now show that $f$ is bijective.

Injective: Let $f(h_1) = f(h_2)$. It follows $h_1 a = h_2 a$. By multiplying on the right by $a^{-1}$ we conclude $h_1 = h_2$. Thus, $f$ is injective!

Surjective: This one’s not so bad. Let $ha \in Ha$. Then $h\in H$ is such that $f(h) = ha$. Therefore, $f$ is surjective.

Since $f$ is both injective and surjective, it’s bijective.

In conclusion, there is a one-to-one correspondence between elements of 𝐻 and $Ha$. Or, $|H| = |Ha|$.

Short Recap

What have we learned so far?

Well, first off, it hasn’t been that much work to show that cosets partition $G$, and there is a one-to-one correspondence between elements of $H$ and the elements of $Ha$. So, each coset contains the same number of elements. Hence, each of the partitions of $G$ has the same number of elements, since each coset is the same size. This means the image showing cosets of $G$ should have been neater. Sort of like this,

It might be really surprising but we are basically done.

Legendary Lagrange

Lagrange’s Theorem: Let $G$ be a finite group and let $H$ be any subgroup of $G$. Then, the order of $H$ divides the order of $G$. Equivalently, the order of $G$ is a multiple of the order of $H$.

Wowww…. how cool is that?!? Would you have thought that the number of elements in H must divide the number of element in $G$????

Proof: (Click to see proof)

Proof: We’ve already proved it, since the collection of cosets partition $G$ it must be that the order of $G$ is the sum of each of the orders of the cosets,

$|G| = |Ha_1| + |Ha_2| + \cdots + |Ha_n|$.

Where there are $n$ distinct cosets of $H$.Furthermore, $n$ is finite since $|G|$ is finite. But all the cosets have the same order (size) as $H$,

$|G| = |Ha_1| + |Ha_2| + \cdots |Ha_n| = |H| + |H| + \cdots |H| = n|H|$.

So that $|G| = n|H|$ where $n$ is the number of distinct cosets of $H$.

Just like that, we’re done! The reason why this theorem is so cool is because of the quick corollaries it gives.

When is a Group Guaranteed to be Cyclic?

If $G$ has prime order $p$, then every nonidentity element is a generator of $G$. Or, $G$ is cyclic!

Proof: (Click to see proof)

Proof: Let the order of $G$ equal a prime number $p$ and $a\in G$ be a nonidentity element of $G$. Denote the order of $a$ by $|a| = k$. Recall $\langle a\rangle = \{e, a, a^2, \cdots, a^{k-1} \}$ is always a subgroup and $|\langle a\rangle|=|a|=k$ (If you are unfamiliar with these facts, I challenge you to prove them!). By Lagrange’s theorem $k$ divides $p$. This implies $k=1$ or $k=p$ since $p$ is prime.

Wait, if $k=1$ then $a=e$, and we didn’t want $a$ to be the identity! Therefore, $|a| = p$, and $G = \langle a\rangle = \{e, a, a^2, \cdots, a^{p-1} \}$ since they both have $p$ elements!

$\square$

Is there a Subgroup?

Let’s say $|G| = 10$. Can there be a subgroup $H$ of order 4? NO! Since $4\nmid 10$. You can play this game with any $|G| = n$. How awesome!

Well, what if $|G| = p$ is a prime number? Then, the only numbers that divide $p$ are 1 and $p$. Thus $|H| = 1$ or $|H| = p = |G|$.

This means that the only subgroups of $G$ are $H=\{e\}$ and $H=G$ when $G$ has prime order.

Fermat’s Little Theorem

Fermat’s Little Theorem is a corollary too! For those in the know:

Fermat’s Little Theorem: If $p$ is a prime then,

$a^{p-1} \equiv 1 \pmod{p}$.

When $a \in \{ 1,2,3,\cdots, p-1\}$, or when $a$‘s residue falls between 1 and $p-1$.

Proof: (Click to see proof)

Proof: To see this, consider the set $\langle a\rangle = \{e, a, a^2, \cdots, a^{k-1} \}$ again. The set $\langle a\rangle$ with multiplication is a subgroup of $G= \{ 1,\,2,\cdots, p-1\}$ with multiplication. By Lagrange’s theorem, the order of $\langle a\rangle$ must divide the order of $G$, which is $|G| = p-1$. Denote the order of $a\in G$ by $|\langle a\rangle| =|a| =k$ . Thus $k$ must divides $p-1$ and therefore $p-1 = kt$.

Finally,

$a^{p-1} \equiv a^{kt} \equiv (a^k)^t \equiv 1^t \equiv 1 \pmod{p}$.

Boom. Mike drop.

$\square$

Closing Remarks

Lagrange’s theorem is so amazing because it’s both so ‘simple’ and has a ‘how would anyone think of it?’ kind of feeling. I hope you had half as much fun as I did when I learned it for the first time. We’ve barely scratched the surface of it.

Oh, just in case you want some fun too, proving awesome statements/theorems. Try to prove the following:

1. If H and K are subgroups of G with |H| and |K| relatively prime (meaning $\gcd{(|H|,|K|)} = 1$), then $H\cap K = \{e\}$.
2. Euler’s Little Theorem:⁴ Denote the number of positive integers less than $n$ and relatively prime to $n$ by $\phi(n)$.⁵ Then for all $a$ such that $\gcd{(a,n)} = 1$, we have $a^{\phi(n)} \equiv 1 \pmod{n}$.

Leave your proofs in the comments!

Footnotes:

1. This is analogous to numbers. If and , then . ↩︎
2. For two set A and B, by showing implies , it must be that . Can you see why? ↩︎
3. A bijection is a fancy term that means a function that is an injection and surjection. And an injection is a fancy way to say that the element f(x) is unique to x. Or, no two elements and have the same or . This is equivalent to saying:
   INJECTION Criteria: if then .
   And a surjection means that every element in Ha is equal to some f(h).
   SURJECTION Criteria: for any there is some such that . ↩︎
4. This is not the standard name of this theorem! ↩︎
5. The function $\phi(n)$ is called Euler’s Totient function, see chapter 10 in Newbie at Number Theory Book. ↩︎