Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 11 / iv / 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 $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(\mathrm{mod}m)$ and $y\equiv z(\mathrm{mod}n)$, then $z-x$ is a sum of a multiple of $m$ and a multiple of $n$, so $x\equiv z(\mathrm{mod}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$. ThereforeInterchanging $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.