= Solution
Assume $ad\equiv bc\pmod n$ and choose $r,s$ as in part (b). Put $\lambda=rc+sd$. Multiplying $ra+sb\equiv1$ by $c$ and using $ad\equiv bc$ gives
$$
\lambda a=rac+sad\equiv rac+sbc\equiv c\pmod n.
$$
Similarly, multiplication by $d$ gives $\lambda b\equiv d\pmod 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>.
Back to article page
