\magnification=\magstep1
\centerline{Mathematics 243--Algebraic Structures}
\centerline{Selected Solutions -- Problem Set 8}
\centerline{November 13, 2006}
\bigskip
\noindent
2.8/22.  Since it is given that $m = 51$, we need to factor:
$51 = 3\cdot 17$, so we take $p = 3$ and $q = 17$.  This means
that the decoding exponent $d$ will satisfy 
$$de \equiv 1 \bmod (p-1)(q-1),\ {\rm so}\ 5d \equiv 1\bmod 32$$
This says $[d]$ should be the multiplicative inverse of $[5]$ in 
${\bf Z}_{32}$.  We see $d = 13$, since $5\cdot 13 = 65 \equiv 1 \bmod 32$.
(This can also be derived by carrying out the Euclidean algorithm
to find $\gcd(5,32) = 1$, of course.)

To decode the given message, we must apply the decoding function 
$$g(x) = x^{13} \bmod 51$$
to each two-digit block in the ciphertext.  This can be done without
too much trouble by the technique of {\it repeated squaring}.
For instance, the third block is $x = 32$:
$$\eqalign{
x &\equiv 32 \bmod 51\cr
x^2 &\equiv 32^2 = 1024 \equiv 4 \bmod 51\cr
x^4 &\equiv 4^2 = 16 \bmod 51\cr
x^8 &\equiv 16^2 = 256 \equiv 1\bmod 51\cr
{\rm so}\ x^{13} &= x^8\cdot x^4\cdot x \equiv 1\cdot 16\cdot 32 = 512 \equiv 2 \bmod 51\cr}$$
This means that 
$$g(32) = 32^{13} \equiv 2 \bmod 51$$
and the third block decodes to the letter `C'.  Carrying out the same process
on each 2-digit block gives the decoded message `EUCLIDEAN ALGORITHM'.
\bigskip
\noindent
3.1/5.  Let $S = \{x \in {\bf R} : 0 < x \le 1\}$ with the operation
of multiplication.  This set is closed under products since $0 < x \le 1$
and $0 < y \le 1$ implies $0< xy \le 1$.  Multiplication in ${\bf R}$ is 
associative in general, so that property also holds for products of
elements of $S$.  The multiplicative identity $1$ in ${\bf R}$ is in $S$,
so $S$ has a multiplicative identity.  But note that if $x \in S$ then 
the multiplicative inverse $1/x$ need not be in $S$.  For instance, 
if $x = 1/3$, then $x^{-1} = 3 \notin S$.  We conclude that $S$ is not
a group under multiplication.
\bigskip
\noindent
3.1/24.  We have the following operation table for multiplication 
modulo 10 on the set $S = \{[0],[2],[4],[6],[8]\} \subset {\bf Z}_{10}$:
$$\matrix{
   &[0]&[2]&[4]&[6]&[8]\cr
[0]&[0]&[0]&[0]&[0]&[0]\cr
[2]&[0]&[4]&[8]&[2]&[6]\cr
[4]&[0]&[8]&[6]&[4]&[2]\cr  
[6]&[0]&[2]&[4]&[6]&[8]\cr
[8]&[0]&[6]&[2]&[8]&[4]\cr}$$
The set is closed under multiplication modulo 10 as can be seen from 
the table.  Multiplication is associative in ${\bf Z}_{10}$, so 
the same is true for multiplication mod 10 on the elements in this subset.  
{\it There is} an identity element for multiplication, but it's not
what you expect.  Look at the row and column for the element $[6]$.
This shows that $[6]$ is an identity for this operation on this subset.  
The only property that fails is that $[0]$ has no multiplicative
inverse -- there is no $[x] \in S$ such that $[0][x] = [6]$.   
Note that the subset $\{[2],[4],[6],[8]\}$ {\it does} form a group 
under multiplication mod 10. 
\bigskip
\noindent
3.1/33.  Let 
$$G = \left\{ \pmatrix{1&a&b\cr
                  0&1&c\cr
                  0&0&1\cr} : a,b,c \in {\bf R} \right\}$$
We claim that $G$ is a group under matrix multiplication.  

First, $G$ is closed under matrix products because 
$$  \pmatrix{1&a&b\cr
                  0&1&c\cr
                  0&0&1\cr}\pmatrix{1&d&e\cr
                                    0&1&f\cr
                                    0&0&1\cr}=\pmatrix{  1&d+a&e+af+b\cr   
                                                         0&1&f+c\cr
                                                         0&0&1\cr}\leqno(1)$$
Since this matrix has the correct form (1's on main diagonal, 0's below, real numbers
above), this is an element of $G$.  Matrix multiplication is associative whenever
the product of three matrices is defined, so that property holds for the matrices
in $G$.  The identity matrix 
$$I = \pmatrix{1&0&0\cr
                  0&1&0\cr
                  0&0&1\cr}$$
is in $G$ (take $a=b=c = 0$), and is an identity element for matrix multiplication.
Finally, from (1) we see that if $d = -a, f = -c,$ and $e = -af - b = ac - b$,
then 
$$\pmatrix{1&a&b\cr
                  0&1&c\cr
                  0&0&1\cr}\pmatrix{1&-a&ac-b\cr
                                    0&1&-c\cr
                                    0&0&1\cr} = \pmatrix{1&0&0\cr
                  0&1&0\cr
                  0&0&1\cr} = I.$$
The product in the other order also gives $I$, so 
$$\pmatrix{1&a&b\cr
                  0&1&c\cr
                  0&0&1\cr}^{-1} = \pmatrix{1&-a&ac-b\cr
                                    0&1&-c\cr
                                    0&0&1\cr}$$
This is a matrix in $G$, so every element of $G$ has an inverse in $G$.
\bye
\bye
