= Solution
An <equivalence relation> on $A$ is a <binary relation> that is reflexive, symmetric and transitive: $xRx$ for every $x$; $xRy\Rightarrow yRx$; and $xRy,\ yRz\Rightarrow xRz$. Write $T=R\circ S$, using the stated order for <composition of relations>. Composition is associative because both possible bracketings mean that there is a two-step sequence of intermediate witnesses. <Reflexivity> shows
$$
R\subseteq T,\qquad S\subseteq T,
$$
and also that $T$ is reflexive. <Transitivity> and <reflexivity> of the original relations give $R\circ R=R$, $S\circ S=S$. Since both original relations are symmetric,
$$
T^{-1}=(R\circ S)^{-1}=S\circ R.
$$
The four parts below show that each condition is equivalent to the <commuting equivalence relations> condition $R\circ S=S\circ R$.
For the integer example, put $d=\gcd(m,n)$. Membership of $(x,z)$ in the composite means that some $y$ satisfies $y-x=ma$, $z-y=nb$ for integers $a,b$. Consequently $z-x=ma+nb$ is divisible by $d$. Conversely, if $z-x$ is divisible by $d$, the <Bezout identity> expresses it as $ma+nb$; setting $y=x+ma$ provides the required witness. Thus
$$
\boxed{R\circ S=\{(x,z)\in\mathbb Z^2:x\equiv z\pmod d\}.}
$$
Reversing the roles of $m,n$ gives exactly the same <modular congruence> relation, hence $R\circ S=S\circ R$. This verifies all four conditions and identifies their common smallest <equivalence relation> explicitly.
Back to article page
