Subsubsection 8.3.3.1 Solutions to equations
Since a group has inverses, we can solve very simple ‘linear’ equations in them. This is stated as
\begin{equation*}
a*x=b\text{ is solved by }x=a'*b\text{ } (=a^{-1}*b)\text{.}
\end{equation*}
For instance, over \(\mathbb{R}\text{,}\) \(a+x=b\) always has a solution for any real numbers \(a,b\text{.}\) We just take \(x=(-a)+b\text{,}\) where \(-a\) is the inverse for the group operation of \(a\) (as mentioned above).
More important to us is the fact that in \(\mathbb{Z}_{n}\text{,}\) there are solutions. The operation is still \(+\text{,}\) so we have \(a+x\equiv b\) mod(\(n\)) solved by \(x\equiv ((-a)+b)\) mod(\(n\)).
This doesn’t seem much more interesting, but you will see soon why this concept is so important.
Subsubsection 8.3.3.3 Finite groups
A group can have finitely many or infinitely many elements. Most of our normal ones, such as \(\mathbb{Z}, \mathbb{Q}, \mathbb{R}\text{,}\) matrix groups, are infinite.
But the ones we’ll use in this text will mostly have finitely many elements. This is because we are counting each equivalence class, like \([0],[1],[2]\) in (mod \(3\)) arithmetic, as just one element.
A group with finitely many elements is called, unimaginatively, a finite group.
Subsubsection 8.3.3.5 Order of an element
This is a tougher concept. Suppose you have some element, such as \([1]\in \mathbb{Z}_{3}\text{.}\) If you just keep adding \([1]\) to itself, eventually you get back to zero, right? After all,
\begin{equation*}
[1]+[1]+[1]\equiv [0]\text{ (mod }3\text{).}
\end{equation*}
Take a finite group \(G\) with order \(|G|=n\text{.}\) We will bring the concept of order to elements, not just groups.
First, list all elements of the group:
\begin{equation*}
\{e=x_{1}, x_{2}, \ldots,x_{n}\}
\end{equation*}
Now let’s take an element \(x\text{,}\) and start operating on it by itself. What I mean by this is listing \(x,x*x=x^{2},x^{3},\ldots\text{.}\) (Don’t be confused by the power notation alternating with addition notation; \(\mathbb{Z}_{n}\) has two operations, so we keep \(+\) there, but in a general group we use multiplicative notation.)
Here is the key. There are only finitely many elements in the group, so by \(x^{n+1}\) at the latest, at least two of these ‘powers’ will be equal. (This argument, that if you fit \(n+1\) objects into \(n\) slots then there must be a repeat, is called the pigeonhole principle, among other names.)
To be concrete, let’s say \(x^{s}=x^{t}\text{,}\) with \(s\lt t\text{.}\) Now we can do a very curious thing. Take the inverse of \(x\text{,}\) written \(x^{-1}\text{.}\) If we multiply it together \(s\) times, we get \((x^{-1})^{s}\) which we can write \(x^{-s}\text{.}\) Then multiply \(x^{s}=x^{t}\) by \(x^{-s}\text{;}\)
\begin{equation*}
x^{-s}x^{s}=x^{-s}x^{t}\text{, or }e=x^{t-s}\text{.}
\end{equation*}
We are almost there! This means there is a positive integer
\(k\) such that
\(x^{k}=e\text{.}\) By the Well-Ordering Principle (
Axiom 1.2.1), there is a
least such integer. This integer, associated to a specific element of the group, is what we have been aiming for.
Definition 8.3.10.
For a group element \(x\in G\text{,}\) the least (positive) integer \(k\) such that \(x^k = e\) is called the order of the element \(x\text{.}\) We write it \(|x|\text{,}\) by analogy with the order of a group.
Example 8.3.11.
For example, in \(\mathbb{Z}_{6}\text{,}\) look at the element \([4]\text{.}\) We see that
\begin{equation*}
[4]+[4]+[4]+[4]+[4]+[4]\equiv [0] \text{ mod(6), but }[4]+[4]+[4]\equiv [0] \text{ mod(6) too}\text{.}
\end{equation*}
So while \(6\) might look like a possibility for the order of \([4]\text{,}\) we see that clearly \(3\) is actually the smallest (positive) number of times to add \([4]\) to get \([0]\text{.}\) So \(|[4]|=3\text{.}\)
Subsubsection 8.3.3.6 The connection
Here comes the coolest part, where we connect the two concepts of order. We will definitely use
Theorem 8.3.12 in proving various theorems.
Take a look at any old element \(x\in G\text{.}\) If \(x\) has order \(m\text{,}\) then there are (at least) \(m\) distinct elements of \(G\text{,}\)
\begin{equation*}
\{x,x^{2},x^{3},\ldots,x^{m-1},e\}\text{.}
\end{equation*}
Now take any other element not in this subset, \(y\text{,}\) and look at the set
\begin{equation*}
\{xy,x^{2}y,x^{3}y,\ldots,x^{m-1}y,ey=y\}\; ;
\end{equation*}
Note that these are also all distinct elements of the group. Are any of them also included in the first set (powers of \(x\))?
Suppose that some \(x^s y\) is the same as some \(x^t\text{.}\) That would mean \(x^{s}y=x^{t}\text{,}\) so multiplying by \(x^{-t}\) we get
\begin{equation*}
x^{s-t}y=e
\end{equation*}
That would mean \(y=x^{t-s}\text{,}\) a contradiction since we said \(y\) isn’t a power of \(x\text{.}\) Hence the new elements form a disjoint set from the previous set.
Now find an element \(z\) not in either set, and do the same thing. Then the set
\begin{equation*}
\{xz,x^{2}z,x^{3}z,\ldots,x^{m-1}z,ez=z\}
\end{equation*}
will be disjoint from the other sets, and all its elements will still be distinct. Since \(G\) is finite, eventually doing this process again and again will fill out \(G\) completely.
Theorem 8.3.12. Lagrange’s Theorem on Group Order.
The order of any element \(x\) of \(G\) divides the order of the group itself. We can write this as
\begin{equation*}
|x|\mid |G|
\end{equation*}
Proof.
Examine the above argument. We have a number of subsets of \(G\text{,}\) all of size \(m\text{,}\) which exactly fill out \(G\text{,}\) which has size \(n\text{.}\) This forces that \(m\) divides \(n\) as integers.
Example 8.3.13.
For example, above we saw that \([4]\in\mathbb{Z}_{6}\) has order 3, and of course \(\mathbb{Z}_{6}\) itself has order 6. You can check for yourself that 3 divides 6, so that \(|[4]|\mid |\mathbb{Z}_{6}|\text{.}\)
We already had a theorem with Lagrange’s name, but that doesn’t usually stop whoever names theorems from giving them names. Lagrange was one of the most important mathematicians of the eighteenth century; see
Historical remark 16.3.7 for more about him.
Subsubsection 8.3.3.7 Cyclic groups
There is another, simpler concept to keep in mind.
If \(G\) has order \(|G|=n\) and there is some element \(x\in G\) such that \(x\) has order \(|x|=n\) as well, then it must go through all the possible other elements of \(G\) before hitting \(x^{n}=e\text{.}\)
This element, whose powers run through all \(n\) elements of \(G\text{,}\) is called a generator of the group.
Any group that has a generator (again, an element whose powers hit all elements of the group) is called a cyclic group.
It is pretty clear, I hope, that
\(\mathbb{Z}_{n}\) is a cyclic group with generator
\([1]\text{,}\) for any
\(n\text{.}\) But not every group is cyclic! See Exercises
8.4.9 and
8.4.10.
There can be more than one generator; going back to \(\mathbb{Z}_{6}\text{,}\) note that
\begin{equation*}
[1]+[1]+[1]+[1]+[1]+[1]\equiv [0]\text{ and }[5]+[5]+[5]+[5]+[5]+[5]\equiv [0]\text{.}
\end{equation*}
Other elements are in between (e.g. \([2]\equiv [1]+[1]\equiv [5]+[5]+[5]+[5]\)).