<section xml:id="section-mod-n-sym">
<title>Integer Equivalence Classes and Symmetries</title>
<author>
Carl Friedrich Gauß
</author>
<author>
Leonhard Euler
</author>
<introduction>
<p>
Let us now investigate some mathematical structures that can be viewed as sets with single operations.
</p>
</introduction>
<subsection>
<title>The Integers mod <m>n</m></title>
<author>
Gottfried Wilhelm Leibniz
</author>
<p>
The integers mod <m>n</m> have become indispensable in the theory and applications of algebra.
In mathematics they are used in cryptography, coding theory,
and the detection of errors in identification codes.
</p>
<p>
We have already seen that two integers <m>a</m> and <m>b</m> are equivalent mod <m>n</m> if <m>n</m> divides <m>a - b</m>.
The integers mod <m>n</m> also partition
<m>{\mathbb Z}</m> into <m>n</m> different equivalence classes;
we will denote the set of these equivalence classes by <m>{\mathbb Z}_n</m>.
<notation>
<usage><m>\mathbb Z_n</m></usage>
<description>the integers modulo <m>n</m></description>
</notation>
Consider the integers modulo 12 and the corresponding partition of the integers:
<md>
<mrow>{[0]} & = \{ \ldots, -12, 0, 12, 24, \ldots \}</mrow>
<mrow>{[1]} & = \{ \ldots, -11, 1, 13, 25, \ldots \}</mrow>
<mrow>& \vdots</mrow>
<mrow>{[11]} & = \{ \ldots, -1, 11, 23, 35, \ldots \}</mrow>
</md>.
</p>
<p>
When no confusion can arise,
we will use <m>0, 1, \ldots, 11</m> to indicate the equivalence classes <m>{[0]}, {[1]}, \ldots, {[11]}</m> respectively.
We can do arithmetic on <m>{\mathbb Z}_n</m>.
For two integers <m>a</m> and <m>b</m>,
define addition modulo <m>n</m> to be <m>(a + b) \pmod{n}</m>;
that is, the remainder when <m>a + b</m> is divided by <m>n</m>.
Similarly, multiplication modulo <m>n</m> is defined as <m>(a b) \pmod{ n}</m>,
the remainder when <m>a b</m> is divided by <m>n</m>.
</p>
<example xml:id="example-groups-zn-addition">
<title>Modular Addition</title>
<p>
The following examples illustrate integer arithmetic modulo <m>n</m>:
<md>
<mrow>7 + 4 & \equiv 1 \pmod{ 5} & 7 \cdot 3 & \equiv 1 \pmod{ 5}</mrow>
<mrow>3 + 5 & \equiv 0 \pmod{ 8} & 3 \cdot 5 & \equiv 7 \pmod{ 8}</mrow>
<mrow>3 + 4 & \equiv 7 \pmod{ 12} & 3 \cdot 4 & \equiv 0 \pmod{ 12}</mrow>
</md>.
</p>
<p>
In particular,
notice that it is possible that the product of two nonzero numbers modulo <m>n</m> can be equivalent to <m>0 </m> modulo <m>n</m>.
</p>
</example>
<example xml:id="example-groups-zn-arithmetic-laws">
<title>Modular Arithmetic</title>
<p>
Most, but not all,
of the usual laws of arithmetic hold for addition and multiplication in <m>{\mathbb Z}_n</m>.
For instance,
it is not necessarily true that there is a multiplicative inverse.
Consider the multiplication table for
<m>{\mathbb Z}_8</m> in <xref ref="figure-z8-mult" />.
Notice that 2, 4, and 6 do not have multiplicative inverses;
that is, for <m>n = 2</m>, 4, or 6, there is no integer <m>k</m> such that <m>k n \equiv 1 \pmod{ 8}</m>.
</p>
<figure xml:id="figure-z8-mult">
<caption>Multiplication table for <m>{\mathbb Z_8}</m></caption>
<p>
<me>
\begin{array}{c|cccccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 0 & 2 & 4 & 6 & 0 & 2 & 4 & 6 \\ 3 & 0 & 3 & 6 & 1 & 4 & 7 & 2 & 5 \\ 4 & 0 & 4 & 0 & 4 & 0 & 4 & 0 & 4 \\ 5 & 0 & 5 & 2 & 7 & 4 & 1 & 6 & 3 \\ 6 & 0 & 6 & 4 & 2 & 0 & 6 & 4 & 2 \\ 7 & 0 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{array}
</me>
</p>
</figure>
</example>
<proposition xml:id="proposition-zn-equiv-classes">
<statement>
<p>
Let <m>{\mathbb Z}_n</m> be the set of equivalence classes of the integers mod <m>n</m> and <m>a,
b, c \in {\mathbb Z}_n</m>.
<ol>
<li>
<p>
Addition and multiplication are commutative:
<md>
<mrow>a + b & \equiv b + a \pmod{ n}</mrow>
<mrow>a b & \equiv b a \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
Addition and multiplication are associative:
<md>
<mrow>(a + b) + c & \equiv a + (b + c)\pmod{ n}</mrow>
<mrow>(a b) c & \equiv a (b c) \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
There are both additive and multiplicative identities:
<md>
<mrow>a + 0 & \equiv a \pmod{ n}</mrow>
<mrow>a \cdot 1 & \equiv a \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
Multiplication distributes over addition:
<md>
<mrow>a (b + c) \equiv a b + a c \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
For every integer <m>a</m> there is an additive inverse <m>-a</m>:
<md>
<mrow>a + (-a) \equiv 0 \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
Let <m>a</m> be a nonzero integer.
Then <m>\gcd(a,n) = 1</m> if and only if there exists a multiplicative inverse <m>b</m> for <m>a \pmod{n}</m>;
that is, a nonzero integer <m>b</m> such that
<me>
a b \equiv 1 \pmod{ n}
</me>.
</p>
</li>
</ol>
</p>
</statement>
<proof>
<p>
We will prove (1) and (6) and leave the remaining properties to be proven in the exercises.
</p>
<p>
(1) Addition and multiplication are commutative modulo <m>n</m> since the remainder of <m>a + b</m> divided by <m>n</m> is the same as the remainder of <m>b + a</m> divided by <m>n</m>.
</p>
<p>
(6) Suppose that <m>\gcd(a, n) = 1</m>.
Then there exist integers <m>r</m> and <m>s</m> such that <m>ar + ns = 1</m>.
Since <m>ns = 1 - ar</m>,
it must be the case that <m>ar \equiv 1 \pmod{n}</m>.
Letting <m>b</m> be the equivalence class of <m>r</m>,
<m>a b \equiv 1\pmod{n}</m>.
</p>
<p>
Conversely, suppose that there exists an integer <m>b</m> such that <m>ab \equiv 1 \pmod{ n}</m>.
Then <m>n</m> divides <m>ab -1</m>,
so there is an integer <m>k</m> such that <m>ab - nk = 1</m>.
Let <m>d = \gcd(a,n)</m>.
Since <m>d</m> divides <m>ab - nk</m>,
<m>d</m> must also divide 1; hence, <m>d = 1</m>.
</p>
</proof>
</proposition>
</subsection>
<subsection>
<title>Symmetries</title>
<figure xml:id="figure-groups-rectangle">
<caption>Rigid motions of a rectangle</caption>
<image xml:id="groups-rectangle">
<latex-image>
\begin{tikzpicture}[scale=1.2]
\draw (-3,0) -- (-1.25,0) -- (-1.25,1) -- (-3,1) -- cycle;
\draw (3,0) -- (1.25,0) -- (1.25,1) -- (3,1) -- cycle;
\draw [->] (-1,0.5) -- (1,0.5);
\node [above] at (0,0.5) {\emph{reflection}};
\node [below] at (0,0.5) {\emph{horizontal axis}};
\node [above,left] at (-3,1) {$A$};
\node [below,left] at (-3,0) {$D$};
\node [above,right] at (-1.25,1) {$B$};
\node [below,right] at (-1.25,0) {$C$};
\node [above,right] at (3,1) {$C$};
\node [below,right] at (3,0) {$B$};
\node [above,left] at (1.25,1) {$D$};
\node [below,left] at (1.25,0) {$A$};
\draw (-3,2) -- (-1.25,2) -- (-1.25,3) -- (-3,3) -- cycle;
\draw (3,2) -- (1.25,2) -- (1.25,3) -- (3,3) -- cycle;
\draw [->] (-1,2.5) -- (1,2.5);
\node [above] at (0,2.5) {\emph{reflection}};
\node [below] at (0,2.5) {\emph{vertical axis}};
\node [above,left] at (-3,3) {$A$};
\node [below,left] at (-3,2) {$D$};
\node [above,right] at (-1.25,3) {$B$};
\node [below,right] at (-1.25,2) {$C$};
\node [above,right] at (3,3) {$A$};
\node [below,right] at (3,2) {$D$};
\node [above,left] at (1.25,3) {$B$};
\node [below,left] at (1.25,2) {$C$};
\draw (-3,4) -- (-1.25,4) -- (-1.25,5) -- (-3,5) -- cycle;
\draw (3,4) -- (1.25,4) -- (1.25,5) -- (3,5) -- cycle;
\draw [->] (-1,4.5) -- (1,4.5);
\node [above] at (0,4.5) {$180^\circ$};
\node [below] at (0,4.5) {\emph{rotation}};
\node [above,left] at (-3,5) {$A$};
\node [below,left] at (-3,4) {$D$};
\node [above,right] at (-1.25,5) {$B$};
\node [below,right] at (-1.25,4) {$C$};
\node [above,right] at (3,5) {$D$};
\node [below,right] at (3,4) {$A$};
\node [above,left] at (1.25,5) {$C$};
\node [below,left] at (1.25,4) {$B$};
\draw (-3,6) -- (-1.25,6) -- (-1.25,7) -- (-3,7) -- cycle;
\draw (3,6) -- (1.25,6) -- (1.25,7) -- (3,7) -- cycle;
\draw [->] (-1,6.5) -- (1,6.5);
\node [above] at (0,6.5) {\emph{identity}};
\node [above,left] at (-3,7) {$A$};
\node [below,left] at (-3,6) {$D$};
\node [above,right] at (-1.25,7) {$B$};
\node [below,right] at (-1.25,6) {$C$};
\node [above,right] at (3,7) {$B$};
\node [below,right] at (3,6) {$C$};
\node [above,left] at (1.25,7) {$A$};
\node [below,left] at (1.25,6) {$D$};
\end{tikzpicture}
</latex-image>
</image>
</figure>
<p>
A <term>symmetry</term> of a geometric figure is a rearrangement of the figure preserving the arrangement of its sides and vertices as well as its distances and angles.
A map from the plane to itself preserving the symmetry of an object is called a
<term>rigid motion</term>.
<idx><h>Rigid motion</h></idx>
For example,
if we look at the rectangle in <xref ref="figure-groups-rectangle" />,
it is easy to see that a rotation of <m>180^{\circ}</m> or
<m>360^{\circ}</m> returns a rectangle in the plane with the same orientation as the original rectangle and the same relationship among the vertices.
A reflection of the rectangle across either the vertical axis or the horizontal axis can also be seen to be a symmetry.
However, a <m>90^{\circ}</m> rotation in either direction cannot be a symmetry unless the rectangle is a square.
</p>
<figure xml:id="figure-s3-symmetry">
<caption>Symmetries of a triangle</caption>
<image xml:id="groups-s3-symmetry">
<latex-image>
\begin{tikzpicture}[scale=0.7]
\draw (0,0) -- (0:2) -- (60:2) -- cycle;
\node [left] at (0,0) {$A$};
\node at (1,2.1) {$B$};
\node [right] at (0:2) {$C$};
\draw [->] (2,1) -- (4,1);
\node [above] at (3,1) {\emph{reflection}};
\draw (4,0) -- (0:6) -- ++(120:2) -- cycle;
\node [left] at (4,0) {$B$};
\node [right] at (0:6) {$C$};
\node at (5,2.1) {$A$};
\node [right] at (7,1) {$ \mu_3 = \begin{pmatrix}A & B & C \\ B & A & C\end{pmatrix}$};
\draw (0,3) -- (2,3) -- ++(120:2) -- cycle;
\node [left] at (0,3) {$A$};
\node at (1,5.1) {$B$};
\node [right] at (2,3) {$C$};
\draw [->] (2,4) -- (4,4);
\node [above] at (3,4) {\emph{reflection}};
\draw (4,3) -- (6,3) -- ++(120:2) -- cycle;
\node [left] at (4,3) {$C$};
\node [right] at (6,3) {$A$};
\node at (5,5.1) {$B$};
\node [right] at (7,4) {$ \mu_2 = \begin{pmatrix}A & B & C \\ C & B & A\end{pmatrix}$};
\draw (0,6) -- (2,6) -- ++(120:2) -- cycle;
\node [left] at (0,6) {$A$};
\node at (1,8.1) {$B$};
\node [right] at (2,6) {$C$};
\draw [->] (2,7) -- (4,7);
\node [above] at (3,7) {\emph{reflection}};
\draw (4,6) -- (6,6) -- ++(120:2) -- cycle;
\node [left] at (4,6) {$A$};
\node [right] at (6,6) {$B$};
\node at (5,8.1) {$C$};
\node [right] at (7,7) {$ \mu_1 = \begin{pmatrix}A & B & C \\ A & C & B\end{pmatrix}$};
\draw (0,9) -- (2,9) -- ++(120:2) -- cycle;
\node [left] at (0,9) {$A$};
\node at (1,11.1) {$B$};
\node [right] at (2,9) {$C$};
\draw [->] (2,10) -- (4,10);
\node [above] at (3,10) {\emph{rotation}};
\draw (4,9) -- (6,9) -- ++(120:2) -- cycle;
\node [left] at (4,9) {$B$};
\node [right] at (6,9) {$A$};
\node at (5,11.1) {$C$};
\node [right] at (7,10) {$ \rho_2 = \begin{pmatrix}A & B & C \\ C & A & B\end{pmatrix}$};
\draw (0,12) -- (2,12) -- ++(120:2) -- cycle;
\node [left] at (0,12) {$A$};
\node at (1,14.1) {$B$};
\node [right] at (2,12) {$C$};
\draw [->] (2,13) -- (4,13);
\node [above] at (3,13) {\emph{rotation}};
\draw (4,12) -- (6,12) -- ++(120:2) -- cycle;
\node [left] at (4,12) {$C$};
\node [right] at (6,12) {$B$};
\node at (5,14.1) {$A$};
\node [right] at (7,13) {$ \rho_1 = \begin{pmatrix}A & B & C \\ B & C & A\end{pmatrix}$};
\draw (0,15) -- (2,15) -- ++(120:2) -- cycle;
\node [left] at (0,15) {$A$};
\node at (1,17.1) {$B$};
\node [right] at (2,15) {$C$};
\draw [->] (2,16) -- (4,16);
\node [above] at (3,16) {\emph{identity}};
\draw (4,15) -- (6,15) -- ++(120:2) -- cycle;
\node [left] at (4,15) {$A$};
\node [right] at (6,15) {$C$};
\node at (5,17.1) {$B$};
\node [right] at (7,16) {$ id = \begin{pmatrix}A & B & C \\ A & B & C\end{pmatrix}$};
\end{tikzpicture}
</latex-image>
</image>
</figure>
<p>
Let us find the symmetries of the equilateral triangle <m>\bigtriangleup ABC</m>.
To find a symmetry of <m>\bigtriangleup ABC</m>,
we must first examine the permutations of the vertices <m>A</m>,
<m>B</m>,
and <m>C</m> and then ask if a permutation extends to a symmetry of the triangle.
Recall that a <term>permutation</term>
of a set <m>S</m> is a one-to-one and onto map <m>\pi :S \rightarrow S</m>.
The three vertices have <m>3! = 6</m> permutations,
so the triangle has at most six symmetries.
To see that there are six permutations,
observe there are three different possibilities for the first vertex,
and two for the second,
and the remaining vertex is determined by the placement of the first two.
So we have <m>3 \cdot 2 \cdot 1 = 3! = 6</m> different arrangements.
To denote the permutation of the vertices of an equilateral triangle that sends <m>A</m> to <m>B</m>,
<m>B</m> to <m>C</m>, and <m>C</m> to <m>A</m>, we write the array
<me>
\begin{pmatrix} A & B & C \\ B & C & A \end{pmatrix}
</me>.
Notice that this particular permutation corresponds to the rigid motion of rotating the triangle by
<m>120^{\circ}</m> in a clockwise direction.
In fact, every permutation gives rise to a symmetry of the triangle.
All of these symmetries are shown in <xref ref="figure-s3-symmetry" />.
</p>
<p>
A natural question to ask is what happens if one motion of the triangle
<m>\bigtriangleup ABC</m> is followed by another.
Which symmetry is <m>\mu_1 \rho_1</m>;
that is, what happens when we do the permutation <m>\rho_1</m> and then the permutation <m>\mu_1</m>?
<em>Remember that we are composing functions here.
Although we usually multiply left to right,
we compose functions right to left.</em> We have
<md>
<mrow>(\mu_1 \rho_1)(A) & = \mu_1( \rho_1( A ) ) = \mu_1( B ) = C</mrow>
<mrow>(\mu_1 \rho_1)(B) & = \mu_1( \rho_1( B ) ) = \mu_1( C ) = B</mrow>
<mrow>(\mu_1 \rho_1)(C) & = \mu_1( \rho_1( C ) ) = \mu_1( A ) = A</mrow>
</md>.
</p>
<p>
This is the same symmetry as <m>\mu_2</m>.
Suppose we do these motions in the opposite order,
<m>\rho_1</m> then <m>\mu_1</m>.
It is easy to determine that this is the same as the symmetry <m>\mu_3</m>;
hence, <m>\rho_1 \mu_1 \neq \mu_1 \rho_1</m>.
A multiplication table for the symmetries of an equilateral triangle
<m>\bigtriangleup ABC</m> is given in <xref ref="figure-s3" />.
</p>
<p>
Notice that in the multiplication table for the symmetries of an equilateral triangle,
for every motion of the triangle <m>\alpha</m> there is another motion <m>\beta</m> such that <m>\alpha \beta = id</m>;
that is, for every motion there is another motion that takes the triangle back to its original orientation.
</p>
<figure xml:id="figure-s3">
<caption>Symmetries of an equilateral triangle</caption>
<p>
<me>
\begin{array}{c|cccccc} \circ & id & \rho_1 & \rho_2 & \mu_1 & \mu_2 & \mu_3 \\ \hline id & id & \rho_1 & \rho_2 & \mu_1 & \mu_2 & \mu_3 \\ \rho_1 & \rho_1 & \rho_2 & id & \mu_3 & \mu_1 & \mu_2 \\ \rho_2 & \rho_2 & id & \rho_1 & \mu_2 & \mu_3 & \mu_1 \\ \mu_1 & \mu_1 & \mu_2 & \mu_3 & id & \rho_1& \rho_2\\ \mu_2 & \mu_2 & \mu_3 & \mu_1 & \rho_2 & id & \rho_1\\ \mu_3 & \mu_3 & \mu_1 & \mu_2 & \rho_1 & \rho_2& id \end{array}
</me>
</p>
</figure>
</subsection>
</section>
Section 1.1 Integer Equivalence Classes and Symmetries
View Source for section
Let us now investigate some mathematical structures that can be viewed as sets with single operations.
Subsection 1.1.1 The Integers mod \(n\)
View Source for subsection
<subsection>
<title>The Integers mod <m>n</m></title>
<author>
Gottfried Wilhelm Leibniz
</author>
<p>
The integers mod <m>n</m> have become indispensable in the theory and applications of algebra.
In mathematics they are used in cryptography, coding theory,
and the detection of errors in identification codes.
</p>
<p>
We have already seen that two integers <m>a</m> and <m>b</m> are equivalent mod <m>n</m> if <m>n</m> divides <m>a - b</m>.
The integers mod <m>n</m> also partition
<m>{\mathbb Z}</m> into <m>n</m> different equivalence classes;
we will denote the set of these equivalence classes by <m>{\mathbb Z}_n</m>.
<notation>
<usage><m>\mathbb Z_n</m></usage>
<description>the integers modulo <m>n</m></description>
</notation>
Consider the integers modulo 12 and the corresponding partition of the integers:
<md>
<mrow>{[0]} & = \{ \ldots, -12, 0, 12, 24, \ldots \}</mrow>
<mrow>{[1]} & = \{ \ldots, -11, 1, 13, 25, \ldots \}</mrow>
<mrow>& \vdots</mrow>
<mrow>{[11]} & = \{ \ldots, -1, 11, 23, 35, \ldots \}</mrow>
</md>.
</p>
<p>
When no confusion can arise,
we will use <m>0, 1, \ldots, 11</m> to indicate the equivalence classes <m>{[0]}, {[1]}, \ldots, {[11]}</m> respectively.
We can do arithmetic on <m>{\mathbb Z}_n</m>.
For two integers <m>a</m> and <m>b</m>,
define addition modulo <m>n</m> to be <m>(a + b) \pmod{n}</m>;
that is, the remainder when <m>a + b</m> is divided by <m>n</m>.
Similarly, multiplication modulo <m>n</m> is defined as <m>(a b) \pmod{ n}</m>,
the remainder when <m>a b</m> is divided by <m>n</m>.
</p>
<example xml:id="example-groups-zn-addition">
<title>Modular Addition</title>
<p>
The following examples illustrate integer arithmetic modulo <m>n</m>:
<md>
<mrow>7 + 4 & \equiv 1 \pmod{ 5} & 7 \cdot 3 & \equiv 1 \pmod{ 5}</mrow>
<mrow>3 + 5 & \equiv 0 \pmod{ 8} & 3 \cdot 5 & \equiv 7 \pmod{ 8}</mrow>
<mrow>3 + 4 & \equiv 7 \pmod{ 12} & 3 \cdot 4 & \equiv 0 \pmod{ 12}</mrow>
</md>.
</p>
<p>
In particular,
notice that it is possible that the product of two nonzero numbers modulo <m>n</m> can be equivalent to <m>0 </m> modulo <m>n</m>.
</p>
</example>
<example xml:id="example-groups-zn-arithmetic-laws">
<title>Modular Arithmetic</title>
<p>
Most, but not all,
of the usual laws of arithmetic hold for addition and multiplication in <m>{\mathbb Z}_n</m>.
For instance,
it is not necessarily true that there is a multiplicative inverse.
Consider the multiplication table for
<m>{\mathbb Z}_8</m> in <xref ref="figure-z8-mult" />.
Notice that 2, 4, and 6 do not have multiplicative inverses;
that is, for <m>n = 2</m>, 4, or 6, there is no integer <m>k</m> such that <m>k n \equiv 1 \pmod{ 8}</m>.
</p>
<figure xml:id="figure-z8-mult">
<caption>Multiplication table for <m>{\mathbb Z_8}</m></caption>
<p>
<me>
\begin{array}{c|cccccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 0 & 2 & 4 & 6 & 0 & 2 & 4 & 6 \\ 3 & 0 & 3 & 6 & 1 & 4 & 7 & 2 & 5 \\ 4 & 0 & 4 & 0 & 4 & 0 & 4 & 0 & 4 \\ 5 & 0 & 5 & 2 & 7 & 4 & 1 & 6 & 3 \\ 6 & 0 & 6 & 4 & 2 & 0 & 6 & 4 & 2 \\ 7 & 0 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{array}
</me>
</p>
</figure>
</example>
<proposition xml:id="proposition-zn-equiv-classes">
<statement>
<p>
Let <m>{\mathbb Z}_n</m> be the set of equivalence classes of the integers mod <m>n</m> and <m>a,
b, c \in {\mathbb Z}_n</m>.
<ol>
<li>
<p>
Addition and multiplication are commutative:
<md>
<mrow>a + b & \equiv b + a \pmod{ n}</mrow>
<mrow>a b & \equiv b a \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
Addition and multiplication are associative:
<md>
<mrow>(a + b) + c & \equiv a + (b + c)\pmod{ n}</mrow>
<mrow>(a b) c & \equiv a (b c) \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
There are both additive and multiplicative identities:
<md>
<mrow>a + 0 & \equiv a \pmod{ n}</mrow>
<mrow>a \cdot 1 & \equiv a \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
Multiplication distributes over addition:
<md>
<mrow>a (b + c) \equiv a b + a c \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
For every integer <m>a</m> there is an additive inverse <m>-a</m>:
<md>
<mrow>a + (-a) \equiv 0 \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
Let <m>a</m> be a nonzero integer.
Then <m>\gcd(a,n) = 1</m> if and only if there exists a multiplicative inverse <m>b</m> for <m>a \pmod{n}</m>;
that is, a nonzero integer <m>b</m> such that
<me>
a b \equiv 1 \pmod{ n}
</me>.
</p>
</li>
</ol>
</p>
</statement>
<proof>
<p>
We will prove (1) and (6) and leave the remaining properties to be proven in the exercises.
</p>
<p>
(1) Addition and multiplication are commutative modulo <m>n</m> since the remainder of <m>a + b</m> divided by <m>n</m> is the same as the remainder of <m>b + a</m> divided by <m>n</m>.
</p>
<p>
(6) Suppose that <m>\gcd(a, n) = 1</m>.
Then there exist integers <m>r</m> and <m>s</m> such that <m>ar + ns = 1</m>.
Since <m>ns = 1 - ar</m>,
it must be the case that <m>ar \equiv 1 \pmod{n}</m>.
Letting <m>b</m> be the equivalence class of <m>r</m>,
<m>a b \equiv 1\pmod{n}</m>.
</p>
<p>
Conversely, suppose that there exists an integer <m>b</m> such that <m>ab \equiv 1 \pmod{ n}</m>.
Then <m>n</m> divides <m>ab -1</m>,
so there is an integer <m>k</m> such that <m>ab - nk = 1</m>.
Let <m>d = \gcd(a,n)</m>.
Since <m>d</m> divides <m>ab - nk</m>,
<m>d</m> must also divide 1; hence, <m>d = 1</m>.
</p>
</proof>
</proposition>
</subsection>
The integers mod \(n\) have become indispensable in the theory and applications of algebra. In mathematics they are used in cryptography, coding theory, and the detection of errors in identification codes.
We have already seen that two integers \(a\) and \(b\) are equivalent mod \(n\) if \(n\) divides \(a - b\text{.}\) The integers mod \(n\) also partition \({\mathbb Z}\) into \(n\) different equivalence classes; we will denote the set of these equivalence classes by \({\mathbb Z}_n\text{.}\) Consider the integers modulo 12 and the corresponding partition of the integers:
\begin{align*}
{[0]} & = \{ \ldots, -12, 0, 12, 24, \ldots \}\\
{[1]} & = \{ \ldots, -11, 1, 13, 25, \ldots \}\\
& \vdots\\
{[11]} & = \{ \ldots, -1, 11, 23, 35, \ldots \}\text{.}
\end{align*}
When no confusion can arise, we will use \(0, 1, \ldots, 11\) to indicate the equivalence classes \({[0]}, {[1]}, \ldots, {[11]}\) respectively. We can do arithmetic on \({\mathbb Z}_n\text{.}\) For two integers \(a\) and \(b\text{,}\) define addition modulo \(n\) to be \((a + b) \pmod{n}\text{;}\) that is, the remainder when \(a + b\) is divided by \(n\text{.}\) Similarly, multiplication modulo \(n\) is defined as \((a b) \pmod{ n}\text{,}\) the remainder when \(a b\) is divided by \(n\text{.}\)
Example 1.1.1. Modular Addition.
View Source for example
<example xml:id="example-groups-zn-addition">
<title>Modular Addition</title>
<p>
The following examples illustrate integer arithmetic modulo <m>n</m>:
<md>
<mrow>7 + 4 & \equiv 1 \pmod{ 5} & 7 \cdot 3 & \equiv 1 \pmod{ 5}</mrow>
<mrow>3 + 5 & \equiv 0 \pmod{ 8} & 3 \cdot 5 & \equiv 7 \pmod{ 8}</mrow>
<mrow>3 + 4 & \equiv 7 \pmod{ 12} & 3 \cdot 4 & \equiv 0 \pmod{ 12}</mrow>
</md>.
</p>
<p>
In particular,
notice that it is possible that the product of two nonzero numbers modulo <m>n</m> can be equivalent to <m>0 </m> modulo <m>n</m>.
</p>
</example>
The following examples illustrate integer arithmetic modulo \(n\text{:}\)
\begin{align*}
7 + 4 & \equiv 1 \pmod{ 5} & 7 \cdot 3 & \equiv 1 \pmod{ 5}\\
3 + 5 & \equiv 0 \pmod{ 8} & 3 \cdot 5 & \equiv 7 \pmod{ 8}\\
3 + 4 & \equiv 7 \pmod{ 12} & 3 \cdot 4 & \equiv 0 \pmod{ 12}\text{.}
\end{align*}
In particular, notice that it is possible that the product of two nonzero numbers modulo \(n\) can be equivalent to \(0 \) modulo \(n\text{.}\)
Example 1.1.2. Modular Arithmetic.
View Source for example
<example xml:id="example-groups-zn-arithmetic-laws">
<title>Modular Arithmetic</title>
<p>
Most, but not all,
of the usual laws of arithmetic hold for addition and multiplication in <m>{\mathbb Z}_n</m>.
For instance,
it is not necessarily true that there is a multiplicative inverse.
Consider the multiplication table for
<m>{\mathbb Z}_8</m> in <xref ref="figure-z8-mult" />.
Notice that 2, 4, and 6 do not have multiplicative inverses;
that is, for <m>n = 2</m>, 4, or 6, there is no integer <m>k</m> such that <m>k n \equiv 1 \pmod{ 8}</m>.
</p>
<figure xml:id="figure-z8-mult">
<caption>Multiplication table for <m>{\mathbb Z_8}</m></caption>
<p>
<me>
\begin{array}{c|cccccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 0 & 2 & 4 & 6 & 0 & 2 & 4 & 6 \\ 3 & 0 & 3 & 6 & 1 & 4 & 7 & 2 & 5 \\ 4 & 0 & 4 & 0 & 4 & 0 & 4 & 0 & 4 \\ 5 & 0 & 5 & 2 & 7 & 4 & 1 & 6 & 3 \\ 6 & 0 & 6 & 4 & 2 & 0 & 6 & 4 & 2 \\ 7 & 0 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{array}
</me>
</p>
</figure>
</example>
Most, but not all, of the usual laws of arithmetic hold for addition and multiplication in \({\mathbb Z}_n\text{.}\) For instance, it is not necessarily true that there is a multiplicative inverse. Consider the multiplication table for \({\mathbb Z}_8\) in Figure 1.1.3. Notice that 2, 4, and 6 do not have multiplicative inverses; that is, for \(n = 2\text{,}\) 4, or 6, there is no integer \(k\) such that \(k n \equiv 1 \pmod{ 8}\text{.}\)
View Source for figure
<figure xml:id="figure-z8-mult">
<caption>Multiplication table for <m>{\mathbb Z_8}</m></caption>
<p>
<me>
\begin{array}{c|cccccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 0 & 2 & 4 & 6 & 0 & 2 & 4 & 6 \\ 3 & 0 & 3 & 6 & 1 & 4 & 7 & 2 & 5 \\ 4 & 0 & 4 & 0 & 4 & 0 & 4 & 0 & 4 \\ 5 & 0 & 5 & 2 & 7 & 4 & 1 & 6 & 3 \\ 6 & 0 & 6 & 4 & 2 & 0 & 6 & 4 & 2 \\ 7 & 0 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{array}
</me>
</p>
</figure>
\begin{equation*}
\begin{array}{c|cccccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 0 & 2 & 4 & 6 & 0 & 2 & 4 & 6 \\ 3 & 0 & 3 & 6 & 1 & 4 & 7 & 2 & 5 \\ 4 & 0 & 4 & 0 & 4 & 0 & 4 & 0 & 4 \\ 5 & 0 & 5 & 2 & 7 & 4 & 1 & 6 & 3 \\ 6 & 0 & 6 & 4 & 2 & 0 & 6 & 4 & 2 \\ 7 & 0 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \end{array}
\end{equation*}
Proposition 1.1.4.
View Source for proposition
<proposition xml:id="proposition-zn-equiv-classes">
<statement>
<p>
Let <m>{\mathbb Z}_n</m> be the set of equivalence classes of the integers mod <m>n</m> and <m>a,
b, c \in {\mathbb Z}_n</m>.
<ol>
<li>
<p>
Addition and multiplication are commutative:
<md>
<mrow>a + b & \equiv b + a \pmod{ n}</mrow>
<mrow>a b & \equiv b a \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
Addition and multiplication are associative:
<md>
<mrow>(a + b) + c & \equiv a + (b + c)\pmod{ n}</mrow>
<mrow>(a b) c & \equiv a (b c) \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
There are both additive and multiplicative identities:
<md>
<mrow>a + 0 & \equiv a \pmod{ n}</mrow>
<mrow>a \cdot 1 & \equiv a \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
Multiplication distributes over addition:
<md>
<mrow>a (b + c) \equiv a b + a c \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
For every integer <m>a</m> there is an additive inverse <m>-a</m>:
<md>
<mrow>a + (-a) \equiv 0 \pmod{ n}</mrow>
</md>.
</p>
</li>
<li>
<p>
Let <m>a</m> be a nonzero integer.
Then <m>\gcd(a,n) = 1</m> if and only if there exists a multiplicative inverse <m>b</m> for <m>a \pmod{n}</m>;
that is, a nonzero integer <m>b</m> such that
<me>
a b \equiv 1 \pmod{ n}
</me>.
</p>
</li>
</ol>
</p>
</statement>
<proof>
<p>
We will prove (1) and (6) and leave the remaining properties to be proven in the exercises.
</p>
<p>
(1) Addition and multiplication are commutative modulo <m>n</m> since the remainder of <m>a + b</m> divided by <m>n</m> is the same as the remainder of <m>b + a</m> divided by <m>n</m>.
</p>
<p>
(6) Suppose that <m>\gcd(a, n) = 1</m>.
Then there exist integers <m>r</m> and <m>s</m> such that <m>ar + ns = 1</m>.
Since <m>ns = 1 - ar</m>,
it must be the case that <m>ar \equiv 1 \pmod{n}</m>.
Letting <m>b</m> be the equivalence class of <m>r</m>,
<m>a b \equiv 1\pmod{n}</m>.
</p>
<p>
Conversely, suppose that there exists an integer <m>b</m> such that <m>ab \equiv 1 \pmod{ n}</m>.
Then <m>n</m> divides <m>ab -1</m>,
so there is an integer <m>k</m> such that <m>ab - nk = 1</m>.
Let <m>d = \gcd(a,n)</m>.
Since <m>d</m> divides <m>ab - nk</m>,
<m>d</m> must also divide 1; hence, <m>d = 1</m>.
</p>
</proof>
</proposition>
Let \({\mathbb Z}_n\) be the set of equivalence classes of the integers mod \(n\) and \(a,
b, c \in {\mathbb Z}_n\text{.}\)
- Addition and multiplication are commutative:\begin{align*} a + b & \equiv b + a \pmod{ n}\\ a b & \equiv b a \pmod{ n}\text{.} \end{align*}
- Addition and multiplication are associative:\begin{align*} (a + b) + c & \equiv a + (b + c)\pmod{ n}\\ (a b) c & \equiv a (b c) \pmod{ n}\text{.} \end{align*}
- There are both additive and multiplicative identities:\begin{align*} a + 0 & \equiv a \pmod{ n}\\ a \cdot 1 & \equiv a \pmod{ n}\text{.} \end{align*}
- Multiplication distributes over addition:\begin{gather*} a (b + c) \equiv a b + a c \pmod{ n}\text{.} \end{gather*}
- For every integer \(a\) there is an additive inverse \(-a\text{:}\)\begin{gather*} a + (-a) \equiv 0 \pmod{ n}\text{.} \end{gather*}
- Let \(a\) be a nonzero integer. Then \(\gcd(a,n) = 1\) if and only if there exists a multiplicative inverse \(b\) for \(a \pmod{n}\text{;}\) that is, a nonzero integer \(b\) such that\begin{equation*} a b \equiv 1 \pmod{ n}\text{.} \end{equation*}
Proof.
View Source for proof
<proof>
<p>
We will prove (1) and (6) and leave the remaining properties to be proven in the exercises.
</p>
<p>
(1) Addition and multiplication are commutative modulo <m>n</m> since the remainder of <m>a + b</m> divided by <m>n</m> is the same as the remainder of <m>b + a</m> divided by <m>n</m>.
</p>
<p>
(6) Suppose that <m>\gcd(a, n) = 1</m>.
Then there exist integers <m>r</m> and <m>s</m> such that <m>ar + ns = 1</m>.
Since <m>ns = 1 - ar</m>,
it must be the case that <m>ar \equiv 1 \pmod{n}</m>.
Letting <m>b</m> be the equivalence class of <m>r</m>,
<m>a b \equiv 1\pmod{n}</m>.
</p>
<p>
Conversely, suppose that there exists an integer <m>b</m> such that <m>ab \equiv 1 \pmod{ n}</m>.
Then <m>n</m> divides <m>ab -1</m>,
so there is an integer <m>k</m> such that <m>ab - nk = 1</m>.
Let <m>d = \gcd(a,n)</m>.
Since <m>d</m> divides <m>ab - nk</m>,
<m>d</m> must also divide 1; hence, <m>d = 1</m>.
</p>
</proof>
We will prove (1) and (6) and leave the remaining properties to be proven in the exercises.
(1) Addition and multiplication are commutative modulo \(n\) since the remainder of \(a + b\) divided by \(n\) is the same as the remainder of \(b + a\) divided by \(n\text{.}\)
(6) Suppose that \(\gcd(a, n) = 1\text{.}\) Then there exist integers \(r\) and \(s\) such that \(ar + ns = 1\text{.}\) Since \(ns = 1 - ar\text{,}\) it must be the case that \(ar \equiv 1 \pmod{n}\text{.}\) Letting \(b\) be the equivalence class of \(r\text{,}\) \(a b \equiv 1\pmod{n}\text{.}\)
Conversely, suppose that there exists an integer \(b\) such that \(ab \equiv 1 \pmod{ n}\text{.}\) Then \(n\) divides \(ab -1\text{,}\) so there is an integer \(k\) such that \(ab - nk = 1\text{.}\) Let \(d = \gcd(a,n)\text{.}\) Since \(d\) divides \(ab - nk\text{,}\) \(d\) must also divide 1; hence, \(d = 1\text{.}\)
Subsection 1.1.2 Symmetries
View Source for subsection
<subsection>
<title>Symmetries</title>
<figure xml:id="figure-groups-rectangle">
<caption>Rigid motions of a rectangle</caption>
<image xml:id="groups-rectangle">
<latex-image>
\begin{tikzpicture}[scale=1.2]
\draw (-3,0) -- (-1.25,0) -- (-1.25,1) -- (-3,1) -- cycle;
\draw (3,0) -- (1.25,0) -- (1.25,1) -- (3,1) -- cycle;
\draw [->] (-1,0.5) -- (1,0.5);
\node [above] at (0,0.5) {\emph{reflection}};
\node [below] at (0,0.5) {\emph{horizontal axis}};
\node [above,left] at (-3,1) {$A$};
\node [below,left] at (-3,0) {$D$};
\node [above,right] at (-1.25,1) {$B$};
\node [below,right] at (-1.25,0) {$C$};
\node [above,right] at (3,1) {$C$};
\node [below,right] at (3,0) {$B$};
\node [above,left] at (1.25,1) {$D$};
\node [below,left] at (1.25,0) {$A$};
\draw (-3,2) -- (-1.25,2) -- (-1.25,3) -- (-3,3) -- cycle;
\draw (3,2) -- (1.25,2) -- (1.25,3) -- (3,3) -- cycle;
\draw [->] (-1,2.5) -- (1,2.5);
\node [above] at (0,2.5) {\emph{reflection}};
\node [below] at (0,2.5) {\emph{vertical axis}};
\node [above,left] at (-3,3) {$A$};
\node [below,left] at (-3,2) {$D$};
\node [above,right] at (-1.25,3) {$B$};
\node [below,right] at (-1.25,2) {$C$};
\node [above,right] at (3,3) {$A$};
\node [below,right] at (3,2) {$D$};
\node [above,left] at (1.25,3) {$B$};
\node [below,left] at (1.25,2) {$C$};
\draw (-3,4) -- (-1.25,4) -- (-1.25,5) -- (-3,5) -- cycle;
\draw (3,4) -- (1.25,4) -- (1.25,5) -- (3,5) -- cycle;
\draw [->] (-1,4.5) -- (1,4.5);
\node [above] at (0,4.5) {$180^\circ$};
\node [below] at (0,4.5) {\emph{rotation}};
\node [above,left] at (-3,5) {$A$};
\node [below,left] at (-3,4) {$D$};
\node [above,right] at (-1.25,5) {$B$};
\node [below,right] at (-1.25,4) {$C$};
\node [above,right] at (3,5) {$D$};
\node [below,right] at (3,4) {$A$};
\node [above,left] at (1.25,5) {$C$};
\node [below,left] at (1.25,4) {$B$};
\draw (-3,6) -- (-1.25,6) -- (-1.25,7) -- (-3,7) -- cycle;
\draw (3,6) -- (1.25,6) -- (1.25,7) -- (3,7) -- cycle;
\draw [->] (-1,6.5) -- (1,6.5);
\node [above] at (0,6.5) {\emph{identity}};
\node [above,left] at (-3,7) {$A$};
\node [below,left] at (-3,6) {$D$};
\node [above,right] at (-1.25,7) {$B$};
\node [below,right] at (-1.25,6) {$C$};
\node [above,right] at (3,7) {$B$};
\node [below,right] at (3,6) {$C$};
\node [above,left] at (1.25,7) {$A$};
\node [below,left] at (1.25,6) {$D$};
\end{tikzpicture}
</latex-image>
</image>
</figure>
<p>
A <term>symmetry</term> of a geometric figure is a rearrangement of the figure preserving the arrangement of its sides and vertices as well as its distances and angles.
A map from the plane to itself preserving the symmetry of an object is called a
<term>rigid motion</term>.
<idx><h>Rigid motion</h></idx>
For example,
if we look at the rectangle in <xref ref="figure-groups-rectangle" />,
it is easy to see that a rotation of <m>180^{\circ}</m> or
<m>360^{\circ}</m> returns a rectangle in the plane with the same orientation as the original rectangle and the same relationship among the vertices.
A reflection of the rectangle across either the vertical axis or the horizontal axis can also be seen to be a symmetry.
However, a <m>90^{\circ}</m> rotation in either direction cannot be a symmetry unless the rectangle is a square.
</p>
<figure xml:id="figure-s3-symmetry">
<caption>Symmetries of a triangle</caption>
<image xml:id="groups-s3-symmetry">
<latex-image>
\begin{tikzpicture}[scale=0.7]
\draw (0,0) -- (0:2) -- (60:2) -- cycle;
\node [left] at (0,0) {$A$};
\node at (1,2.1) {$B$};
\node [right] at (0:2) {$C$};
\draw [->] (2,1) -- (4,1);
\node [above] at (3,1) {\emph{reflection}};
\draw (4,0) -- (0:6) -- ++(120:2) -- cycle;
\node [left] at (4,0) {$B$};
\node [right] at (0:6) {$C$};
\node at (5,2.1) {$A$};
\node [right] at (7,1) {$ \mu_3 = \begin{pmatrix}A & B & C \\ B & A & C\end{pmatrix}$};
\draw (0,3) -- (2,3) -- ++(120:2) -- cycle;
\node [left] at (0,3) {$A$};
\node at (1,5.1) {$B$};
\node [right] at (2,3) {$C$};
\draw [->] (2,4) -- (4,4);
\node [above] at (3,4) {\emph{reflection}};
\draw (4,3) -- (6,3) -- ++(120:2) -- cycle;
\node [left] at (4,3) {$C$};
\node [right] at (6,3) {$A$};
\node at (5,5.1) {$B$};
\node [right] at (7,4) {$ \mu_2 = \begin{pmatrix}A & B & C \\ C & B & A\end{pmatrix}$};
\draw (0,6) -- (2,6) -- ++(120:2) -- cycle;
\node [left] at (0,6) {$A$};
\node at (1,8.1) {$B$};
\node [right] at (2,6) {$C$};
\draw [->] (2,7) -- (4,7);
\node [above] at (3,7) {\emph{reflection}};
\draw (4,6) -- (6,6) -- ++(120:2) -- cycle;
\node [left] at (4,6) {$A$};
\node [right] at (6,6) {$B$};
\node at (5,8.1) {$C$};
\node [right] at (7,7) {$ \mu_1 = \begin{pmatrix}A & B & C \\ A & C & B\end{pmatrix}$};
\draw (0,9) -- (2,9) -- ++(120:2) -- cycle;
\node [left] at (0,9) {$A$};
\node at (1,11.1) {$B$};
\node [right] at (2,9) {$C$};
\draw [->] (2,10) -- (4,10);
\node [above] at (3,10) {\emph{rotation}};
\draw (4,9) -- (6,9) -- ++(120:2) -- cycle;
\node [left] at (4,9) {$B$};
\node [right] at (6,9) {$A$};
\node at (5,11.1) {$C$};
\node [right] at (7,10) {$ \rho_2 = \begin{pmatrix}A & B & C \\ C & A & B\end{pmatrix}$};
\draw (0,12) -- (2,12) -- ++(120:2) -- cycle;
\node [left] at (0,12) {$A$};
\node at (1,14.1) {$B$};
\node [right] at (2,12) {$C$};
\draw [->] (2,13) -- (4,13);
\node [above] at (3,13) {\emph{rotation}};
\draw (4,12) -- (6,12) -- ++(120:2) -- cycle;
\node [left] at (4,12) {$C$};
\node [right] at (6,12) {$B$};
\node at (5,14.1) {$A$};
\node [right] at (7,13) {$ \rho_1 = \begin{pmatrix}A & B & C \\ B & C & A\end{pmatrix}$};
\draw (0,15) -- (2,15) -- ++(120:2) -- cycle;
\node [left] at (0,15) {$A$};
\node at (1,17.1) {$B$};
\node [right] at (2,15) {$C$};
\draw [->] (2,16) -- (4,16);
\node [above] at (3,16) {\emph{identity}};
\draw (4,15) -- (6,15) -- ++(120:2) -- cycle;
\node [left] at (4,15) {$A$};
\node [right] at (6,15) {$C$};
\node at (5,17.1) {$B$};
\node [right] at (7,16) {$ id = \begin{pmatrix}A & B & C \\ A & B & C\end{pmatrix}$};
\end{tikzpicture}
</latex-image>
</image>
</figure>
<p>
Let us find the symmetries of the equilateral triangle <m>\bigtriangleup ABC</m>.
To find a symmetry of <m>\bigtriangleup ABC</m>,
we must first examine the permutations of the vertices <m>A</m>,
<m>B</m>,
and <m>C</m> and then ask if a permutation extends to a symmetry of the triangle.
Recall that a <term>permutation</term>
of a set <m>S</m> is a one-to-one and onto map <m>\pi :S \rightarrow S</m>.
The three vertices have <m>3! = 6</m> permutations,
so the triangle has at most six symmetries.
To see that there are six permutations,
observe there are three different possibilities for the first vertex,
and two for the second,
and the remaining vertex is determined by the placement of the first two.
So we have <m>3 \cdot 2 \cdot 1 = 3! = 6</m> different arrangements.
To denote the permutation of the vertices of an equilateral triangle that sends <m>A</m> to <m>B</m>,
<m>B</m> to <m>C</m>, and <m>C</m> to <m>A</m>, we write the array
<me>
\begin{pmatrix} A & B & C \\ B & C & A \end{pmatrix}
</me>.
Notice that this particular permutation corresponds to the rigid motion of rotating the triangle by
<m>120^{\circ}</m> in a clockwise direction.
In fact, every permutation gives rise to a symmetry of the triangle.
All of these symmetries are shown in <xref ref="figure-s3-symmetry" />.
</p>
<p>
A natural question to ask is what happens if one motion of the triangle
<m>\bigtriangleup ABC</m> is followed by another.
Which symmetry is <m>\mu_1 \rho_1</m>;
that is, what happens when we do the permutation <m>\rho_1</m> and then the permutation <m>\mu_1</m>?
<em>Remember that we are composing functions here.
Although we usually multiply left to right,
we compose functions right to left.</em> We have
<md>
<mrow>(\mu_1 \rho_1)(A) & = \mu_1( \rho_1( A ) ) = \mu_1( B ) = C</mrow>
<mrow>(\mu_1 \rho_1)(B) & = \mu_1( \rho_1( B ) ) = \mu_1( C ) = B</mrow>
<mrow>(\mu_1 \rho_1)(C) & = \mu_1( \rho_1( C ) ) = \mu_1( A ) = A</mrow>
</md>.
</p>
<p>
This is the same symmetry as <m>\mu_2</m>.
Suppose we do these motions in the opposite order,
<m>\rho_1</m> then <m>\mu_1</m>.
It is easy to determine that this is the same as the symmetry <m>\mu_3</m>;
hence, <m>\rho_1 \mu_1 \neq \mu_1 \rho_1</m>.
A multiplication table for the symmetries of an equilateral triangle
<m>\bigtriangleup ABC</m> is given in <xref ref="figure-s3" />.
</p>
<p>
Notice that in the multiplication table for the symmetries of an equilateral triangle,
for every motion of the triangle <m>\alpha</m> there is another motion <m>\beta</m> such that <m>\alpha \beta = id</m>;
that is, for every motion there is another motion that takes the triangle back to its original orientation.
</p>
<figure xml:id="figure-s3">
<caption>Symmetries of an equilateral triangle</caption>
<p>
<me>
\begin{array}{c|cccccc} \circ & id & \rho_1 & \rho_2 & \mu_1 & \mu_2 & \mu_3 \\ \hline id & id & \rho_1 & \rho_2 & \mu_1 & \mu_2 & \mu_3 \\ \rho_1 & \rho_1 & \rho_2 & id & \mu_3 & \mu_1 & \mu_2 \\ \rho_2 & \rho_2 & id & \rho_1 & \mu_2 & \mu_3 & \mu_1 \\ \mu_1 & \mu_1 & \mu_2 & \mu_3 & id & \rho_1& \rho_2\\ \mu_2 & \mu_2 & \mu_3 & \mu_1 & \rho_2 & id & \rho_1\\ \mu_3 & \mu_3 & \mu_1 & \mu_2 & \rho_1 & \rho_2& id \end{array}
</me>
</p>
</figure>
</subsection>
View Source for figure
<figure xml:id="figure-groups-rectangle">
<caption>Rigid motions of a rectangle</caption>
<image xml:id="groups-rectangle">
<latex-image>
\begin{tikzpicture}[scale=1.2]
\draw (-3,0) -- (-1.25,0) -- (-1.25,1) -- (-3,1) -- cycle;
\draw (3,0) -- (1.25,0) -- (1.25,1) -- (3,1) -- cycle;
\draw [->] (-1,0.5) -- (1,0.5);
\node [above] at (0,0.5) {\emph{reflection}};
\node [below] at (0,0.5) {\emph{horizontal axis}};
\node [above,left] at (-3,1) {$A$};
\node [below,left] at (-3,0) {$D$};
\node [above,right] at (-1.25,1) {$B$};
\node [below,right] at (-1.25,0) {$C$};
\node [above,right] at (3,1) {$C$};
\node [below,right] at (3,0) {$B$};
\node [above,left] at (1.25,1) {$D$};
\node [below,left] at (1.25,0) {$A$};
\draw (-3,2) -- (-1.25,2) -- (-1.25,3) -- (-3,3) -- cycle;
\draw (3,2) -- (1.25,2) -- (1.25,3) -- (3,3) -- cycle;
\draw [->] (-1,2.5) -- (1,2.5);
\node [above] at (0,2.5) {\emph{reflection}};
\node [below] at (0,2.5) {\emph{vertical axis}};
\node [above,left] at (-3,3) {$A$};
\node [below,left] at (-3,2) {$D$};
\node [above,right] at (-1.25,3) {$B$};
\node [below,right] at (-1.25,2) {$C$};
\node [above,right] at (3,3) {$A$};
\node [below,right] at (3,2) {$D$};
\node [above,left] at (1.25,3) {$B$};
\node [below,left] at (1.25,2) {$C$};
\draw (-3,4) -- (-1.25,4) -- (-1.25,5) -- (-3,5) -- cycle;
\draw (3,4) -- (1.25,4) -- (1.25,5) -- (3,5) -- cycle;
\draw [->] (-1,4.5) -- (1,4.5);
\node [above] at (0,4.5) {$180^\circ$};
\node [below] at (0,4.5) {\emph{rotation}};
\node [above,left] at (-3,5) {$A$};
\node [below,left] at (-3,4) {$D$};
\node [above,right] at (-1.25,5) {$B$};
\node [below,right] at (-1.25,4) {$C$};
\node [above,right] at (3,5) {$D$};
\node [below,right] at (3,4) {$A$};
\node [above,left] at (1.25,5) {$C$};
\node [below,left] at (1.25,4) {$B$};
\draw (-3,6) -- (-1.25,6) -- (-1.25,7) -- (-3,7) -- cycle;
\draw (3,6) -- (1.25,6) -- (1.25,7) -- (3,7) -- cycle;
\draw [->] (-1,6.5) -- (1,6.5);
\node [above] at (0,6.5) {\emph{identity}};
\node [above,left] at (-3,7) {$A$};
\node [below,left] at (-3,6) {$D$};
\node [above,right] at (-1.25,7) {$B$};
\node [below,right] at (-1.25,6) {$C$};
\node [above,right] at (3,7) {$B$};
\node [below,right] at (3,6) {$C$};
\node [above,left] at (1.25,7) {$A$};
\node [below,left] at (1.25,6) {$D$};
\end{tikzpicture}
</latex-image>
</image>
</figure>
A symmetry of a geometric figure is a rearrangement of the figure preserving the arrangement of its sides and vertices as well as its distances and angles. A map from the plane to itself preserving the symmetry of an object is called a rigid motion. For example, if we look at the rectangle in Figure 1.1.5, it is easy to see that a rotation of \(180^{\circ}\) or \(360^{\circ}\) returns a rectangle in the plane with the same orientation as the original rectangle and the same relationship among the vertices. A reflection of the rectangle across either the vertical axis or the horizontal axis can also be seen to be a symmetry. However, a \(90^{\circ}\) rotation in either direction cannot be a symmetry unless the rectangle is a square.
View Source for figure
<figure xml:id="figure-s3-symmetry">
<caption>Symmetries of a triangle</caption>
<image xml:id="groups-s3-symmetry">
<latex-image>
\begin{tikzpicture}[scale=0.7]
\draw (0,0) -- (0:2) -- (60:2) -- cycle;
\node [left] at (0,0) {$A$};
\node at (1,2.1) {$B$};
\node [right] at (0:2) {$C$};
\draw [->] (2,1) -- (4,1);
\node [above] at (3,1) {\emph{reflection}};
\draw (4,0) -- (0:6) -- ++(120:2) -- cycle;
\node [left] at (4,0) {$B$};
\node [right] at (0:6) {$C$};
\node at (5,2.1) {$A$};
\node [right] at (7,1) {$ \mu_3 = \begin{pmatrix}A & B & C \\ B & A & C\end{pmatrix}$};
\draw (0,3) -- (2,3) -- ++(120:2) -- cycle;
\node [left] at (0,3) {$A$};
\node at (1,5.1) {$B$};
\node [right] at (2,3) {$C$};
\draw [->] (2,4) -- (4,4);
\node [above] at (3,4) {\emph{reflection}};
\draw (4,3) -- (6,3) -- ++(120:2) -- cycle;
\node [left] at (4,3) {$C$};
\node [right] at (6,3) {$A$};
\node at (5,5.1) {$B$};
\node [right] at (7,4) {$ \mu_2 = \begin{pmatrix}A & B & C \\ C & B & A\end{pmatrix}$};
\draw (0,6) -- (2,6) -- ++(120:2) -- cycle;
\node [left] at (0,6) {$A$};
\node at (1,8.1) {$B$};
\node [right] at (2,6) {$C$};
\draw [->] (2,7) -- (4,7);
\node [above] at (3,7) {\emph{reflection}};
\draw (4,6) -- (6,6) -- ++(120:2) -- cycle;
\node [left] at (4,6) {$A$};
\node [right] at (6,6) {$B$};
\node at (5,8.1) {$C$};
\node [right] at (7,7) {$ \mu_1 = \begin{pmatrix}A & B & C \\ A & C & B\end{pmatrix}$};
\draw (0,9) -- (2,9) -- ++(120:2) -- cycle;
\node [left] at (0,9) {$A$};
\node at (1,11.1) {$B$};
\node [right] at (2,9) {$C$};
\draw [->] (2,10) -- (4,10);
\node [above] at (3,10) {\emph{rotation}};
\draw (4,9) -- (6,9) -- ++(120:2) -- cycle;
\node [left] at (4,9) {$B$};
\node [right] at (6,9) {$A$};
\node at (5,11.1) {$C$};
\node [right] at (7,10) {$ \rho_2 = \begin{pmatrix}A & B & C \\ C & A & B\end{pmatrix}$};
\draw (0,12) -- (2,12) -- ++(120:2) -- cycle;
\node [left] at (0,12) {$A$};
\node at (1,14.1) {$B$};
\node [right] at (2,12) {$C$};
\draw [->] (2,13) -- (4,13);
\node [above] at (3,13) {\emph{rotation}};
\draw (4,12) -- (6,12) -- ++(120:2) -- cycle;
\node [left] at (4,12) {$C$};
\node [right] at (6,12) {$B$};
\node at (5,14.1) {$A$};
\node [right] at (7,13) {$ \rho_1 = \begin{pmatrix}A & B & C \\ B & C & A\end{pmatrix}$};
\draw (0,15) -- (2,15) -- ++(120:2) -- cycle;
\node [left] at (0,15) {$A$};
\node at (1,17.1) {$B$};
\node [right] at (2,15) {$C$};
\draw [->] (2,16) -- (4,16);
\node [above] at (3,16) {\emph{identity}};
\draw (4,15) -- (6,15) -- ++(120:2) -- cycle;
\node [left] at (4,15) {$A$};
\node [right] at (6,15) {$C$};
\node at (5,17.1) {$B$};
\node [right] at (7,16) {$ id = \begin{pmatrix}A & B & C \\ A & B & C\end{pmatrix}$};
\end{tikzpicture}
</latex-image>
</image>
</figure>
Let us find the symmetries of the equilateral triangle \(\bigtriangleup ABC\text{.}\) To find a symmetry of \(\bigtriangleup ABC\text{,}\) we must first examine the permutations of the vertices \(A\text{,}\) \(B\text{,}\) and \(C\) and then ask if a permutation extends to a symmetry of the triangle. Recall that a permutation of a set \(S\) is a one-to-one and onto map \(\pi :S \rightarrow S\text{.}\) The three vertices have \(3! = 6\) permutations, so the triangle has at most six symmetries. To see that there are six permutations, observe there are three different possibilities for the first vertex, and two for the second, and the remaining vertex is determined by the placement of the first two. So we have \(3 \cdot 2 \cdot 1 = 3! = 6\) different arrangements. To denote the permutation of the vertices of an equilateral triangle that sends \(A\) to \(B\text{,}\) \(B\) to \(C\text{,}\) and \(C\) to \(A\text{,}\) we write the array
\begin{equation*}
\begin{pmatrix} A & B & C \\ B & C & A \end{pmatrix}\text{.}
\end{equation*}
Notice that this particular permutation corresponds to the rigid motion of rotating the triangle by \(120^{\circ}\) in a clockwise direction. In fact, every permutation gives rise to a symmetry of the triangle. All of these symmetries are shown in Figure 1.1.6.
A natural question to ask is what happens if one motion of the triangle \(\bigtriangleup ABC\) is followed by another. Which symmetry is \(\mu_1 \rho_1\text{;}\) that is, what happens when we do the permutation \(\rho_1\) and then the permutation \(\mu_1\text{?}\) Remember that we are composing functions here. Although we usually multiply left to right, we compose functions right to left. We have
\begin{align*}
(\mu_1 \rho_1)(A) & = \mu_1( \rho_1( A ) ) = \mu_1( B ) = C\\
(\mu_1 \rho_1)(B) & = \mu_1( \rho_1( B ) ) = \mu_1( C ) = B\\
(\mu_1 \rho_1)(C) & = \mu_1( \rho_1( C ) ) = \mu_1( A ) = A\text{.}
\end{align*}
This is the same symmetry as \(\mu_2\text{.}\) Suppose we do these motions in the opposite order, \(\rho_1\) then \(\mu_1\text{.}\) It is easy to determine that this is the same as the symmetry \(\mu_3\text{;}\) hence, \(\rho_1 \mu_1 \neq \mu_1 \rho_1\text{.}\) A multiplication table for the symmetries of an equilateral triangle \(\bigtriangleup ABC\) is given in Figure 1.1.7.
Notice that in the multiplication table for the symmetries of an equilateral triangle, for every motion of the triangle \(\alpha\) there is another motion \(\beta\) such that \(\alpha \beta = id\text{;}\) that is, for every motion there is another motion that takes the triangle back to its original orientation.
View Source for figure
<figure xml:id="figure-s3">
<caption>Symmetries of an equilateral triangle</caption>
<p>
<me>
\begin{array}{c|cccccc} \circ & id & \rho_1 & \rho_2 & \mu_1 & \mu_2 & \mu_3 \\ \hline id & id & \rho_1 & \rho_2 & \mu_1 & \mu_2 & \mu_3 \\ \rho_1 & \rho_1 & \rho_2 & id & \mu_3 & \mu_1 & \mu_2 \\ \rho_2 & \rho_2 & id & \rho_1 & \mu_2 & \mu_3 & \mu_1 \\ \mu_1 & \mu_1 & \mu_2 & \mu_3 & id & \rho_1& \rho_2\\ \mu_2 & \mu_2 & \mu_3 & \mu_1 & \rho_2 & id & \rho_1\\ \mu_3 & \mu_3 & \mu_1 & \mu_2 & \rho_1 & \rho_2& id \end{array}
</me>
</p>
</figure>
\begin{equation*}
\begin{array}{c|cccccc} \circ & id & \rho_1 & \rho_2 & \mu_1 & \mu_2 & \mu_3 \\ \hline id & id & \rho_1 & \rho_2 & \mu_1 & \mu_2 & \mu_3 \\ \rho_1 & \rho_1 & \rho_2 & id & \mu_3 & \mu_1 & \mu_2 \\ \rho_2 & \rho_2 & id & \rho_1 & \mu_2 & \mu_3 & \mu_1 \\ \mu_1 & \mu_1 & \mu_2 & \mu_3 & id & \rho_1& \rho_2\\ \mu_2 & \mu_2 & \mu_3 & \mu_1 & \rho_2 & id & \rho_1\\ \mu_3 & \mu_3 & \mu_1 & \mu_2 & \rho_1 & \rho_2& id \end{array}
\end{equation*}
