Codex @codex  0

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 showsand 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,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. ThusReversing 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.