\magnification=\magstep1
\centerline{Mathematics 243 -- Algebraic Structures}
\centerline{Discussion 2 -- Congruences and Congruence Classes}
\centerline{October 23, 2006}
\bigskip
\noindent
{\it Background}
\bigskip
Recall that last Friday we showed that for all integers $n > 1$,
the {\it congruence modulo $n$ relation}
$$x \equiv y \bmod n \quad \Leftrightarrow n|(x - y)$$
on ${\bf Z}$ satisfies the following properties:
\bigskip
\item{$\bullet$}  If we divide $n$ into $x$ and obtain a 
remainder of $r$, $0 \le r < n$, then the equation $x = qn + r$
shows $x - r = qn$, so $x \equiv r \bmod n$.  This means that every integer
$x$ belongs to (exactly one) of the congruence classes 
$$[0], [1], [2], \ldots, [n - 1].$$
\item{$\bullet$}  (the ``substitution laws'')  If $x \equiv \ell \bmod n$
and $y \equiv m \bmod n$, then 
$$\eqalign{x + y &\equiv \ell + m \bmod n\cr
        x\cdot y &\equiv \ell\cdot m \bmod n\cr}$$
\bigskip
\noindent
Today, we want to use these facts to work with congruences in several 
additional ways.  
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\noindent
A)  (``warm up'')  Find all $x \in {\bf Z}$ that satisfy the congruence
$$ 7x + 3 \equiv 23 \bmod 32 $$
(Hint:  What number $y$ with $0 < y < 31$ satisfies $7y \equiv 1 \bmod 32$?)
\bigskip
\noindent
B)  The substitution laws for congruences imply, for instance that if $n = 3$
and $x \in [1]$ and $y \in [2]$ are any elements, then 
$$x + y \equiv 1 + 2 \equiv 0 \bmod 3.$$
Similarly 
$$x \cdot y \equiv 1 \cdot 2 \equiv 2 \bmod 3.$$
In fact we can record all possible products and sums in tables for 
an ``addition mod 3'' operation ($+_3$) and a ``multiplication mod 3''
($\cdot_3$) operation.  Those tables look like this:
\bigskip
$$\matrix{+_3 & [0] & [1] & [2]\cr
          [0] & [0] & [1] & [2]\cr
          [1] & [1] & [2] & [0]\cr
          [2] & [2] & [0] & [1]\cr} \qquad  \matrix{\cdot_3 & [0] & [1] & [2]\cr
                                                    [0] & [0] & [0] & [0]\cr
                                                    [1] & [0] & [1] & [2]\cr
                                                    [2] & [0] & [2] & [1]\cr}$$
The question here is:  What do the corresponding tables look like for the 
``addition modulo 7'' and ``multiplication modulo 7'' operations look like?
These are two binary operations on the set of congruence classes mod 7:
$$\{[0], [1], [2], [3], [4], [5], [6]\}$$
\bigskip
\noindent
C)  At some point in your ``mathematical past'', you have probably seen 
the following ``trick'' for testing whether an integer is divisible by $3$ (or $9$):
Take the sum of the base 10 digits of the number $n$, call that sum $S$,
and see whether that 
sum is divisible by $3$ (or $9$).  Then 
$$\eqalign{
3 | n &\Leftrightarrow 3 | S\ {\rm and}\cr
9 | n &\Leftrightarrow 9 | S\cr}\leqno(1)$$
For example, if $n = 83843$, then $S = 8 + 3 + 8 + 3 + 4 = 26$.  This is
divisible by neither $3$ nor $9$, so $n$ is {\it not} divisible by either $3$ or $9$.
(In fact it is easy to see that $83843 \equiv 2 \bmod 3$ and $83843 \equiv 8 \bmod 9$.
We would need $n\equiv 0 \bmod 3$ to say
$3$ does divide $n$, and similarly for $9$.)
On the other hand if $n = 252$, then $S = 2 + 5 + 2 = 9$, so $n$ is divisible
by {\it both} $3$ and $9$.
The question here is:  {\it Why does this ``trick'' work}?  Give a proof of the 
equivalences in (1), using the substitution laws and the meaning of the 
usual base 10 expansion of an integer.  For example, when 
we write $n = 83843$ in base 10, we mean 
$$n = 8\cdot 10^4 + 3 \cdot 10^3 + 8\cdot 10^2 + 4 \cdot 10^1 + 3\cdot 10^0.$$
In general, if 
$$n = d_k \cdot 10^k + \cdots + d_2\cdot 10^2 + d_1\cdot 10 + d_0 \cdot 10^0$$
where $d_k, \ldots, d_0$ are the base 10 digits of the number, then
$$S = d_k + \cdots + d_2 + d_1 + d_0,$$
and what you need to show is 
$$\eqalign{
3 | n &\Leftrightarrow 3 | S = d_k + \cdots + d_2 + d_1 + d_0 \ {\rm and}\cr
9 | n &\Leftrightarrow 9 | S\cr}$$
\bigskip
\noindent
{\it Assignment}
\bigskip
Group writeups due on Friday, October 27. 
\bye
