\magnification=\magstep1
\centerline{Mathematics 243, section 3 -- Algebraic Structures}
\centerline{Review Sheet, Final Exam}
\centerline{December 7, 2012}
\bigskip
\noindent
{\it General Information}
\bigskip
The final examination for this course will be given at 
11:30 a.m. on Saturday, December 15 in our regular class room, 
Swords 302.  It will be a comprehensive exam, covering all 
the material we have studied this semester, divided {\it roughly} 
in thirds according to the topics from the three hour exams.
Some questions on earlier material (e.g. the one-to-one and onto
properties of mappings, binary operations, equivalence relations, 
etc.) may appear in the context of topics covered later in the semester, though.
The exam will be roughly twice the length of one of the three
midterms, but you will have the full 2.5 hour period from
11:30 am to 2:00 pm to work on it if you need that much time.
\bigskip
\noindent
{\it Topics to be Covered}
\bigskip
\item{1)}  Sets: set operations (union, intersection, difference, complement,
Cartesian product, etc.) and their properties.
\item{2)}  Mappings: the 1-1 and onto properties, direct and inverse
images of sets under mappings,
\item{3)} Binary operations: identity elements, inverses, properties
such as associativity, commutativity, key examples such as 
function composition, matrix addition and multiplication, 
addition and multiplication in ${\bf Z}$ and ${\bf Z}_n$, etc.  
\item{4)}  Relations:  especially equivalence relations and 
the partition of a set into equivalence classes under an 
equivalence relation (key example:  the congruence mod $n$
relation on ${\bf Z}$ -- the set of equivalence classes
in that case is ${\bf Z}_n$).
\item{5)}  Properties of ${\bf Z}$:  the Well-Ordering
Property, proof by mathematical induction, the division algorithm,
divisibility, prime numbers and prime factorizations,
the gcd and lcm of two integers, Euclid's algorithm for the
gcd, and its use to find integers $p,q$ satisfying $pm + qn = d$
when $d = \gcd(m,n)$ (especially for computing inverses mod $n$)
\item{6)}  The congruence mod $n$ relation on ${\bf Z}$
and the integers modulo $n$,  addition and multiplication
in ${\bf Z}_n$ and their properties.
\item{7)}  Applications to cryptography (affine and RSA cryptosystems). 
\item{8)}  Groups:  the definition, key examples such as
${\bf Z}_n$ under addition mod $n$, matrix groups such as $GL_2({\bf R})$, the permutation group 
${\cal S}(A)$, the group
$${\bf Z}_n^\times = \{[x] \in {\bf Z}_n : [x]^{-1}\ {\rm (multiplicative\ inverse)\ exists}\}
= \{[x] \in {\bf Z}_n : \gcd(x,n) = 1\}$$
under multiplication mod $n$
\item{9)}  Subgroups of groups:  know how to determine whether
a given subset of a group is a subgroup.  Cyclic subgroups.
\item{10)}  Cyclic groups, generators, orders of elements, etc.
\item{11)}  Homomorphisms of groups, kernel and image of a 
homomorphism, isomorphisms.
\vfill
\eject
\noindent
{\it Proofs to Know}
\bigskip
See the review sheets for Exams 1, 2, and 3.  (These
are reposted on the course homepage in case you need
additional copies.)
\bigskip
\noindent
{\it Philosophical Comments and Suggestions on How to Prepare}
\bigskip
\item{$\bullet$}  The reason we give final exams  
in almost all mathematics classes is to encourage students
to ``put whole courses together'' in their minds. 
Preparing for the final should help to 
make the ideas ``stick'' so you will have the material at your 
disposal to use in later courses.  
\item{$\bullet$}  You probably have noticed how things 
that seemed hard earlier in the semester seem easier now.  That
is because you have been using those concepts repeatedly and
deepening your understanding with each ``pass.''  The same thing
should happen now with the course as a whole, if you have been
approaching the problem sets, the definitions quizzes, and the 
hour exams in the right way.  
\item{$\bullet$}  It may not be necessary to say this, but
here goes anyway:  {\it You should take this exam seriously} -- 
it is worth $25\%$ of your course average and it can 
pull your course grade up {\it or down} depending on how you do.  
\item{$\bullet$}  Especially because our exam is so late in the
exam week, you should get started reviewing early
and do some work on this {\it every day} between now 
and the date of the final.  Don't try to ``cram'' at the end.  
There's too much stuff that you need to know to approach 
preparing that way!
\item{$\bullet$}  Reread your class notes in addition to the
text, especially for topics where you lost points on the midterms.  
There are a lot of worked-out examples and discussions of all of 
the topics we have covered there.
\item{$\bullet$}  
Look over the midterm exams with the solutions. Go over your corrected problem sets.
If there were questions where you lost a lot 
of points, be sure you understand why what you did was not
correct, and how to solve those questions. 
\item{$\bullet$}  Be sure you actually do 
enough practice problems so that you have the 
facility to solve exam-type questions in a limited
amount of time.   {\it Even if you 
have saved solutions for practice problems from the midterms},
it is going to be much more beneficial to do practice problems
starting ``from scratch'' rather than just reading old
solutions.  Remember, the goal of the course is to get
you to be able to develop solutions to these problems
yourselves, not just to understand solutions that someone
else has written down.  
Another analogy -- as most of you know from your study
of languages, it's much easier to understand 
another language passively than it is to actually 
use a language actively yourself (for instance, to form your
own complete, grammatically correct sentences).  
The goal of this course is to make you reasonably
proficient ``algebra speakers'' and there's no substitute
for active practice on those skills.
\bigskip
\noindent
{\it Review Session}
\bigskip
I will be happy to run a review session for the final
exam during study week.  We can discuss a time in class
on Friday, December 7.
\bigskip
\noindent
{\it Some Sample Exam Questions}
\bigskip
\noindent
I.    
\bigskip
\item{A)} Let $A = {\bf Z}$, the set of all integers.
Consider $\varphi : A \to A$ be the mapping defined
by 
$$\varphi(x) = \cases{5x & if $x$ is even\cr
                      x - 2 & if $x$ is odd\cr}$$
Is $\varphi$ one-to-one?  Why or why not?
Is $\varphi$ onto?  Why or why not?
\item{B)}  What is $\varphi^{-1}(\{3,4,5,6,7\})$ for
the mapping in part A?
\item{C)}  What is $\varphi(\{1,2,3\} \cap \{x\in A : x^2 < 5\})$?
\bigskip
\noindent
II.
\item{A)}  Give the precise statement and the proof of the Division 
Algorithm in ${\bf Z}$.
\item{B)}  Find the integer $d = \gcd(753,154)$ and express 
$d$ in the form $d = 753m + 154n$ for some integers $m,n$.
\item{C)}  Show that if $a,b,c$ are integers, $a | (b\cdot c)$ and 
$\gcd(a,c) = 1$, then $a|b$.  
\bigskip
\noindent
III.  Let $f_0 = 0, f_1 = 1$, and $f_n = f_{n-1} + f_{n-2}$ for 
all $n \ge 2$.  The $f_n$ are called the {\it Fibonacci numbers}; the 
first few of them are $1,1,2,3,5,8,13,21,34, \ldots$.
\item{A)}  Let $A = \pmatrix{1&1\cr 1&0\cr}$.  Compute the 
matrix powers $A^2,A^3,A^4$.  Do you see a pattern developing?
\item{B)}  (The pattern!)  Show by mathematical induction:
$$\pmatrix{1&1\cr 1&0\cr}^n = \pmatrix{f_{n+1}&f_n\cr f_n& f_{n-1}}$$
for all $n \ge 1$.
\bigskip
\noindent
IV.  
\item{A)}  In an affine cipher on a 26-letter alphabet, 
``E'' (the most common letter) is encrypted to ``Z'' and ``T''
(the next most common letter) is encrypted to ``B''.  What
are the encryption and decryption functions?  
\item{B)} In an RSA public key cryptosystem, the public key consists of
the integer $m = 143$ and the encryption exponent $e = 29$.
What is the decryption exponent $d$?  
\bigskip
\noindent
V.  Consider the following set of all $2\times 2$ matrices with real entries:
$$G = 
\left\{\pmatrix{a&b\cr 0&d\cr}\ |\ a,b,d \in {\bf R}\right\}.$$ 
\item{A)} Show that $G$ is a group under matrix {\it addition\/}.
\item{B)} Is the set 
$$H = \left\{ \pmatrix{1&n\cr 0&1\cr}\ |\ n \in {\bf Z}\right\}$$
a subgroup of the group from part A?  Why or why not?
\bigskip
\noindent
VI. All parts of this question refer to  ${\bf Z}_{30}$,
in which the operations are addition and multiplication mod 30.
\item{A)}  Which elements of ${\bf Z}_{30}$ have {\it multiplicative}
inverses in ${\bf Z}_{30}$?
\item{B)}  Find all the elements of the additive group 
$({\bf Z}_{30},+)$ that generate the additive subgroup
$\langle [24]\rangle$.
\bigskip
\noindent
VII.  Let $G$ and $H$ be groups and let 
$\varphi : G \to H$ be a group homomorphism.
\item{A)}  Give the precise definition of the {\it kernel\/} of $\varphi$,
$\ker(\varphi)$.
\item{B)}  Show that if $K = \ker(\varphi)$ and $g \in G$
is an arbitrary fixed element, then $gKg^{-1} = \{gkg^{-1}\ |\ k \in K\}$
is equal to $K$.
\item{C)}   Show that the relation $R$ on $G$
defined by 
$$x R y \Leftrightarrow xy^{-1} \in \ker(\varphi)$$
is an {\it equivalence relation} on $G$.  

\bye

