\magnification=\magstep1
\centerline{Mathematics 243, section 1 -- Algebraic Structures}
\centerline{Information on Exam 3}
\centerline{November 17, 2006}
\bigskip
\noindent
{\it General Information}
\bigskip
The third exam this semester will be
given the Friday after Thanksgiving, December 1.  The exam will cover the
material we have discussed since the second exam, through
the material on isomorphisms and homomorphisms of groups from
class on Monday, November 20.  The relevant sections 
in Gilbert and Gilbert are 2.8, 3.1, 3.2, 3.3, 3.4, and 3.5.  
The topics to review are:
\bigskip
\item{1)}  Applications to cryptography (affine and RSA encryption
and decryption).  I won't ask you to encrypt or decrypt long messages
like the ones from Problem Set 8 with either type of system, but you 
should be prepared to carry out encryption or decryption
of one or two characters with just a calculator.
\item{2)}  The definition of a group; how to determine if a given 
set with a given binary operation has the structure of a group; key 
examples such as ${\bf Z}_m, +$, the group of invertible
classes in ${\bf Z}_m$ under multiplication:  ${\bf Z}_m^\times, \cdot$, 
the group of invertible $2\times 2$ matrices, $GL(2,{\bf R})$
under the matrix product, groups of permutations, 
etc., what it means for a group to be abelian,
which of the key examples are abelian and which are not.  
\item{3)}  Subgroups, the general subgroup criterion from Theorem 3.9,
cyclic subgroups.
\item{4)}  Cyclic groups, generators, orders of elements, the 
distinct subgroups of a cyclic group of order $n$.
\item{5)}  Isomorphisms of groups and group homomorphisms, the kernel, 
other properties.  {\it Note: we do not have time to ``squeeze in''
a problem set on this material before the exam, so it will be 
especially important to try at least a good sample of the review questions
below from sections 3.4 and 3.5.}
\bigskip
\noindent
{\it Proofs to Know}
\bigskip
\item{1)}  Know how to prove Theorem 3.9 and how to apply it to 
show that subsets of groups are or are not subgroups, both in 
explicit examples and in cases where the subset is defined by 
a condition such as we saw in the problems about the center of a group,
$K = \{x \in G : x = aha^{-1} for some h \in H\}$, the kernel of a homomorphism, etc.
\item{2)}  Let $G = \langle a\rangle$ be a cyclic group.  Then
\itemitem{a)}  Every subgroup $H$ of $G$ is cyclic.
\itemitem{b)}  If $G$ is finite cyclic of order $n$ and 
$H = \langle a^k\rangle$, then $H = \langle a^d \rangle$ where $d = \gcd(n,k)$.
\item{3)}  If $\varphi : G \to H$ is a group homomorphism, then
$\varphi(e_G) = e_H$, and for all $x\in G$, 
$\varphi(x^{-1}) = (\varphi(x))^{-1}$.
\item{4)}  The kernel of a group homomorphism 
$\varphi : G \to G'$ is a subgroup of $G$.
\vfill\eject
\noindent
{\it Some Review Problems}
\bigskip
\noindent
From Gilbert and Gilbert:
\bigskip
\item{1)} Section 2.8: 9, 11, 19, 21 (see note 1 under General Information above)
\item{2)} Section 3.1: problems like 1-33, 48, 49.
\item{3)} Section 3.2: 7, 8, 9, 10, 11, 19, 30, 32 (take $m$ fixed and argue
by induction on $n$), 33 (induction on $n$)
\item{4)} Section 3.3: 1, 7, 10, 11, 16, 17, 18, 19
\item{5)} Section 3.4: 1, 2, 3, 7 
\item{6)} Section 3.5: 1, 2, 3, 5, 13, 14
\bigskip
\noindent
{\it Review Session}
\bigskip
I have off-campus commitments in Boston on the evenings of Tuesday and Wednesday,
November 28 and 29.  I will need to leave campus
at 5:00 pm at the latest each of those days. Thus, if we are going to do 
an evening review session this time, it has to be Monday, November 27 or 
Thursday, November 30.
I am happy to do a session either evening.  I expect Thursday
will be more popular.  That's OK, but be aware that the better 
prepared you are that evening, the more valuable the session will be.
{\it A word to the wise: Do not put off studying for this exam until 
the review session!}
\bigskip
\noindent
{\it Sample Exam Questions}
\bigskip
\noindent
I.  An RSA public-key cryptographic system has $m = 143$ and
the encryption exponent $e = 17$.  
\item{A)} What is the corresponding decryption exponent $d$?
\item{B)} If you use a 26-letter alphabet, represented
by the numbers $0,1,\ldots,25$, and 3-digit blocks
to represent the encrypted symbols, what would be the 
encrypted form of the plaintext: HC?
\item{{\it Note:}} Be prepared for questions about affine ciphers
as well -- see review problems above!
\bigskip
\noindent
II.  Let ${\bf Q}$ be the set of rational numbers:
${\bf Q} = \{m/n : m,n \in {\bf Z}, n \ne 0\}$.
Define a binary operation $*$ on ${\bf Q} - \{-1\}$ by
$x * y = x + y + x\cdot y$
(where $\cdot$ is ordinary multiplication).  
Is ${\bf Q}$ a group under $*$?  Why or why not?
\bigskip
\noindent
III.  
\item{A)}  Find all generators of the group $G = {\bf Z}_{21}$,
in which the operation is addition mod 21.  
\item{B)}  What are the possible orders of elements of 
the group $G$ from part A? 
\bigskip
\noindent
IV.  Let $G = \langle a\rangle$ be a cyclic group.
\item{A)}  Show that every subgroup $H \subset G$ is cyclic.
\item{B)}  Show that if $G$ is finite, with $|G| = n$, then
$\langle a^k\rangle = \langle a^d\rangle$ where $d = \gcd(n,k)$.
\bigskip
\noindent
V.  Let $G = {\bf Z}_{12}$ and $H = {\bf Z}_9$, which are both
groups under addition.  We write $[x]_{12}$ for the congruence class
of $x$ mod 12, and similarly $[x]_9$ for the class mod 9.  Define 
$\phi : G \to H$ by $\phi([x]_{12}) = [3x]_9$.
\item{A)} Show that $[x]_{12} = [y]_{12}$ implies
$[3x]_9 = [3y]_9$ (so that this mapping actually makes sense).
\item{B)} Show that $\phi$ is a {\it group homomorphism\/}.
\item{C)} Find all the elements of $\ker(\phi)$.
\bigskip
\noindent
VI.  Let $G$ be a group and let $a \in G$ be a fixed element.  Define
$$C(a) = \{x \in G : ax = xa\}$$
\item{A)} Is $b = \pmatrix{1&2\cr 3&4\cr}$ in $C(a)$ for
$a = \pmatrix{1&1\cr 0&1\cr}$ in $G = GL(2,{\bf R})$ (a group under
matrix multiplication)?  Why or why not?
\item{B)} Show that $C(a)$ is a subgroup of $G$.   
\bye
