\magnification=\magstep1
\centerline{Mathematics 243 -- Algebraic Structures}
\centerline{Solutions for Review Problems for Final Exam}
\centerline{December 8, 2006}
\bigskip
\noindent
I.  A)  $\varphi$ {\it is} one-to-one.  If $x$ and $x'$ are
two even numbers, then $\varphi(x) = \varphi(x')$ implies $5x = 5x'$, which implies
$x = x'$ (since $5(x - x') = 0$ implies $x - x' = 0$).  
Similarly if $x$ and $x'$ are both odd, then $\varphi(x) = \varphi(x')$
implies $x - 2 = x' - 2$.  Adding 2 to both sides, $x = x'$.  Finally
if $x$ is even and $x'$ is odd, then $\varphi(x)$ is even and $\varphi(x')$ is
odd, so $\varphi(x) \ne \varphi(x')$.  

$\varphi$ is not onto, since for instance $\varphi(x) \ne 2$ for all $x \in {\bf Z}$.

\bigskip
\noindent
B) 
$$\varphi^{-1}(\{3,4,5,6,7\}) = \{x \in {\bf Z} : \varphi(x) \in \{3,4,5,6,7\}\}
= \{5,7,9\}$$
(There are no integers mapping to the even numbers $4,6$ here.)

\bigskip
\noindent
C)  
$$\varphi(\{1,2,3\} \cap \{x \in A : x^2 < 5\}) = \varphi(\{1,2\}) = \{-1,10\}$$

\bigskip
\noindent
II.  A)  See class notes or the text.
\bigskip
\noindent
B)  Applying the Euclidean Algorithm we have
$$\eqalign{753 &= 4\cdot 154 + 137\cr
           154 &= 1\cdot 137 + 17\cr
           137 &= 8\cdot 17 + 1\cr}$$
So $\gcd(753,154) = 1$.  Then 
$$\matrix{ &1 & 0\cr 
            &0 & 1\cr
           4&1 &-4\cr
           1&-1& 5\cr
           8&9 &-44\cr}$$
So $1 = 9\cdot 753 + (-44)\cdot 137$.
\bigskip
\noindent
C)  From the hypothesis that $\gcd(a,c) = 1$ we have $1 = ra + sc$ for
some integers $r,s$.  Multiplying both sides of this equation by $b$ we
obtain $b = rab + sbc$.  Since we know also $a|(bc)$, $bc = qa$ for some
integer $q$.  Hence $b = rab + sbc = a(rb + sq)$, which shows $a|b$.
\bigskip
\noindent
III. A)
$$A^2 = \pmatrix{2 & 1 \cr 1& 1\cr},\quad A^3 := \pmatrix{3&2\cr 2&1\cr}, \quad A^4=\pmatrix{5&3\cr 3&2\cr}$$
\bigskip
\noindent
B) Note that $f_0 = 0, f_1 = 1, f_2 = 1, f_3 = 2$. etc.
 The base case for the induction is $n = 1$, and 
$$A^1 = A = \pmatrix{1 & 1\cr 1 & 0\cr} = \pmatrix{f_2 & f_1 \cr f_1 & f_0\cr}$$
as claimed.  Now assume that the statement is true for $n = k$:
$$A^k = \pmatrix{f_{k+1} & f_k \cr f_k & f_{k-1}}.$$
Then 
$$A^{k+1} = A^k \cdot A = \pmatrix{f_{k+1} & f_k \cr f_k & f_{k-1}}\pmatrix{1 & 1\cr 1 & 0\cr}$$
By the definition of matrix multiplication this is
$$A^{k+1} = \pmatrix{f_{k+1} + f_k & f_{k+1}\cr f_k + f_{k-1} & f_k\cr}$$
Using the recurrence for the Fibonacci numbers, this gives
$$A^{k+1} = \pmatrix{f_{k+2} & f_{k+1} \cr f_{k+1} & f_k\cr}$$
which is what we wanted to show.
\bigskip
\noindent
IV.  A) 
 We want to assume that $A$ is represented by $[0]$, $B$ by $[1]$, etc. through 
$Z$ by $[25]$, all mod 26.  The encryption function for an affine cipher has the 
form $f([x]) = [a][x] + [b]$  so from $f([4]) = [25]$ and $f([19]) = [1]$,
$$[a][4] + [b] = [25] \quad  {\rm and}  [a][19] + [b] = [1].$$ 
Hence subtracting,
$[15][a] = [-24] = [2]$.  $[15]$ has a multplicative inverse in ${\bf Z}_{26}$
since $\gcd(26,15) = 1$, and  $[15]^{-1} = [7]$, since $7\cdot 15 = 105 \equiv 1 \bmod 26$.
Therefore $[a] = [7][2] = [14]$ and $[b] = [25] - [56] = [25] - [4] = [21]$ in 
${\bf Z}_{26}$.    Therefore 
$$f([x]) = [14][x] + [21].$$
This is actually a sort of trick question because it turns out that 
this mapping {\it does not have an inverse function}(!)  It would not be suitable
for use as an affine cipher.  The reason is that $[14]$ {\it does not} have
an inverse in ${\bf Z}_{26}$, so this mapping is not one-to-one.
Note that $f([x]) = f([x + 13])$  since $[14 x] = [14 x + 26]$.   
\bigskip
\noindent
B)  The integer $m = 323 = 17\cdot 19$.  So we want $ed = 29d \equiv 1\bmod (17-1)(19-1) = 288$.
This implies $d = 149$ (by calculations like the ones in II A above).
\bigskip
\noindent
V.  A)  $G$ is closed under matrix sums since 
$$\pmatrix{a & b \cr 0 & d\cr} + \pmatrix{a' & b' \cr 0 & d'\cr} = \pmatrix{a+a' & b+b' \cr 0 &d+d'\cr}$$
which is also in $G$.  Matrix addition in $G$ is associative because addition
in ${\bf R}$ is associative:
$$\eqalign{
&\left( \pmatrix{a & b \cr 0 & d\cr} + \pmatrix{a' & b' \cr 0 & d'\cr} \right) + \pmatrix{a'' & b'' \cr 0 &d''\cr} \cr
&= \pmatrix{(a+a') + a'' & (b + b') + b''\cr 0 & (d + d') + d''\cr}\cr
&= \pmatrix{a+(a' + a'') & b + (b' + b'')\cr 0 & d + (d' + d'')\cr}\cr
&=\pmatrix{a & b \cr 0 & d\cr} + \left(\pmatrix{a' & b' \cr 0 & d'\cr} + \pmatrix{a'' & b'' \cr 0 &d''\cr}\right) \cr}.$$
The matrix $Z = \pmatrix{0 & 0 \cr 0 & 0\cr}$ is in $G$ (take $a = b = d = 0$) and 
is an identity element for matrix addition.  Finally, for each 
$A = \pmatrix{a & b \cr 0 & d\cr} \in G$, $-A = \pmatrix{-a & -b \cr 0 & -d\cr} \in G$
too and satisfies $A + (-A) = Z$ (as above).  Therefore $G$ is a group under 
matrix sums.
\bigskip
\noindent
B)  No.  The set $H$ is not closed under matrix {\it sums}.  For instance
$$\pmatrix{1 & 1 \cr 0 & 1\cr} + \pmatrix{1 & 2 \cr 0 & 1\cr} = \pmatrix{2 & 3 \cr 0 &2\cr}$$
which is not in $H$ (because of the 2's on the main diagonal).

\bigskip
\noindent
VI.  A) The elements that have multiplicative inverses in ${\bf Z}_{30}$ are
the $[x]$ with $\gcd(x,30) = 1$:
$$[1],[7],[11],[13],[17],[19],[23],[29]$$
\bigskip
\noindent
B)  The elements that generate the additive subgroup $\langle [24]\rangle$
are the classes $[x]$ such that $\gcd(30,x) = \gcd(30,24) = 6$.  This gives
$$[6],[12],[18],[24].$$\bigskip
\noindent
VII.  A)  $\ker(\varphi) = \{x \in G : \varphi(x) = e_H\}$.
\bigskip
\noindent
B)  First, if $k \in K = \ker(\varphi)$, then 
by properties we know for group homomorphisms,
$$\varphi(gkg^{-1}) = \varphi(g)\varphi(k)\varphi(g^{-1}) = \varphi(g) e_H (\varphi(g))^{-1} = e_H$$
Therefore $gkg^{-1} \in K$, so $gKg^{-1} \subseteq K$.  To get the other inclusion,
note that if $k \in K$, then $k = g\left(g^{-1}k g\right) g^{-1}$.
By an argument exactly like the other direction, we see that 
$g^{-1}k g\in K$ if $k \in K$.  Therefore $k \in gKg^{-1}$ and 
$K \subseteq gKg^{-1}$.  Hence $K = gKg^{-1}$.
\bigskip
\noindent
C)  The relation $R$ is reflexive since for all $x \in G$, $xx^{-1} = e_G \in \ker(\varphi)$.
The relation $R$ is symmetric since if $xRy$, then $xy^{-1} \in \ker(\varphi)$.
But $\ker(\varphi)$ is a subgroup of $G$, so it closed under inverses.
$(xy^{-1})^{-1} = yx^{-1}$ (reverse order rule for inverses).  Hence $yRx$ follows.  
Finally, the relation $R$ is transitive since if $xRy$ and $yRz$ then
$xy^{-1}, yz^{-1} \in \ker(\varphi)$.  $\ker(\varphi)$ is a subgroup
of $G$ so it is closed under products:
$$(xy^{-1})(yz^{-1}) = x(y^{-}y)z^{-1} = xz^{-1}$$
Hence $xRz$ and $R$ is transitive.
\bye
