Example 8.3.1.
\begin{equation*}
2^{(2^{3})}=2^{8}=256\text{ but }(2^{2})^{3}=4^{3}=64\text{.}
\end{equation*}
Section 8.3 Essential Group Facts for Number Theory
Many of the bookkeeping issues which arise in number theory can be made much easier by changing our language and introducing a small amount of abstraction. That abstraction is the concept of group. These notes will introduce this concept in the most basic way possible, with only the minimum needed to translate many difficult arguments into simpler language.
Subsection 8.3.1 Step-by-step notions to the definition
We will take an approach that starts with the familiar and adds properties until we reach our goal.
Subsubsection 8.3.1.1 Sets
Sets are just what you think. They are collections of (mathematical) stuff.
In our uses of groups, we will exclusively be concerned with sets that are collections of numbers, like \(P\text{,}\) the set of primes, and \(\mathbb{Z}\text{,}\) the set of integers, or \(\mathbb{Z}_{n}\text{,}\) the set of equivalence classes of integers modulo \(n\text{.}\) But it’s helpful to think more generally.
Subsubsection 8.3.1.2 Binary operations
A binary operation is a set with a multiplication table on it. That’s it.
Usually books call it \(*\) or something like that, and then define a binary operation on the set \(S\) to be a function from \(S\times S\) to \(S\text{.}\)
- Usually this would be (say) normal addition or multiplication on numbers, though it could also be subtraction.
- On the other hand, if \(S\) is the set of continuous functions on \(\mathbb{R}\text{,}\) the operation could be composition of functions, \(f\circ g\text{.}\)
Notice that if our set is \(\mathbb{Q}\) and our operation is division, we don’t have a full table. The essential thing is that it’s a set with a table or rule for the operation.
Subsubsection 8.3.1.3 Closed operations
A binary operation is called closed if you don’t get anything outside the set with your operation. This is important because it’s easy to break this.
- If you are adding two positive numbers, for instance, you always get a new positive number.
- Is this still true if you subtract two positive numbers from each other?
- This also can happen with division, right? You have to look at \(\mathbb{Q}\text{,}\) and then you have to be careful because of the previous point.
- For a more complicated example, let \(S\) be the set of 2x2 matrices with determinant 1; if you add two of them, your determinant might change a lot.
- On the other hand, if you multiply two such matrices, you’re golden; the determinant will still be 1.
Subsubsection 8.3.1.4 Associative operations
An operation is associative if it doesn’t matter how you put parentheses in.
This is not an algebra course, so I won’t harp on this – everything we do will satisfy it in obvious ways. But it’s worth noting that exponentiation is not associative, so it’s not a trivial condition.
Subsubsection 8.3.1.5 Identity
Much more important is whether your operation has an identity element.
You have seen this many times before in addition and multiplication.
\begin{equation*}
a+0=a=0+a\text{ and }a\cdot 1=a=1\cdot a\text{.}
\end{equation*}
When we turn this into abstract math, we say that an identity for a general operation \(*\) on a set \(S\) is an element, conveniently called \(e\text{,}\) which has the very nice property that if you \(*\) by it, you get the same thing back.
- That is, \(e*a=a=a*e\) for any \(a\in S\text{.}\)
- The identity matrix under matrix multiplication is another example.
- By the way, if there is an identity, there’s only one, which is sometimes useful to know.
Example 8.3.2.
Here is a more interesting example. Let your set be the set of all rotations of a square which leave it facing the same way. That is, rotation by 90 degrees to the left, 180 degrees right, etc. (Think of a child’s block sorter.)
- The binary operation combining two (possibly different) rotations would be to first do one rotation, and then the other one.
- Then an identity element \(e\) of this is just to leave the block alone!
This is sort of weird at first, but an extremely important example.
Subsubsection 8.3.1.6 Inverses
Almost there! Let’s keep thinking about that last example. Say I turn the block 90 degrees to the right, then I realize I made a horrible mistake and want to get back to the original position. Is there anything I can do, short of buying a new square block?
Of course there is! Just turn it back 90 degrees to the left. So if I call the first move \(90R\) and the second one \(90L\text{,}\) I can say that \(90R*90L=e\text{,}\) since the net effect is the same.
Generalizing this, if \(a\) is an element of your set \(S\) and there is another element \(a'\) such that
\begin{equation*}
a*a'=e=a'*a\text{,}
\end{equation*}
then we call \(a'\) an inverse of \(a\text{.}\)
- The absolute prototype of this is negative numbers. That is, for any number \(n\text{,}\) if you add \(-n\text{,}\) then you get zero!
- The same thing happens a lot; for matrix multiplication, the inverse matrix would be the operation inverse.
- For rational numbers (not including zero, of course), the reciprocal would be the multiplicative inverse.
But notice that in both of these cases not every mathematical object has an inverse with respect to every operation! A matrix with determinant zero does not have an inverse matrix. In \(\mathbb{Q}\) under multiplication, zero has no inverse.
Subsection 8.3.2 What is a group?
Definition 8.3.3. Group.
If a set and binary operation on that set is closed and associative with identity and inverses for every element, we call that set a group.
Example 8.3.4.
The most excellent examples of this are the following:
- \(\mathbb{R}, \mathbb{Q}, \mathbb{Z}\) under addition with zero as identity
- The sets \(\mathbb{R}\) and \(\mathbb{Q}\) except zero (written as \(\mathbb{R}\setminus\{0\}\) and \(\mathbb{Q}\setminus\{0\}\text{,}\) respectively) under multiplication with 1 as identity
- \(\mathbb{Z}_{n}\) under addition with \([0]\) as identity. For example, in \(\mathbb{Z}_{3}\text{,}\) every element has an inverse; \([0]'=[0]\text{,}\) \([1]'=[2]\text{,}\) and \([2]'=[1]\text{,}\) because \([0]+[0]=[0]=[1]+[2]\text{.}\)
Remark 8.3.5.
If we are talking about any old group, we just call it \(G\text{.}\)
Also, after a while, it gets boring to always type \(*\text{,}\) and instead we just use normal multiplication notation, writing \(x*y=xy\text{.}\)
Example 8.3.6. A preview of what’s to come.
We noted that \(\mathbb{Q}\setminus\{0\}\) is a group under multiplication, with \(1\) as the identity. Is there something analogous for \(\mathbb{Z}_{n}\text{?}\)
Indeed there is, and we will see it soon. But notice that things will be more complicated.
- For instance, in \(\mathbb{Z}_{3}\text{,}\) both \([1]\) and \([2]\) have multiplicative inverses (in fact, themselves), so \(\mathbb{Z}_{3} \setminus\{[0]\}\) is a (multiplicative) group, just like \(\mathbb{Q}\setminus\{0\}\text{.}\)
- But in \(\mathbb{Z}_{4}\text{,}\) both \([0]\) and \([2]\) do not have multiplicative inverses, so it would not make sense to say that \(\mathbb{Z}_{4}\setminus\{[0]\}\) is a group.
That extra complication is one reason we need to think hard about these things!
Subsection 8.3.3 Properties of groups we will need
The reason for introducing groups in a course which does not presume previous exposure to algebra is that is just makes things simpler. We will start here with familiar facts in a new guise, and then work our way to some facts which will prove invaluable.
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.2 Inverses of product
We can give a formula of sorts for the inverse in any group; see Exercise 8.4.8.
Fact 8.3.7.
The inverse of \(ab\) is \(b^{-1}a^{-1}\text{.}\)
Proof.
First, \(b^{-1}\) and \(a^{-1}\) exist, so \((b^{-1})(a^{-1})\) exists. Next, if \(ab\cdot x= 1\text{,}\) then
\begin{equation*}
(b^{-1}a^{-1})(ab)x= (b^{-1}a^{-1})\cdot 1= b^{-1}a^{-1}\text{;}
\end{equation*}
we use associativity to simplify
\begin{equation*}
(b^{-1}a^{-1})(ab)x= (b^{-1})(a^{-1}a)bx= (b^{-1}\cdot 1\cdot b)x= 1\cdot x= x\text{,}
\end{equation*}
which gives \(x= b^{-1}a^{-1}\text{.}\)
(Keep in mind that in our main example \(ab\cdot x\equiv 1\) is the notion of equality we are using in finding and using these inverses.)
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.4 Order of a group
Definition 8.3.8.
The number of elements of a finite group is called the order of the group.
For any old group \(G\text{,}\) we use \(|G|\) as notation for its order.
Example 8.3.9.
So if we are talking about \(\mathbb{Z}_{3}\text{,}\) it has 3 elements, so it has order 3 (unsurprisingly) and we write \(|\mathbb{Z}_{3}|=3\text{.}\)
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]\)).
Subsubsection 8.3.3.8 Abelian groups
This won’t come up too much, but it is important to note that most of the groups we will encounter in this course have one additional special property.
Namely, it doesn’t matter what order you do the operation in. (Such an operation is called commutative.)
- For instance, clearly (in any \(\mathbb{Z}_{n}\)) it is true that \([1]+[2]=[2]+[1]\text{,}\) or really for any elements at all.
- Not all groups have this property; you may recall that multiplying matrices in two different orders may yield two different answers.
- If your group has this property, then it is clear that Fact 8.3.7 reduces to \((ab)^{-1}=a^{-1}b^{-1}\text{.}\)
Any group which has this property, that \(a*b=b*a\) for all \(a,b\in G\text{,}\) is called an Abelian group. Just keep it in mind!
