\magnification=\magstep1
\overfullrule=0pt
\def\Sol{\bigskip \item{} {\it Solution} : }
\centerline{Mathematics 243, section 1 -- Algebraic Structures}
\centerline{Final Examination -- December 13, 2006}

\bigskip
\noindent
I. 
Let $\varphi, \psi : {\bf Z} \to {\bf Z}$ be the mappings defined
$$\eqalign{\varphi(x) &= \cases{3x & if $x$ is odd\cr 1 & if $x$ is even\cr}\cr
           \psi(x) &= \cases{x + 1 & if $x$ is odd\cr
                             x - 1 & if $x$ is even\cr}\cr}$$ 
\bigskip
\item{A)} (10) Is $\psi$ a permutation of ${\bf Z}$?  Prove your assertion.
\bigskip
\Sol
Yes $\psi$ is a permutation, or one-to-one (injective) and onto (surjective)
mapping from ${\bf Z}$
to itself.  Suppose that $\psi(x) = \psi(x')$.  Then $x$ and $x'$ must
be either both even or both odd, since $\psi$ maps odd integers to even
integers, and even integers to odd integers.  If $x,x'$ are both 
even, then $x - 1 = x' - 1$.  Adding $1$ to both sides yields $x = x'$.
Similarly, if $x,x'$ are both odd, then $x + 1 = x' + 1$.  Subtracting $1$
from both sides shows $x = x'$ in this case too.  Hence $\psi$ is injective.
$\psi$ is also surjective since if $y$ is even, then $y = \psi(x)$ for the
odd number $x = y - 1$.  Moreover if $y$ is odd, then $y = \psi(x)$ for 
the even number $x = y + 1$.  
\bigskip
\item{B)} (10) What is the mapping $\varphi \circ \psi$?  
\Sol
$$(\varphi \circ \psi)(x) = \cases{1 & if $x$ is odd\cr
                                   3x - 3 & if $x$ is even\cr}$$
\bigskip
\noindent
II.  Let $A = \{1,2\}$ and let ${\cal P} = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}$
(the collection of all subsets of $A$).  Let $+$ be the binary operation on
${\cal P}$ defined by $C + D = (C \cup D) - (C\cap D)$.  For instance,
$\{1\} + \{1,2\} = \{1,2\} - \{1\} = \{2\}$.  
\bigskip
\item{A)}  (15) Compute the rest of the operation table for $+$ on
${\cal P}$.
\Sol
The complete operation table looks like this:
$$\matrix{       +  & \emptyset & \{1\} & \{2\} & \{1,2\}\cr
          \emptyset & \emptyset & \{1\} & \{2\} & \{1,2\}\cr
             \{1\}  &  \{1\}    & \emptyset & \{1,2\} & \{2\} \cr
             \{2\}  &  \{2\}    & \{1,2\} & \emptyset & \{1\} \cr
            \{1,2\} &  \{1,2\}  &  \{2\} & \{1\} & \emptyset\cr}$$
\bigskip
\item{B)}  (5)  Is there an identity element for $+$ in ${\cal P}$.  If so,
what is the identity element?
\Sol
Yes.  $E = \emptyset$ acts as an identity element here.  (Note:  In 
fact from the table above, we can see that ${\cal P}$ is even
a {\it group} of order 4 under this operation!)
\bigskip
\noindent
III.  (10)  Prove by contradiction: if $A = \{a_1, \ldots, a_n\}$ 
is a {\it finite\/} set and $\varphi : A \to A$ is surjective then 
$\varphi$ is also injective.
\Sol
Suppose $\varphi$ is not injective.  Then there are two distinct elements of
$A$, say $a_i$ and $a_j$ that satisfy $\varphi(a_i) = \varphi(a_j)$.
But then there can be at most $n - 1$ distinct elements in the
image of $\varphi$, so that $\varphi$ is not onto.  This contradiction
shows that $\varphi$ must be surjective.
\bigskip
\noindent
IV.
\item{A)}  (5) Let $a,b$ be two integers, at least one of which is nonzero.
Give the definition of a gcd of $a,b$. 
\Sol
$d$ is a gcd of $a,b$ if $d > 0$, $d|a$ and $d|b$, and if 
$c|a$ and $c|b$, then $c|d$.  
\bigskip
\item{B)} (15)  Find the integer $d = \gcd(537,411)$ and express 
$d$ in the form $d = 537r + 411s$ for some integers $r,s$.
\Sol
Applying the Euclidean algorithm:
$$\eqalign{537 &= 1\cdot 411 + 126\cr
           411 &= 3\cdot 126 + 33\cr
           126 &= 3\cdot 33 + 27\cr
            33 &= 1\cdot 27 + 6\cr
            27 &= 4\cdot 6 + 3\cr
            6  &= 2\cdot 3 + 0\cr}$$
Hence $\gcd(537,411) = 3$.  To find the integers $r,s$:
$$\matrix{ & 1 & 0\cr
           & 0 & 1\cr
          1& 1 & -1\cr
          3& -3& 4\cr
          3&10 &-13\cr
          1&-13 & 17\cr
          4& 62 & -81\cr}$$
This shows $62\cdot 537 + (-81)\cdot 411 = 3$.
\bigskip
\item{C)}  (15)  Assume that $a,b,c$ are integers, 
$d = \gcd(a,b)$, $a|c$ and $b|c$.  Prove that $ab|cd$. 
\Sol
Since $d = \gcd(a,b)$, as in part C, there are integers
$r,s$ such that $d = ar + bs$, hence $cd = car + cbs$.
Since $a|c$, there is an integer $q$ such that $c = qa$, and
similarly there is an integer $p$ such that $c = pb$.
Substitute as follows:
$$\eqalign{cd &= car + cbs\cr
              &= (pb)ar + qa(bs)\cr
              &= ab(pr + qs)\cr}$$
Since $p,r,s,q$ are all integers, so is $pr + qs$, and this
shows $ab|cd$.  
\bigskip 
\item{D)}  (20) An RSA public key cryptographic system has $m = 209$ and encryption
exponent $e = 37$.  What is the corresponding decryption exponent $d$?
\Sol
Since $209 = 19\cdot 11$, we want to find $d$ such that 
$37 d \equiv 1 \bmod (19-1)(11-1) = 180$.  Since $\gcd(37,180) = 1$,
such a $d$ exists and we can find it by the same process as in part B:
$$\eqalign{180 &= 4\cdot 37 + 32\cr
            37 &= 1\cdot 32 + 5\cr
            32 &= 6\cdot 5 + 2\cr
             5 &= 2\cdot 2 + 1\cr}$$
Then 
$$\matrix{ & 1 & 0\cr
           & 0 & 1\cr
          4& 1 & -4\cr
          1& -1& 5\cr
          6& 7 & -34\cr
          2& -15& 73\cr}$$
Hence $(-15)\cdot 180 + 73 \cdot 37 = 1$.  This says $d = 73$.  
\bigskip
\noindent
V.  (20) Prove by mathematical induction:  for all real numbers $a,b$ and all $n \ge 1$:
$$\pmatrix{a & b \cr 0 & a}^n = \pmatrix{a^n & na^{n-1} b \cr 0 & a^n}.$$
\Sol
The statement is clear in the base case $n = 1$.  So assume
that 
$$\pmatrix{a & b \cr 0 & a}^k = \pmatrix{a^k & ka^{k-1} b \cr 0 & a^k}.$$
Then 
$$\eqalign{
\pmatrix{a & b \cr 0 & a}^{k+1} &= \pmatrix{a^k & ka^{k-1} b \cr 0 & a^k\cr}\pmatrix{a&b\cr 0&a\cr}\cr
&=\pmatrix{a^{k+1} & a^k\cdot b + ka^{k-1}b\cdot a\cr 0 & a^{k+1}\cr}\cr
&=\pmatrix{a^{k+1} & (k+1)a^k b \cr 0 & a^{k+1}\cr} \cr }$$
which is what we wanted to show.
\bigskip
\noindent
VI. (20) Consider the set of all $2\times 2$ matrices with real entries:
$$M_{2\times 2}({\bf R}) = 
\left\{\pmatrix{a&b\cr c&d\cr} : a,b,c,d \in {\bf R}\right\}.$$ 
Show that $M_{2\times 2}({\bf R})$ is a group under matrix 
{\it addition\/}:
$$\pmatrix{a&b\cr c&d\cr} + \pmatrix{e&f\cr g&h\cr} = 
\pmatrix{a+e&b+f\cr c+g&d+h\cr}.$$
\Sol
$G$ is closed under sums since from the above, if $a,b,c,d,e,f,g,h$
in ${\bf R}$, then the sum matrix is also an element of $M_{2\times 2}({\bf R})$.
Matrix sums are associative since if $A = (a_{ij}), B = (b_{ij})$ and
$C = (c_{ij})$, then the entry in row $i$ and column $j$ in the sum 
$(A + B) + C$ is $(a_{ij} + b_{ij}) + c_{ij} = a_{ij} + (b_{ij} + c_{ij})$,
using the associativity of $+$ in ${\bf R}$.  Hence $(A + B) + C = A + (B + C)$.
The zero matrix $Z = \pmatrix{0 & 0\cr 0 & 0\cr}$ is an identity element
for matrix sums.  Finally if $A = \pmatrix{a & b \cr c & d\cr}$ is in $G$,
then the additive inverse of $A$ is $-A = \pmatrix{-a & -b \cr -c & -d}$.
\bigskip
\noindent
VII.  All parts of this question refer to the group $G = {\bf Z}_{27}$,
in which the operation is addition mod 27.
\bigskip
\item{A)} (5) Find all generators for $G$.
\Sol 
The generators are the classes $[x]$ with $\gcd(x,27) = 1$, so 
$$[x] = [1],[2],[4],[5],[7],[8],[10],[11],[13],[14],[16],[17],[19],[20],[22],[23],[25],[26]$$
\bigskip
\item{B)} (5) Find the elements of the cyclic subgroup $\langle [21] \rangle$
in $G$.  
\Sol
By our general theorems on subgroups of cyclic groups, 
this is the same subgroup as $\langle [3]\rangle$
since $\gcd(21,27) = 3$.  Hence
$$
\langle [21] \rangle = \{[0],[3],[6],[9],[12],[15],[18],[21],[24]\}$$
\bigskip
\item{C)} (5) Find all elements of $G$ of order $9$.
\Sol
These are the same as the generators of $\langle [3]\rangle = \langle [21]\rangle$
from part B:
$$[3],[6],[12],[15],[21],[24].$$
\bigskip
\noindent
VIII.  Let $G$ and $H$ be groups with identity elements
$e_G$ and $e_{H}$ respectively, and let 
$\varphi : G \to H$ be a group homomorphism.
\bigskip
\item{A)} (15)  Show that $\ker(\varphi)$ is a subgroup of $G$.
\Sol
Write $K$ for $\ker(\varphi)$.  $K \ne \emptyset$ because we know
$\varphi(e_G) = e_H$, so $e_G \in K$.  If $x,y\in K$, then since $\varphi$
is a group homomorphism
$\varphi(xy) = \varphi(x) \varphi(y) = e_H e_H = e_H$.
Hence $xy \in K$ so $K$ is closed under products.  
Finally, let $x \in K$ and recall that since $\varphi$ is a group 
homomorphism
$\varphi(x^{-1}) = (\varphi(x))^{-1}$ for all $x \in G$.  If
$x \in K$, then this says $\varphi(x^{-1}) = (e_H)^{-1} = e_H$.
Hence $K$ is closed under inverses too, and $K$ is a subgroup of $G$.
\bigskip
\item{B)} (5)  Let $c\in H$, and let $a,b\in \varphi^{-1}(\{c\})$, 
(the inverse image under the mapping $\varphi$). Prove that $ab^{-1} \in \ker(\varphi)$.
\Sol
From the given information, $\varphi(a) = \varphi(b) = c$. 
Hence by the group homomorphism properties.
$$\varphi(ab^{-1}) = \varphi(a)\varphi(b^{-1}) = \varphi(a) (\varphi(b))^{-1} = cc^{-1} = e_H$$
Hence by definition, $ab^{-1}\in K = \ker(\varphi)$.
\bigskip
\item{C)}  (5)  Prove that $\varphi$ is injective if and only if
$\ker(\varphi) = \{e_G\}$.
\Sol
If $\varphi$ is injective, there is only one element that maps to $e_H$, namely
$e_G$.  Hence $K = \ker(\varphi) = \{e_G\}$ (and nothing else).  Conversely,
if $K = \ker(\varphi) = \{e_G\}$ and $\varphi(a) = \varphi(b)$
for $a,b\in G$, then reasoning as in part B, but ``working backwards'' 
$$e_H = \varphi(a) (\varphi(b))^{-1} = \varphi(ab^{-1})$$
Hence $ab^{-1} \in K = \{e_G\}$.  This implies $ab^{-1} = e_G$ so $a = b$.
It follows that $\varphi$ is injective.
\bigskip
\noindent
IX.  (10) Let $G$ be a group, and let $x,y \in G$.  The conjugacy relation
$R$ on $G$ is defined as follows.  We say $x$ and $y$
are {\it conjugate} in $G$, $xRy$, if there exists an $a \in G$ such
that $y = axa^{-1}$.  Show that the conjugacy relation is an equivalence
relation on $G$. 
\Sol
$R$ is reflexive: We have $x = exe^{-1}$, so $xRx$ for all $x \in G$ (take $a = e$
in the definition).
\medskip
\item{}$R$ is symmetric:  If $xRy$, then $y = axa^{-1}$ for some $a\in G$. But
then $x = a^{-1}ya = byb^{-1}$ if we write $b = a^{-1}$.  Hence $yRx$.
\medskip
\item{} $R$ is transitive:  If $xRy$ and $yRz$, then $y = axa^{-1}$ and $z = byb^{-1}$
for some $a,b\in G$ (not necessarily the same).  Then if we substitute for $y$ in 
the second equation,
$$z = b(axa^{-1})b^{-1} = (ba)x(a^{-1}b^{-1}) = (ba)x(ba)^{-1}$$
(reverse order law for inverses).  This shows $yRz$.    

\bye
