{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "

\n", "Abstract Algebra: An Interactive Approach, 2e\n", "

\n", "\n", "

\n", "\n", "\n", "\n", "

\n", "Chapter 1
\n", "Understanding the Group Concept\n", "

\n", "\n", "

Initialization: This cell MUST be evaluated first:

" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "%display latex\n", "try:\n", " load('absalgtext.sage')\n", "except IOError:\n", " load('/media/sf_sage/absalgtext.sage')" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The above command should automatically be evaluated as the worksheet is loaded. As long as a blue \"Initialization Done\" message appears at the bottom, we are ready to proceed.

\r\n", "\r\n", "The very first time this package is run, it may require additional databases to be downloaded from the internet. This only takes a few minutes, and only has \r\n", "to be done once. These databases will be available the next time Sage is run. This particular chapter does not use the databases, but make sure you close Sage and \r\n", "restart it before loading a different chapter.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "

\r\n", "Introdection to Groups
\r\n", "Modular Congruence
\r\n", "The Definition of a Group
\r\n", "Sage Interactive Problems
\r\n", "\r\n", "\r\n", "

Introduction to Groups

\r\n", "\r\n", "\r\n", "

\r\n", "To help introduce us to the concept of groups, let us meet a triangle which, through Sage, will dance before your eyes! To see Terry the Triangle, execute \r\n", "the following Sage command. This is done by clicking the mouse inside the rectangle in which the command appears, and press Shift + Enter. If you are not using CoCalc, you could \r\n", "also click on the expression, then click on the \"Evaluate\" button that appears. Try it!

" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "ShowTerry()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Terry may not look very impressive, but with Sage animation, Terry can do some tricks. For example, Terry can rotate with the following command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Terry(RotRt)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This command takes a little longer to execute. Notice that a light green bar appears becide the area where the answer will appear in order to assure you that the command \r\n", "is being executed. As you can see, RotRt is the abbreviation for rotation right, or clockwise. Terry can rotate counterclockwise with the command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Terry(RotLft)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Terry can do more than just rotate. For example, Terry can spin in three dimensions.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Terry(Spin)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Terry can also do some gymnastic tricks, such as flipping over the right and left shoulder.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Terry(FlipRt)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Terry(FlipLft)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This makes 5 different moves that Terry can do. There is one more trick that Terry can perform:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Terry(Stay)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Good triangle!

\r\n", " \r\n", "These six commands are the six dance steps that Terry can do. Terry can combine these dance steps to form a dance routine. We separate the dance steps by commas. \r\n", "Here is a simple routine that Terry can do:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Terry(FlipRt, Spin, RotRt)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXPERIMENT:
\r\n", "You may have noticed in the previous animation that Terry ends the dance routine in the original orientation. What if the order of the dance steps were \r\n", "changed? Edit the last command to change the order of Terry's steps, and see what happens.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Here is a shorter dance sequence for Terry. Pay special attention to how Terry is oriented after the dance routine.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Terry(FlipRt, Spin)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Sometimes Terry gets tired of doing all of these long routines. When this happens, Terry takes a short cut to get to the final orientation. For example, the above \r\n", "routine leaves Terry in the same orientation as RotLft, and so Terry would simply rotate instead of doing the extra gymnastics. Executing the follow \r\n", "command allows Terry to take short cuts in all dance routines.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitTerry()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Now let's ask Terry to do the same dance routine.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Terry(FlipRt, Spin)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that Terry simply rotates to get to the correct orientation. Rather than calling Terry a bad triangle for being lazy, we must commend Terry for being smart enough \r\n", "to know that a flip to the right followed by a spin is equivalent to a counter-clockwise rotation. In essence Terry has learned how to "multiply" two dance \r\n", "steps together.

\r\n", " \r\n", "We can use Sage to multiply dance steps together, using the star to indicate Terry's multiplication. Thus, Sage simplifies \r\n", "FlipRt · Spin as follows:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FlipRt * Spin" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can display a \"multiplication table\" of all of Terry's dance steps by the following command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable([Stay, FlipRt, RotRt, FlipLft, RotLft, Spin])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "To read this table, we look for the first of the dance steps on the left hand side of the table, and the second of the dance steps on the top. Thus, to determine\r\n", "FlipRt · Spin, we look at the right hand entry of the second row to find RotLft. This table is often refered to \r\n", "as a Cayley table.\r\n", "\r\n", "

\r\n", "This table illuminates some properties of the dance steps. Each of the six dance steps is in a different color, to highlight these properties. One property this \r\n", "table demonstrates that the combination of any two dance steps is equivalent to one of the six dance steps.

\r\n", "\r\n", "Another of the easiest properties to observe is in the Stay row and column. Notice that whenever the command Stay is combined with any \r\n", "other dance step, it leaves that dance step unchanged. Try this for yourself:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Stay * RotRt" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RotRt * Stay" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "EXPERIMENT:
\r\n", "Replace RotRt in the above two Sage commands with a different dance step and re-evaluate them. Notice what happens.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "You may observe that the Stay command acts like the number 1 in our standard multiplication. In mathematical notation, we say that \r\n", "

Stay · x = x and x · Stay = x

\r\n", "for all dance steps x. We call Stay the identity of the dance steps.

\r\n", "\r\n", "But there is a property of these dance steps that is unlike our standard multiplication. In a previous experiment, you were asked to change the order of the dance \r\n", "steps in a routine to see if that would affect the final orientation. In fact, it did! Check out the following two products:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Spin * FlipRt" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FlipRt * Spin" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "As we see, the product depends on the order in which the dance steps are multiplied. In other words,\r\n", "

x·y is sometimes not equal to y·x.

\r\n", "This is perhaps the biggest difference between Terry's algebra and the algebra that we are familiar with. We are familar with the \r\n", "commutative property of numbers:\r\n", "

x y = y x for all real numbers x and y.

\r\n", "Since Terry's dance steps do not obey this law, we say that the dance steps are non-commutative.

\r\n", "\r\n", "There is another property that we are familiar with in standard algebra:\r\n", "

x (y z) = (x y) z for all numbers x, y, and z.

\r\n", "This is called the associative law of multiplication. Do Terry's dance steps obey this law?

\r\n", "\r\n", "EXPERIMENT:
\r\n", "Compare the two products:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "(Spin * RotRt) * FlipLft" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Spin * (RotRt * FlipLft)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Try changing the dance steps to see if we always get the same product, regardless of where the parenthesis are.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "There is another property that we can observe from Terry's multiplication table. Here it is again.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable([Stay, FlipRt, RotRt, FlipLft, RotLft, Spin])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that the identity dance step, Stay is in every row and every column in the table. (Notice the yellow squares.) This indicates that every dance \r\n", "step has some dance step which "undoes" it. For example, RotLft will undo a RotRt command, since
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "RotLft * RotRt" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "gives us the identity element. Likewise, the Spin command undoes itself, for two spins in secession
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Spin * Spin" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "returns to the original position.

\r\n", " \r\n", "Using mathematical notation again, we say that for every dance step x, there is some dance step y such that\r\n", "

x·y = Stay.

\r\n", "The dance step y is called an inverse of x. For example, RotLft is the inverse of RotRt, and \r\n", "Spin is the inverse of Spin. \r\n", "\r\n", "

\r\n", "Terry claims that if x·y = Stay, then y·x will also equal Stay. \r\n", "Although this can be seen to be true by looking at the multiplication table, can you prove that this is so using only the properties of Terry's dance steps that we \r\n", "have discovered? Here is a summary of what we have found so far:
\r\n", "
\r\n", " \r\n", "1) The order in which the dance steps are performed are important.
\r\n", " For example, Spin · FlipRt ≠ FlipRt · Spin.

\r\n", " \r\n", "2) The combination of any two dance steps is equivalent to one of the six dance steps.

\r\n", "\r\n", "3) The order in which a dance routine is simplified does not matter.
\r\n", " That is, (x·y)·z = x·(y·z) for any dance steps x, y, and \r\n", "z.

\r\n", " \r\n", "4) Any dance step combined with Stay yields the same dance step.
\r\n", " That is, x·Stay = x and Stay·x = x for any dance step x.

\r\n", " \r\n", "5) Every dance step has another dance step that "undoes" it. That is,
\r\n", " for any dance step x, there is a dance step y such that x·y = Stay.
\r\n", " For example, a step that undoes RotRt is RotLft.

\r\n", "\r\n", "We will introduce the following mathematical terminology to express each of these properties.

\r\n", "\r\n", "1) The dance steps are not commutative.

\r\n", "2) The dance steps are closed under multiplication.

\r\n", "3) The dance steps are associative.

\r\n", "4) There is an identity dance step.

\r\n", "5) Every dance step has an inverse.

\r\n", "\r\n", "With just these properties, can you prove the following proposition on your own without looking at the proof?\r\n", "\r\n", "

\r\n", " \r\n", "\r\n", "PROPOSITION 1.1
\r\n", "If y is an inverse of x, then x is an inverse of y. Furthermore, x will be the only inverse of y.

\r\n", " \r\n", "Hint: Because we don't have the commutative property, we must use some other strategy. Recall that y must also have an inverse!

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "\r\n", "All of the proofs in these notebooks appear near the end, before the Sage problems, with links allowing us to go directly to them. This gives the user a \r\n", "chance to work the proof out on him own before peeking at the books version. Notice that we did not yet assume that there is only one identity element. However, \r\n", "this fact immediately follows from Proposition 1.1. (See Problems 3 and 4.)
\r\n", "\r\n", "
\r\n", "DEFINITION 1.1 We use the notation x^-1 for the unique inverse of the element x.

\r\n", "\r\n", "\r\n", "This is entered into Sage as
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Spin^-1" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Proposition 1.1 can now be expressed simply as (x^-1)^-1 = x. Is it true that (x·y)^-1 = \r\n", "x^-1·y^-1, as we are accustomed too?

\r\n", "\r\n", "\r\n", "EXPERIMENT:
\r\n", "Try the following commands to see if they give the same result.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "(FlipRt * Spin)^-1" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "FlipRt^-1 * Spin^-1" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Try using different dance steps in place of FlipRt amd Spin. What do you observe?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Apparently, (x·y)^-1 is not always equal to x^-1·y^-1. \r\n", "But Terry would tell you that in order to undo a sequence of dance steps, one must begin by undoing the last dance step. \r\n", "Thus, the way to undo the routine (Spin · RotRt) is by first rotating left, and spinning back to the original position.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "(FlipRt * Spin)^-1" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Spin^-1 * FlipRt^-1" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This suggests that \r\n", "

(x·y)^-1 = y^-1·x^-1.

\r\n", "Can you prove this? \r\n", "\r\n", "

\r\n", " \r\n", "PROPOSITION 1.2
\r\n", "

(x·y)^-1 = y^-1·x^-1.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "Let us see if we can find any more patterns in Terry's multiplication table. Here is the table again:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable([Stay, FlipRt, RotRt, FlipLft, RotLft, Spin])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Before we noticed that every row and every column contained the identity element, Stay. Which other elements have this property?

\r\n", " \r\n", "In answering this, you probably discovered that every row and every column in this table contains all six elements. If we disregard the heading row and column in \r\n", "the table, each element appears exactly once in each row, and once in each column. This formation is refered to as a Latan square. How could we show that \r\n", "this would happen using only the four properties we have been using?

\r\n", "\r\n", "First we must translate this pattern into a mathematical statement before it can be proven. To say that the element RotRt appears only once in \r\n", "the row beginning with Spin is to say that there is only one dance step x such that \r\n", "

Spin · x = RotRt.

\r\n", "So we can say that each row contains exactly one of every element by the following statement:\r\n", "\r\n", "

\r\n", " \r\n", "PROPOSITION 1.3
\r\n", "If a and b are given, then there exists a unique x such that \r\n", "

a·x = b.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "Can you use this proposition to show that any column of the table contains only one of each element? This is essentually Problem 6.

\r\n", " \r\n", "Terry's dance steps provides us with a new and rather different type of multiplication. Even though there are very few of Terry's dance steps, we already can see\r\n", "some of the patterns that can appear when we consider the multiplication of these \r\n", "dance steps. In the next section we will consider another operation that has many of the \r\n", "same patterns.

\r\n", "\r\n", "\r\n", "

Modular Congruence

\r\n", "\r\n", "
\r\n", "Although we have seen an example of a totally different type of "multiplication", in this section we will explore different ways of combining two integers \r\n", "that has many of the same properties. These other types of "products" have some important applications. These multiplications stem from a property of adding \r\n", "and multiplying standard integers.

\r\n", "\r\n", "We have already introduced modular arithmetic in §0.3. We defined x mod n as the remainder r when x is divided by n, \r\n", "using the division algorithm. But we can also say that two integers x and y are equivalent if x mod n = \r\n", "y mod n. We will introduce another notation for this relation.

\r\n", "\r\n", "DEFINITION 1.2
\r\n", "Let x, y, and n be integers. We say x and y are equivalent modulo n, written\r\n", "

x ≡ y (mod n)

\r\n", "if, and only if, there is an integer k such that \r\n", "

(x − y) = k n.

\r\n", "\r\n", "Note the slight difference in notation between the operator mod (expressed in boldface) and the above notation (where mod is not in boldface). The two notations are clearly related, since x ≡ y (mod n) means that x mod n = y mod n.

\r\n", "\r\n", "The new notation also satisfies three very important properties for equivalence (mod n).

\r\n", "\r\n", "1. (Reflexive) Every integer x is equivalent to itself.
\r\n", "2. (Symmetric) If x is equivalent to y, then y is equivalent to x.
\r\n", "3. (Transitive) If x is equivalent to y, and y in turn is equivalent to z, then x is equivalent to z.

\r\n", "\r\n", "DEFINITION 1.3
\r\n", "Any relation that satisfies these three properties is called an equivalence relation. We will use the notation x ∼ y to say \r\n", "that x is equivalent to y for a generic equivalence relation.

\r\n", "\r\n", "Let us prove that equivalence (mod n) forms an equivalence relation.\r\n", "\r\n", "

\r\n", " \r\n", "PROPOSITION 1.4
\r\n", "Let n be a positive integer. Then the definition of\r\n", "

x ≡ y (mod n)

\r\n", "forms an equivalence relation on the set of integers.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "\r\n", "Whenever an equivalence relation is defined on a set, the set can be broken up into disjoint equivalence classes, where each equivalence class is the set of elements related to one element in the class.

\r\n", "\r\n", "DEFINITION 1.4
\r\n", "Let x ∼ y be an equivalence relation defined on a set S. Then the equivalence class [a] is the set of elements of S \r\n", "related to a. That is,\r\n", "

[a] = { s ∈ S | s ∼ a}.

\r\n", "\r\n", "EXAMPLE:
\r\n", "In the relation x ≡ y (mod 10), the set [3] will be the set of integers equivalent to 3 (mod 10), giving the set\r\n", "

[3] = {… -37, -27, -17, -7, 3, 13, 23, 33, 43, …}.

\r\n", "Other equivalence classes in this relation are similar.

\r\n", "\r\n", "It is not hard to show that the set of integers can be broken up into disjoint sets using the equivalence classes.

\r\n", "\r\n", "

\r\n", " \r\n", "PROPOSITION 1.5
\r\n", "If x ∼ y is an equivalence relation on a set S, then S is the disjoint union of equivalence classes.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "\r\n", "Many of the properties of modular arithmetic found in §0.3 can be translated in terms of equivalence relations. For example, Proposition 0.2 can be restated \r\n", "by saying that if \r\n", "

x ≡ a (mod n) and y ≡ b (mod n),

\r\n", "then x + y ≡ a + b (mod n) and x y ≡ a b (mod n).

\r\n", "\r\n", "These statements make it clear that to add or multiply two numbers modulo n, we can choose any representative element from the equivalence class.

\r\n", "\r\n", "EXAMPLE:
\r\n", "Consider the set of numbers from {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, with the binary operation being x ∗ y = (x + y) mod 10. \r\n", "We can have Sage define this binary operation with the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z = AddMod(10); Z" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This produces a set of 10 elements, \r\n", "which Sage displays using curly brackets. Although the elements of Z are displayed\r\n", "as integers, we will soon see that they have differnt properties than ordinary integers. \r\n", "We will continue \r\n", "to use the dot as the way to combine two members of the list. So even though the operation is \r\n", "addition modulo 10, we would write 4 · 7 = 1. Although it seems strange to use the \r\n", "dot instead of the plus sign, for consistency we will always use the dot for the operator, whatever that operator is. So the one thing we must \r\n", "remember is that the dot does not always mean multiplication. Rather, the dot represents the operation in the current context. For Terry's group, \r\n", "the dot represented combining two dance steps. Here, it represents addition modulo 10.

\r\n", "\r\n", "In Sage, we will use the star to indicate the operation, as we did for Terry's dance \r\n", "steps. In order to access the elements in the set Z, we will put \r\n", "a number in brackets to indicate the location number in the set. So here is how we can combine the fourth and seventh elements in Z.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z[4] * Z[7]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We will still use the command MultTable to give the Cayley table of the set, even though the operation is more like addition.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(Z)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Can we find any patterns in this table, as we did in Terry's multiplication table? Yes, and even more. We can see that this table is a Latin square—every row \r\n", "and every column contains one of each number. Notice the diagonal streaks of color in the table. This Caylay table has symmetry—imagine a mirror placed \r\n", "along the northwest to southeast corners. What is causing this symmetry?

\r\n", "\r\n", "EXPERIMENT:
\r\n", "We saw that Terry's multiplication was not commutative. That is, x·y did not always equal y·x. What about adding \r\n", "modulo 10? Try the following commands
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z[4] * Z[7]" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z[7] * Z[4]" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Are these the same? Try this with different numbers.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The symmetry in the table comes from the fact that x·y is always equal to y·x. We say that addition modulo 10 \r\n", "is communitive. Thus, we can see 5 properties from the table:

\r\n", "\r\n", "1) For any two numbers x and y in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, x·y is in that set.
\r\n", "(Recall that we are using the dot to indication the operation, regardless of what that operation is. In this example, the operation is addition modulo 10.)

\r\n", "\r\n", "2) (x·y)·z = x·(y·z) for any x, y, and z.\r\n", "

\r\n", "\r\n", "3) x·0 = x and 0·x = x for all x.

\r\n", "\r\n", "4) For any x, there is a y such that x·y = 0.

\r\n", "\r\n", "5) For any x and y, x·y = y·x.

\r\n", "\r\n", "Notice that 0 now acts like Terry's command Stay. This is the identity.

\r\n", "\r\n", "Besides the table, Sage has another way of picturing a "product" by means of circular graphs. Enter in the following Sage command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Z, Add(1))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "As you can see, Sage labels 10 equi-distant points on the circle with the digits 0 through 9, like a clock. It then draws an arrow from each point to the \r\n", "point produces by "adding 1 modulo 10".

\r\n", " \r\n", "EXPERIMENT:
\r\n", "Create eight more circle graphs by changing the Add(1) in the last command to Add(2), Add(3), \r\n", "Add(4), ⋯ Add(9). Which circular graph is the prettiest?

" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "If none of those graphs were pretty enough, Sage can graph several of them at the same time. For example, the command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Z, Add(1), Add(2), Add(3), Add(4), Add(5))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "draws a circular graph with five different colored arrows. The red arrows represent adding 1 modulo 10, the green arrows represent adding 2, the purple arrows \r\n", "adding 3, the orange arrows adding 4, and the grey arrows represent adding 5 modulo 10.

\r\n", " \r\n", "We can also draw a circular graph of the inverses of the elements. The command
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Z, Inv)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "draws an arrow from each point to its additive inverse. Notice that every arrow has a corresponding arrow in the opposite direction, which indicates that\r\n", "(x^-1)^-1 = x, as we found in Proposition 1.1. Also notice that 0 and 5 are there own inverses, as indicated by the two \r\n", "loops.

\r\n", "\r\n", "We are more familiar with base 10 arithmetic since most of us have ten fingers. However, this modular arithmetic can be done in other bases as well. The beings on \r\n", "the planet Xantz have seven fingers (three on each hand, and one coming out of the nose) so they only use the digits 0, 1, 2, 3, 4, 5, and 6. Their modular \r\n", "arithmetic would look like this:\r\n", "

4 + 5 ≡ 2 (mod 7), 4 × 5 ≡ 6 (mod 7).

\r\n", "\r\n", "
\r\n", "(Actually, the symbols used on Xantz don't look anything like the symbols we use, so this is really a translation of what they would write.)

\r\n", " \r\n", "We can have Sage switch to base 7 with one easy command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z = AddMod(7); Z" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We now can look at the multiplication tables and circle graphs of the set {0,1,2,3,4,5,6}:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(Z)" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Z, Add(1), Add(2), Add(3))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Notice that the patterns that we observed in modular 10 arithmetic are showing up hear as well.

\r\n", " \r\n", "EXPERIMENT:
\r\n", "Try creating tables and circle graphs for modulos other than 7 and 10. Do they all form the same basic pattern?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We can have Sage define the period to be multiplication modulo 7 instead of addition. This is done by the command:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z = MultMod(7); Z" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Now the term "multiplication table" seems more appropriate:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(Z)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Does this multiplication table have the same features that we have been seeing? No it doesn't! But if we remove the 0 row and column, we see that the remainder of the \r\n", "table would satisfy the same properties that we observed in Terry's multiplication table, such as the Latin square property. The identity is now the number 1. This \r\n", "table is in fact symmetrical, indicating that multiplication modulo 7 is commutative.

\r\n", " \r\n", "Here is a circular graph of multiplication modulo 7:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Z, Mult(2), Mult(3))" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "Here, the red arrow indicates multiplication by 2, and the green arrow represents multiplication by 3 modulo 7.

\r\n", "\r\n", "Here is a circular graph of the inverse elements:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Z, Inv)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "What happens to 0? Recall that the inverse of x is defined to be the number y such that x·y = 1. But the equation \r\n", "0·y ≡ 1 (mod 7) has no solution, so 0 does not have an inverse (as we saw in the multiplication table.) Thus, when Sage graphs the \r\n", "inverse function, 0 is sent to a question mark to indicate that there is no inverse of 0. \r\n", "\r\n", "\r\n", "\r\n", "
\r\n", "EXPERIMENT:
\r\n", "Try having Sage work with multiplication with a modulo other than 7, and form a circle graph of the inverse function. Is 0 the only number that does not have \r\n", "an inverse? If not, can you find a pattern to the numbers which do not have an inverse?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "In the last experiment, you probably discovered that there may be many numbers without a multiplicative inverse. For example, by looking at the multiplication \r\n", "table modulo 10,
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z = MultMod(10)\r\n", "MultTable(Z)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "we find several rows that do not contain any 1's. These rows indicate the numbers without inverses modulo 10. We can see these more clearly by looking at the \r\n", "circle graph of the inverse function.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "CircleGraph(Z, Inv)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "So 0, 2, 4, 5, 6, and 8 do not have inverses. Do you see a pattern in these numbers?
\r\n", "Hint: 2 does not have an inverse because there is no integer x such that \r\n", "

2 x = 1 + 10 n

\r\n", "for some n.

\r\n", " \r\n", "To help see the pattern, look at multiplication modulo 15:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "Z = MultMod(15)\r\n", "CircleGraph(Z, Inv)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We see that 0, 3, 5, 6, 9, 10, and 12 do not have inverses. There are eight numbers which do have inverses modulo 15. What if we just considered those \r\n", "eight elements?
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "L = [Z[1], Z[2], Z[4], Z[7], Z[8], Z[11], Z[13], Z[14]]\r\n", "CircleGraph(L, Inv)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "By using this smaller set of numbers, every element now has an inverse. What if we looked at the multiplication table of this smaller set?
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(L)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "One again, we can see some of the patterns in this table that we have seen before. Notice that this is a Latin square—every row and column contains each of \r\n", "the eight numbers. In fact, we can see the symmetry in this table which indicates that the multiplication is communative. Thus, we see that

\r\n", "\r\n", "1) For any two numbers x and y in {1, 2, 4, 7, 8, 11, 13, 14}, x·y is in that set.

\r\n", "2) (x·y)·z = x·(y·z) for any x, y, and z.

\r\n", "3) x · 1 = x and 1 · x = x for all x.

\r\n", "4) For any x, there is a y such that x · y = 1.

\r\n", "5) For any x and y, x · y = y · x.

\r\n", "\r\n", "
\r\n", "EXPERIMENT:
\r\n", "Try this procedure working with different bases, such as n = 8 or n = 9: First type in Z = MultMod(n) which \r\n", "defines the multiplication modulo n. Then use make a circle graph of the Inv function to see which numbers have inverses \r\n", "modulo n. Finally, make a multiplication table of those numbers. Will this table always form a Latin square?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "If the Latin square pattern always seems to appear for the invertible numbers, can we prove that this pattern will always appear?\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 1.6
\r\n", "For n a positive integer greater than 1, let the dot (·) denote multiplication modulo n. Let G be the set of all non-negative numbers \r\n", "less than n that have inverses modulo n. Then the set G has the following properties:

\r\n", "1) For any two numbers x and y in G, x·y is in G.

\r\n", "2) (x·y)·z = x·(y·z) for any x, y, and \r\n", "z.

\r\n", "3) x·1 = 1·x = x for all x.

\r\n", "4) For any x that is in G, there is a y in G such that x·y = 1.

\r\n", "5) For any x and y, x·y = y·x.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "Although we have found that the invertible elements modulo n will always have a multiplication table which forms a Latin square, we have only hinted at which \r\n", "numbers are invertible modulo n.

\r\n", " \r\n", "We saw that the numbers 0, 2, 4, 5, 6, and 8 are not invertible modulo 10. Note that these numbers all have a prime factor in common with 10: 0, 2, 4, 6, 8, and 10 \r\n", "are multiples of 2, whereas 0, 5, and 10 are multiples of 5. The remaining numbers, 1 ,3 ,7, and 9, are coprime to 10. Let us demonstrate why this is true in general.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 1.7
\r\n", "Let n be in ℤ⁺. Then for x between 0 and n − 1, x has a multiplicatative inverse modulo n \r\n", "if, and only if, x is coprime to n.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "\r\n", "We now have seen several binary operations, such as Terry's dance steps, addition modulo n, and multiplication modulo n, which have many properties in common. \r\n", "In the next section we will generalize these examples to produce many more \r\n", "interesting examples, but in such a way that they will all have the important properties that we have seen.\r\n", "\r\n", "\r\n", "

The Definition of a Group

\r\n", "\r\n", "
\r\n", "In this worksheet, we have seen several different ways of combining numbers or dance steps. Yet, all of the different "products" \r\n", "had many properties in common. We are now ready to try to generalize these examples. Our strategy is to define a group abstractly by requiring the same \r\n", "patterns we observed to continue. Thus, we make the following definition based upon the first four properties we saw in all of our examples.

\r\n", "\r\n", "DEFINITION 1.5
\r\n", "A group is a set G together with a binary operation (·) such that the following four properties hold:

\r\n", "1) (closure) For any x and y in G, x·y is in G.

\r\n", "2) (identity) There exists a member e in G which has the property that, for all x in G,\r\n", "

e·x = x·e = x.

\r\n", "3) (inverse) For every x in G, there exists a y in G, called the inverse of x, such that \r\n", "x·y = e.

\r\n", "4) (associative law) For any a, b, and c in G, \r\n", "

(a ·b)·c = a·(b·c).

\r\n", "

\r\n", "\r\n", "These are the same four properties that we observed from Terry's dance steps, so Terry's dance steps give us the first example of a group. This group is more \r\n", "commonly refered to as the group of symmetries of a triangle, abbreviated by D₃.

\r\n", " \r\n", "The members of the group, whether they are numbers, dance steps, or even ordered pairs, are called the elements of the group. The element e that \r\n", "satisfies property 2 is commonly called the identity element of the group.

\r\n", " \r\n", "The mathematical notation for an element x to be in a group G is \r\n", "

x ∈ G.

\r\n", "\r\n", "Thus, the symbol ∈ means "is an element of."

\r\n", " \r\n", "Since Propositions 1.1, 1.2, and 1.3 only used these four properties, the proofs are valid for all groups, using the identity element e in place of the \r\n", "dance step Stay.

\r\n", " \r\n", "Other examples of groups come from modular arithmetic. For n in ℤ, we considered the elements\r\n", "

{0, 1, 2, …, n − 1},

\r\n", "with the opperator (·) being the sum modulo n. This group will be denoted Z_n. For example, \r\n", "the group Z₁₀ is given by:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = ZGroup(10); G" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "We also considered having the opperator (·) denoted the product modulo n, and considered only the set of numbers less than n that are \r\n", "coprime to n. Proposition 1.6 shows that this set also has the four properties of groups. We will refer to this group \r\n", "by Z_n^*. This group can be loaded in Sage by the command ZStar. For example, the group Z₁₅^* has 8 elements, with the following multiplication table.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "G = ZStar(15); G" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "MultTable(G)" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "The groups Z_n and Z_n^* had an additional property—the multiplication tables were symmetric about the \r\n", "northwest to southeast diagonal. Not all groups have this property, but those that do are important enough to give such groups a special name.

\r\n", " \r\n", "DEFINITION 1.6
\r\n", "A group G is abelian (or commutative) if x·y = \r\n", "y·x for all x, y ∈ G.

\r\n", "\r\n", "Although these definitions appear ad hoc, the four properties of groups appear in many different aspects of mathematics. Here are some examples of groups that appear \r\n", "on other contexts besides group theory:

\r\n", " \r\n", "EXAMPLE:
\r\n", "Consider the group consisting of all of the integers, ℤ. Our binary operation would be the sum of the two numbers. It is trivial to see that this satisfies \r\n", "all 4 properties, with 0 as the identity, and −x as the inverse of x. This is obviously an abelian group, since\r\n", "

a + b = b + a for all a and b in ℤ.

\r\n", " \r\n", "EXAMPLE:
\r\n", "Next, we could consider the group of all rational numbers, which is denoted by ℚ. (This is easy to remember, since ℚ stands for Quotient.) \r\n", "Our binary operation would still be addition, so the identity element would still be 0, and this would also be an abelian group.

\r\n", " \r\n", "EXAMPLE:
\r\n", "Consider the group of all rational numbers except for 0. We will refer to this group as ℚ^*. Our group operation would be multiplication instead \r\n", "of addition. The identity element is now 1, and the inverse of an element is the reciprocal. Again, this is an abelian group.

\r\n", " \r\n", "EXAMPLE:
\r\n", "Consider the set of all linear functions of the form\r\n", "

f(x) = m x + b, with m, b ∈ ℝ, m ≠ 0.

\r\n", "(The fancy ℝ here represents the real numbers.) We multiply two linear functions together by function composition. That is, if \r\n", "f(x) = m x + b, and g(x) = n x + c, then\r\n", "

f·g = f(g(x)) = m(n x + c) + b = \r\n", "(m n) x + (m c + b)

\r\n", "which is again a linear function. Note that in f·g, we do g first, then f, so we apply the functions from right to left. We \r\n", "can find the inverse of f(x) as well:\r\n", "

f ^-1(x) = ¹⁄_m x − \r\n", "^b⁄_m,

\r\n", "which is also a linear function. The identity function is just e(x) = x. The associativity property of function composition completes \r\n", "the requirements for the set of all linear functions to constitute a group.

\r\n", "\r\n", "Is this group abelian? Let f(x) = 2x + 3, and g(x) = 3x + 2. Then f(g(x)) is \r\n", "2(3x + 2) + 3 = 6x + 7, whereas g(f(x)) = 3(2x + 3) + 2 = 6x + 11. \r\n", "So this is not an abelian group.

\r\n", "\r\n", "These last four groups have an infinite number of elements, so we unfortunately cannot construct multiplication tables for them. To distinquish the groups which \r\n", "have multiplication tables, we make the following definition:

\r\n", "\r\n", "DEFINITION 1.7
\r\n", "The number of elements in a group G is called the order of the group, and is denoted |G|. If G is has an infinite number of \r\n", "elements, we say that |G| = ∞.

\r\n", "\r\n", "The last four examples had infinite order, and hence we cannot form multiplication tables for these groups. On the opposite end of the spectrum, what is the \r\n", "smallest possible group? The third group property states that there must be an identity element in the group. So the smallest group is the following:

\r\n", "\r\n", "EXAMPLE:
\r\n", "Consider the group containing just the identity element, {e}. Why is this a group?

\r\n", "\r\n", "We know that since e is an identity, e·e = e. It does contain an identity element, and e has an inverse, \r\n", "namely e. We can check associativity by noting that\r\n", "

(e·e)·e = e·(e·e) = e.

\r\n", "We can give a multiplication table of this group by executing the following:
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitGroup(\"e\")\r\n", "MultTable([e])" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "This group seems too simple to be of practical value, so we call this the trivial group. Most of our groups will be much more interesting!

\r\n", " \r\n", "The first of these Sage commands introduces a new command—InitGroup. This command designates the new identity element, and sets the \r\n", "stage for entering a new group.

\r\n", " \r\n", "As we see from these examples, sometimes the operator (·) means addition, sometimes it means multiplication, and sometimes it means \r\n", "neither. Nonetheless, we can consider the operation of an element by itself a number of times. This produces combinations like\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

x·x,

x·x·x,

x·x·x·x, and

x·x·x·x·x.

\r\n", "
\r\n", "Even though the (·) does not always mean multiplication, we can define xⁿ to mean x opperated on itself n times. \r\n", "Thus,\r\n", "\r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", " \r\n", "

x =	x¹,
x·x =	x²,
x·x·x =	x³, etc.

\r\n", "\r\n", "
\r\n", "We formally define xⁿ for any integer n. We let x⁰ = e, the identity element, then we define, for \r\n", "n > 0,\r\n", "

xⁿ = xⁿ⁻¹·x.

\r\n", "By defining the n^th power in terms of the (n − 1)^st power, we inductively have defined xⁿ \r\n", "whenever n is a positive integer.

\r\n", "\r\n", "Finally, we can define negative powers by letting \r\n", "

x⁻ⁿ = (xⁿ)^-1 if n > 0.

\r\n", "Note that if the operator · represents addition, the raising x to a power is repeated addition, which is multiplication.

\r\n", "\r\n", "We can now prove some theorems which involve this exponential notation.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 1.8
\r\n", "If x is an element in a group G, and m and n are integers, then\r\n", "

x^m+n = xⁿ·x^m.

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "This last proof utilizes an important method of proving theorems called induction, which was introduced in §0.1. Induction is based on the well \r\n", "ordering axiom, which states that any non-empty subset of positive integers contains a smallest element.

\r\n", " \r\n", "It is not hard to see why this must be true. If there were some positive integer not in the set, then there must be a smallest positive integer k that \r\n", "is not in the set. Since 1 is in the set, we see that k > 1, and since k is the smallest number not in the set, k − 1 must be \r\n", "in the set. But the property of the set is that if k − 1 is in the set, then k also is. So we have a contradition, so there is no \r\n", "such k, meaning the the set is indeed all positive integers.

\r\n", "\r\n", "This gives us a powerful tool for proofs. In fact, we really do not need to introduce the variable k. To prove a statement for all positive integers \r\n", "n, we can first prove the statement is true for n = 1, and then we can assume that the statement is true for the previous case n − 1. \r\n", "This extra information often gives us the leverage we need to be able to prove the statement is true for n. Here is another example of the use of induction.\r\n", "\r\n", "

\r\n", "\r\n", "PROPOSITION 1.9
\r\n", "If x is an element in a group G, and m and n are in ℤ, then\r\n", "

(x^m)ⁿ = x^{(m n)}

\r\n", "\r\n", "Click here for the proof.\r\n", "\r\n", "

\r\n", "Propositions 1.8 and 1.9 show that the common laws of exponents hold for elements of a group. In the next section, we will use the powers of elements to explore the properties of a group.\r\n", "\r\n", "

\r\n", "\r\n", "

Proofs:

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Proposition 1.1:

\r\n", "\r\n", "Let z be any inverse of y. Our job is to show that z is in fact equal to x. Consider the \r\n", "product x·y·z. According to the associative property, \r\n", "

x·(y·z) = (x·y)·z.

\r\n", "On the left side, we see that y·z is an identity element, so x·(y·z) = x. \r\n", "But on the right side, we find that x·y is an identity element, so (x·y)·z = z. Thus, \r\n", "x = z, and so x is an inverse of y. Therefore, the inverse of an inverse gives us back the original element.

\r\n", "\r\n", "\r\n", "But as a bonus, we see that inverses are unique! We let z be any inverse of y, and found that it had to equal x. Thus, y has only \r\n", "one inverse, namely x. But if we apply the argument again, reversing the roles of x and y, we see that x has only one inverse, namely \r\n", "y. Thus, all inverses are unique.

\r\n", " \r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", "\r\n", "\r\n", "Proof of Proposition 1.2:

\r\n", "\r\n", "Since the inverse (x·y)^-1 is the dance step z such that \r\n", "(x·y)·z = Stay, it suffices to show that y^-1·x^-1 has this \r\n", "property. We see that\r\n", "

(x·y)·(y^-1·x^-1) = \r\n", "x·(y·y^-1)·x^-1 = x·Stay·x^-1 = \r\n", "x·x^-1 = Stay.

\r\n", "So (x·y)^-1 = y^-1·x^-1.

\r\n", " \r\n", "Return to text\r\n", "\r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 1.3:

\r\n", " \r\n", "Suppose that there is an x such that a·x = b. We can multiply both sides of the equation on the left by \r\n", "a^-1 to give us\r\n", "

a^-1·(a·x) = a^-1·b.

\r\n", "Then \r\n", "

(a^-1·a)·x = a^-1·b.

\r\n", "

Stay·x = a^-1·b.

\r\n", "So x = a^-1·b. Thus, if there is a solution, this must be the unique solution a^-1·b. Let \r\n", "us check that this is indeed a solution.\r\n", "

a·x = a·a^-1·b = Stay·b = \r\n", "b.

\r\n", "Thus, there is only one solution to the equation, namely a^-1·b.

\r\n", " \r\n", "Return to text\r\n", "\r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 1.4:

\r\n", " \r\n", "To show that this definition is reflexive, we need to show that x ≡ x (mod n), which is \r\n", "clear since x − x = 0·n.

\r\n", "\r\n", "To show that this definition is symmetric, suppose that \r\n", "x ≡ y (mod n). Then x − y = k n for some integer k, hence y − x = −k n for the integer −k.\r\n", "Thus, y ≡ x (mod n).

\r\n", "\r\n", "Finally, to show that this definition is transitive, suppose both x ≡ y (mod n)\r\n", "and y ≡ z (mod n). Then x − y = k₁ n and \r\n", "y − z = k₂ n, so \r\n", "

x − z = (x − y) + (y − z) = \r\n", "k₁ n + k₂ n = (k₁ + k₂)n.

\r\n", " \r\n", "Hence, we find that x ≡ z (mod n).

\r\n", " \r\n", "Return to text\r\n", "\r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 1.5:

\r\n", " \r\n", "For any a ∈ S, we have by the reflexive property that a ∈ [a], so [a] is non-empty, and the union of all equivalence classes \r\n", "will be all of S. Next, let us show that if there is an element c in common with two equivalence classes [a] and [b], then these classes are \r\n", "the same. Since c ∼ a and c ∼ b, we have by the symmetric and transitive properties that a ∼ b. Hence, for \r\n", "every x ∈ [a], x ∼ a, so x ∈ [b] as well, indicating [a] ⊆ [b]. \r\n", "By similar logic, [b] ⊆ [a], so [a] = [b].

\r\n", " \r\n", "Return to text\r\n", "\r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 1.6:

\r\n", " \r\n", "Properties 2, 3, and 5 come from the properties of standard multiplication.

\r\n", "\r\n", "Property 1 comes from Proposition 1.2. If x and y are both invertible, then y^-1·x^-1 is an inverse of \r\n", "x·y, and so x·y is invertible modulo n.

\r\n", "\r\n", "Property 4 seems obvious, since if x is invertible modulo n, we let y = x^-1 making x·y = 1. But \r\n", "we must check \r\n", "that y is also invertible, which it is since y^-1 = x.

\r\n", " \r\n", "Return to text\r\n", "\r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 1.7:

\r\n", " \r\n", "If x and n are not coprime, then there is a common prime factor p. In order for x to have a multiplicative inverse, \r\n", "there must be a y such that\r\n", "

x·y ≡ 1 (mod n).

\r\n", "But this means that x y = 1 + w n for some w. This is impossible, since x y is a multiple of p, but 1 + w n is one \r\n", "more than a multiple of p.

\r\n", "\r\n", "Now suppose that x and n are coprime. By the greatest common divisor theorem (0.4), there are u and v in ℤ such that \r\n", "

u x + v n = gcd(x, n) = 1.

\r\n", "But then \r\n", "

u x = 1 + (−v) n,

\r\n", "and so u·x ≡ 1 (mod n). Hence, u is a multiplicative inverse of x.

\r\n", " \r\n", "Return to text\r\n", "\r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 1.8:

\r\n", " \r\n", "If m or n are 0, this proposition is very easy to verify:\r\n", "

x^m+0 = x^m = x^m·e = \r\n", "x^m·x⁰, x⁰⁺ⁿ = xⁿ = \r\n", "e·xⁿ = x⁰·xⁿ.

\r\n", "We will now prove the statement when m and n are positive integers. If n is 1, then we have\r\n", "

x^m+1 = x^(m+1)−1·x = \r\n", "x^m·x¹,

\r\n", "using the inductive definition of the power of x.

\r\n", "\r\n", "We will now proceed by means of induction. That is, we will assume that the statement is true for n = k − 1, and then prove that it is \r\n", "then true for n = k. Then we will have that, since the statement is true for n = 1, and it is true for each number that follows, \r\n", "it must be true for all positive n.

\r\n", "\r\n", "Thus, we will assume that \r\n", "

x^m+(k−1) = x^m·x^k−1.

\r\n", "But then\r\n", "

x^m+k = x^m+k−1·x = \r\n", "x^m·x^k−1·x = x^m·x^k.

\r\n", "Thus, by assuming the statement is true for n = k − 1, we found that it was also true for n = k. By induction, \r\n", "this proves that x^m+n = x^m·xⁿ for all positive n.

\r\n", "\r\n", "Once we have the statement true for positive m and n, we can take the inverse of both sides to give us\r\n", "

(x^m+n)^-1 = \r\n", "(xⁿ)^-1·(x^m)^-1.

\r\n", "But by the definition of negative exponents, this is\r\n", "

x^{(−n)+(−m)} = \r\n", "x⁻ⁿ·x^−m

\r\n", "which, by letting M = −n and N = −m, proves the proposition for the case of both exponents being negative.

\r\n", "\r\n", "Finally, if m and n have different signs, then (m + n) will either have the same sign as −n, or the same sign as \r\n", "−m. If (m + n) has the same sign as −n, then we have already shown that\r\n", "

x^m = x^(m+n)+(−n) = \r\n", "x^m+n·x⁻ⁿ.

\r\n", "So we have x^m·(x⁻ⁿ)^-1 = \r\n", "x^m+n·x⁻ⁿ·(x⁻ⁿ)^-1, and hence\r\n", "x^m+n = x^m·xⁿ.

\r\n", "\r\n", "If m + n has the same sign as −m, then we have already shown that\r\n", "

xⁿ = x^(−m)+(m+n) = \r\n", "x^−m·x^m+n.

\r\n", "So we have (x^−m)^-1·xⁿ = \r\n", "(x^−m)^-1·x^−m·x^m+n, and \r\n", "hence x^m+n = x^m·xⁿ.

\r\n", " \r\n", "Thus, we have proven the proposition for all integers m and n.

\r\n", " \r\n", "Return to text\r\n", "\r\n", "

\r\n", " \r\n", "\r\n", "\r\n", "Proof of Proposition 1.9:

\r\n", " \r\n", "Notice that this statement is trivial if n = 0 or n = 1:\r\n", "

(x^m)⁰ = e = x^m·0, \r\n", "(x^m)¹ = x^m = x^m·1

\r\n", "We will again proceed by means of induction, which means we can assume that the statement is true for the previous case, with n replaced by n − 1.\r\n", "That is, we can assume that\r\n", "

(x^m)ⁿ⁻¹ = x^m(n−1).

\r\n", "Note that\r\n", "

(x^m)ⁿ = \r\n", "(x^m)ⁿ⁻¹·x^m = \r\n", "x^m(n−1)·x^m.

\r\n", "By Proposition 1.8, this is equal to x^(m(n−1)+m) = x^{m n}.

\r\n", "\r\n", "So by induction, the proposition holds for positive n. To see that it holds for negative n as well, simply note that\r\n", "

(x^m)ⁿ = ((x^m)⁻ⁿ)^-1 = \r\n", "(x^{−m n})^-1 = x^{m n}.

\r\n", "If n is negative, then −n is positive, so the second step is valid.

\r\n", " \r\n", "Return to text\r\n", "\r\n", "

\r\n", "\r\n", " \r\n", "

Sage Interactive Problems

\r\n", "\r\n", "
\r\n", "§1.1 #13)
\r\n", "If Terry was only allowed to do the steps FlipRt or FlipLft, could it get itself into all six possible positions? If \r\n", "possible, expressthe other four dance steps in terms of these two. The following Sage command reloads Terry's group.
" ] }, { "cell_type": "code", "execution_count": 0, "metadata": { "collapsed": false }, "outputs": [ ], "source": [ "InitTerry()" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§1.1 #14)
\r\n", "Repeat Problem 13, only allow Terry to do only the steps RotRt or RotLft.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§1.1 #15)
\r\n", "Can you find a dance routine which includes each of Terry's 6 dance steps once, and only once, that puts Terry back into the initial position?
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§1.2 #21)
\r\n", "Proposition 1.7 explains how to use xgcd to find the multiplicative inverse modulo n.\r\n", "Use Sage to find the multiplicative inverse of a modulo n, where a = 3, n = 100.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§1.2 #22)
\r\n", "Repeat Problem 21, with a = 5, n = 121.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§1.2 #23)
\r\n", "Repeat Problem 21, with a = 7, n = 360.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§1.2 #24)
\r\n", "Repeat Problem 21, with a = 11, n = 900.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§1.2 #25)
\r\n", "Repeat Problem 21, with a = 13, n = 1200.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§1.2 #26)
\r\n", "Repeat Problem 21, with a = 17, n = 1500.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§1.2 #27)
\r\n", "We saw that there were exactly four numbers less than 10 which were invertible modulo 10. For what other values of n are there exactly four numbers less \r\n", "than n which are invertible modulo n? Use Sage's circle graph to graph the inverse functions.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§1.3 #28)
\r\n", "Use Sage's ZStar command to find the size of Z_n^* for n = 9, 27, 81, 243, 5, 25, 125. Make a conjecture \r\n", "about the size of Z_n^* when n is a power of an odd prime. Note use can use the len(_) command to have Sage count the elements for you.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§1.3 #29)
\r\n", "Use Sage's ZStar command to find the size of Z_n^* for n = 18, 54, 162, 486, 50, 250, 98, 686. Make a conjecture \r\n", "about the size of Z_n^* when n is twice the power of an odd prime.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "
\r\n", "§1.3 #30)
\r\n", "Use Sage's ZStar command to find the size of Z_mn^*, where m and n are coprime, in terms of the sizes \r\n", "of Z_m^* and Z_n^*.
" ] }, { "cell_type": "markdown", "metadata": { "collapsed": false }, "source": [ "\r\n", "\r\n", "\r\n", "\r\n", "" ] } ], "metadata": { "kernelspec": { "display_name": "SageMath (stable)", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.14" } }, "nbformat": 4, "nbformat_minor": 0 }