Past exam of the mathematics course of the University of Cambridge / 2019 / ia / Paper 4 / 6E / c / Solution

Assume $ad\equiv bc(\mathrm{mod}n)$ and choose $r,s$ as in part (b). Put $\lambda =rc+sd$. Multiplying $ra+sb\equiv 1$ by $c$ and using $ad\equiv bc$ givesSimilarly, multiplication by $d$ gives $\lambda b\equiv d(\mathrm{mod}n)$.

Moreover, $\lambda$ is a unit modulo n: if a prime divided both $\lambda$ and $n$, the two congruences would make it divide $c,d,n$, contrary to $(c,d)\in Y$. Thus $R$ means precisely that two pairs differ by multiplication by a unit modulo $n$. Reflexivity, symmetry using ${\lambda }^{-1}$, and transitivity using products of units now show that $R$ is an equivalence relation.