Section8.3Essential Facts about Groups 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.

Subsection8.3.1Step-By-Step Notions to the Definition

We will take an approach that starts with the familiar and adds properties until we reach our goal.

Subsubsection8.3.1.1Sets

First, sets are just what you remember. 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\), the set of primes, and \(\mathbb{Z}\), the set of integers, or \(\mathbb{Z}_{n}\), the set of equivalence classes of integers modulo \(n\). But it's helpful to think more generally.

Subsubsection8.3.1.2Binary 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\).

  • 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}\), the operation could be composition of functions - \(f\circ g\).
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.

Subsubsection8.3.1.3Closed 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}\), 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.

Subsubsection8.3.1.4Associative 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.

Example8.3.1
\[2^{(2^{3})}=2^{8}=256\text{ but }(2^{2})^{3}=4^{3}=64\, .\]

Subsubsection8.3.1.5Identity

Much more important is whether your operation has an identity element.

You have seen this many times before in addition and multiplication.\[a+0=a=0+a\text{ and }a\cdot 1=a=1\cdot a\, .\]

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\), 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\).
  • 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.

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, 90 degrees left, 180 degrees right, etc. (think of a child's block sorter).

  • The binary operation would be to 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.

Subsubsection8.3.1.6Inverses

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\), I can say that \(90R*90L=e\), 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 \[a*a'=e=a'*a\; ,\] then we call \(a'\) an inverse of \(a\).

  • The absolute prototype of this is negative numbers. That is, for any number \(n\), if you add \(-n\), then you get zero!
  • The same thing happens a lot; for matrix multiplication, the inverse matrix would be the operation inverse.
  • For rational numbers, the reciprocal would be the inverse.

But notice that in both of these cases not every element has an inverse! A matrix with determinant zero would be one such; or, in \(\mathbb{Q}\), zero has no inverse.

Subsection8.3.2What is a Group?

Definition8.3.2Group
If a set and binary operation have all these properties, including inverses for every element, we call that set a Group.
Example8.3.3

The most excellent examples of this are the following:

  • \(\mathbb{R}, \mathbb{Q}, \mathbb{Z}\) under addition with zero as identity
  • \(\mathbb{R}, \mathbb{Q}\) except zero under multiplication with 1 as identity
  • \(\mathbb{Z}_{n}\) under addition with \([0]\) as identity. For example, in \(\mathbb{Z}_{3}\), every element has an inverse; \([0]'=[0]\), \([1]'=[2]\), and \([2]'=[1]\), because \([0]+[0]=[0]=[1]+[2]\).

Remark8.3.4

If we are talking about any old group, we just call it \(G\).

Also, after a while, it gets boring to always type \(*\), and instead we just use normal multiplication notation - \(x*y=xy\).

Example8.3.5A preview of what's to come
A final example is just 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}\)? Indeed there is, and we will see it soon. But notice that things will be more complicated.
  • For instance, in \(\mathbb{Z}_{3}\), both \([1]\) and \([2]\) have multiplicative inverses (in fact, themselves), so \(\mathbb{Z}_{3} \setminus\{[0]\}\) works, just like \(\mathbb{Q}\setminus\{0\}\) does.
  • But in \(\mathbb{Z}_{4}\), \([2]\) also does not have a multiplicative inverse, 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!

Subsection8.3.3Properties 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.

Subsubsection8.3.3.1Solutions to Equations

Since a group has inverses, we can solve very simple `linear' equations in them. This is stated as \[a*x=b\text{ is solved by }x=a'*b (=a^{-1}*b)\; .\]

For instance, over \(\mathbb{R}\), \(a+x=b\) always has a solution for any real numbers \(a,b\) - we just take \(x=b+(-a)\), where (as mentioned above) \(-a\) is the inverse for the group operation of \(a\).

More important to us is the fact that in \(\mathbb{Z}_{n}\), there are solutions. The operation is still \(+\), so we have \(a+x\equiv b\) mod(\(n\)) solved by \(x\equiv (b+(-a))\) mod(\(n\)).

This doesn't seem much more interesting, but you will see soon why this concept is so important.

Subsubsection8.3.3.2Finite Groups

A group can have finitely many or infinitely many elements. Most of our normal ones are infinite - \(\mathbb{Z}, \mathbb{Q}, \mathbb{R}\), matrix groups, etc.

But the ones we'll use in class 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.

Subsubsection8.3.3.3Order of a Group

The number of elements of a finite group is called the order of the group.

  • So if we are talking about \(\mathbb{Z}_{3}\), it has 3 elements, so it has order 3 (unsurprisingly).
  • For any old group \(G\), we have a nice notation for its order - \(|G|\). So, \(|\mathbb{Z}_{3}|=3\).

Subsubsection8.3.3.4Order of an Element

This is a tougher concept. Suppose you have some element - for instance, \([1]\in \mathbb{Z}_{3}\). If you just keep adding \([1]\) to itself, eventually you get back to zero, right? After all, \[[1]+[1]+[1]\equiv [0]\text{ mod (3).}\]

Take a finite group \(G\) with order \(|G|=n\). We will bring the concept of order to elements, not just groups.

  • Let's list all elements - \[\{e=x_{1}, x_{2}, \ldots,x_{n}\}\; .\]
  • Now let's take an element \(x\), and start operating on it by itself - listing \(x,x*x=x^{2},x^{3},\ldots\).
  • (Don't be confused by the power notation alternating with addition notation; \(\mathbb{Z}_{n}\) has two operations, so we keep \(+\), but in a general group we use multiplicative notation.)
  • (Also, I won't prove it now, but the power notation works the same as we ordinarily use it.)
  • 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 is called the pigeonhole principle, by the way).
  • Let's say \(x^{s}=x^{t}\), with \(s<t\).
  • Now we can do a very curious thing; let's take the inverse of \(x\), written \(x'\) or, more suggestively, \(x^{-1}\).
  • If we multiply it together \(s\) times, we get \((x^{-1})^{s}\) which we can write \(x^{-s}\).
  • Then multiply \(x^{s}=x^{t}\) by \(x^{-s}\); \[x^{-s}x^{s}=x^{-s}x^{t}\text{, or }e=x^{t-s}\; .\]
  • So there is a positive integer \(k\) such that \(x^{k}=e\).
  • By the Well-Ordering Principle, there is a least such integer.
  • We call that number the order of the element \(x\), and we write it \(|x|\), in analogy with the order of a group.
  • For example, in \(\mathbb{Z}_{6}\), look at the element \([4]\). \[[4]+[4]+[4]+[4]+[4]+[4]\equiv [0] \text{ mod(6), but }[4]+[4]+[4]\equiv [0] \text{ mod(6) too.}\] So 6 is a possible order, but clearly 3 is the smallest number of times that will yield \([0]\), so \(|[4]|=3\).

Subsubsection8.3.3.5The Connection

Here comes the coolest part. We will definitely use it in proving various theorems.

  • Take a look at \(x\) - any old element of \(G\).
  • Now, if \(x\) has order \(m\), then there are (at least) \(m\) distinct elements of \(G\), \[\{x,x^{2},x^{3},\ldots,x^{m-1},e\}\; .\]
  • Now take any other element not in this subset, \(y\), and look at the set \[\{xy,x^{2}y,x^{3}y,\ldots,x^{m-1}y,ey=y\}\; ;\] Note that these are all distinct elements.
  • Suppose that some \(x^s y\) is the same as any \(x^t\). If so, \(x^{s}y=x^{t}\), so by multiplying by \(x^{-t}\), we get \(x^{s-t}y=e\).
  • That means \(y=x^{t-s}\), a contradiction. So 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 \[\{xz,x^{2}z,x^{3}z,\ldots,x^{m-1}z,ez=z\}\] will be disjoint form 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.

Let's see what this argument gives. We have a number of subsets of \(G\), all of size \(m\), which exactly fill out \(G\), which has size \(n\). This forces the fact that \(m\) divides \(n\) as an integer.

For example, above we saw that \([4]\in\mathbb[Z]_{6}\) has order 3, and of course \(\mathbb{Z}_{6}\) has order 6. You can check for yourself that 3 divides 6, so that \(|[4]|\mid |\mathbb{Z}_{6}|\). (We already had a theorem by this name, but that doesn't usually stop whoever names theorems from giving them names.)

Subsubsection8.3.3.6Cyclic 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\).
  • This element, whose powers run through all \(n\) elements of \(G\), is called a generator.
  • 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]\), for any \(n\).

There can be more than one generator; going back to \(\mathbb{Z}_{6}\), note that \[[1]+[1]+[1]+[1]+[1]+[1]\equiv [0]\text{ and }[5]+[5]+[5]+[5]+[5]+[5]\equiv [0]\, .\] Other elements are in between (e.g. \([2]\equiv [1]+[1]\equiv [5]+[5]+[5]+[5]\)).

Subsubsection8.3.3.7Abelian 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.

  • For instance, clearly (in any \(\mathbb{Z}_{n}\)) it is true that \([1]+[2]=[2]+[1]\), 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.
  • Any group which has this property, that \(a*b=b*a\) for all \(a,b\in G\), is called an Abelian group. Just keep it in mind!