Number Theory: In Context and Interactive

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.

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.

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

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.

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

For instance, over \(\mathbb{R}\text{,}\) \(a+x=b\) always has a solution for any real numbers \(a,b\text{.}\) We just take \(x=b+(-a)\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 (b+(-a))\) 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.

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

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,

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:

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{;}\)

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.

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{,}\)

Now take any other element not in this subset, \(y\text{,}\) and look at the set

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

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

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.

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

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!