= Solution
Assume any of conditions (i)–(iii). The established <reflexivity>, <symmetry> and <transitivity> make $T$ an <equivalence relation>, and it contains both $R,S$. If $E$ is any <equivalence relation> containing $R,S$ and $xRaSz$, then $xEaEz$, so <transitivity> of $E$ gives $xEz$. Thus $T\subseteq E$. This proves that \b[$T$ is the unique smallest equivalence relation containing $R$ and $S$]. Conversely, condition (iv) explicitly makes $T$ an <equivalence relation>, so it has properties (i) and (ii). Together these implications prove all four conditions equivalent.
For the final integer example, let $g=\gcd(m,n)$. If $x\equiv y\pmod m$ and $y\equiv z\pmod n$, then $z-x$ is a sum of a multiple of $m$ and a multiple of $n$, so $x\equiv z\pmod g$. Conversely, if $g$ divides $z-x$, <Bezout identity> provides integers $a,b$ with $z-x=am+bn$. Set $y=x+am$. Then $y-x$ is divisible by $m$ and $z-y$ by $n$, so $xRySz$. Therefore
$$
\boxed{R_m\circ R_n=R_{\gcd(m,n)}=R_n\circ R_m.}
$$
Interchanging $m,n$ gives the other equality. The composite is thus exactly congruence modulo the <greatest common divisor>, an <equivalence relation>, and all four equivalent conditions hold.
Back to article page
