From: achou@theory.lcs.mit.edu (Andrew Chou)
Date: Tue, 27 Feb 96 13:51:15 EST
To: 6042-tas

My two problem suggestions:

1)
A binary tree is defined as follows.
1) A single node is a binary tree.
2) If $T_1$ and $T_2$ are binary trees, then
           n 
          / \
	T_1 T_2
is a binary tree.

For each leaf, assign it weight $2^{-d}$ where
$d$ is the depth of the leaf.
The depth of leaf is the length of the shortest path from the root
to the leaf.

Let $S$ denote the set of leaves.
Prove
that 
\[
\sum_{l \in S} w(l) = 1.
\]

2)
Define the L=lcm (a,b) to the least number such a|L and b|L
Prove
lcm (a,b) = \frac{ab}{\gcd(a,b)}
-----------------------


\documentstyle[12pt]{article}

\input{macros-course}
%% (Daniele Micciancio)

\begin{document}

\begin{problems}

\problem

In this problem $R_k$ denotes
the ``congruence modulo $k$'' equivalence
relation:
\[ R_k = \{(a,b) \colon a\equiv b \mod{k}\}. \]
 
Let $n$ and $m$ be two positive integers $\geq 2$.
Consider the equivalence relations $R_n$ and $R_m$.


\bparts

\ppart Prove that the union of $R_m$ and $R_n$
\[R=R_n\cup R_m\] 
is not an equivalence relation.

\ppart Now consider $R$ composed with itself:
\[R\circ R = \{(a,c)\mid \exists b.(a,b)\in R \wedge (b,c)\in R\}\]
Prove that $R\circ R = R_n\circ R_m$.

\ppart Finally, prove that 
\[R_n\circ R_m = R_{gcd(n,m)}.\]

\eparts

Notice that from part $(b)$ and $(c)$ it follows
that $R\circ R=R_{gcd(n,m)}$, and therefore 
$R\circ R$ is an equivalence relation.

\problem

Consider two equivalence relations $E_1$ and $E_2$.
Their union $E_1\cup E_2$ is generally not an equivalence relation.
The {\em least upper bound} of $E_1$ and $E_2$
(written $E_1\vee E_2$) is the smallest 
equivalence relation that contains both $E_1$ and $E_2$.

Given three equivalence relations $E_1$, $E_2$ and $E$,
in order to show that $E=E_1\vee E_2$ you must prove
two things: 
\begin{enumerate}
 \item $E$ contains both $E_1$ and $E_2$:
  \[ E_1\cup E_2 \subseteq E \]
 \item $E$ is the smallest equivalence relation satisfying 
  property $(1)$:
  for any (other) equivalence relation $E'$
  such that $E_1 \subseteq E'$ and $E_2 \subseteq E'$, 
  then also $E\subseteq E'$.
\end{enumerate}

It can be formally proved that $E_1\vee E_2$ always
exists and it is unique, 
so $\vee$ is a well defined binary operation 
between equivalence relations.

Consider the {\em congruence modulo $n$} 
equivalence relation over the integers:
\[ R_n = \{(a,b) \colon a\equiv b \mod{n}. \]

In this problem you have to  prove that the 
least upper bound of the ``congruence modulo $n$''
and ``congruence modulo $m$'' equivalence relations
is the congruence modulo the $gcd(m,n)$:
\[R_n \vee R_m = R_{gcd(m,n)}.\]

\bparts

\ppart
Prove that 
\[R_n\circ R_m\subseteq R_m\vee R_n\]
(remember that $R_m\vee R_n$ is an equivalence relation 
and it contains both $R_m$ and $R_n$).

\ppart
Show that both $R_n$ and $R_m$ are contained
in $R_n\circ R_m$:
\[ R_n\cup R_m\subseteq R_n\circ R_m\]

\ppart
Prove that $R_n\circ R_m$ is an equivalence relation
(show that it is symmetric, reflexive and transitive).

\ppart
Use the results in parts $a)$, $b)$ and $c)$  
to prove that 
\[R_n\circ R_m = R_m\vee R_n\]

\ppart Prove that 
$R_n\circ R_m = R_{gcd(n,m)}$.

\eparts

\end{problems}

\end{document}

-------------

MEYER

\ppart Prove that if $\gcd(m,n) = 1$, then $m$ is {\em not} a zero-divisor modulo $n$.

-------------------