Congruence and Division.
Suppose \(ad \equiv bd \pmod n\text{.}\) Then \(a \equiv b \pmod{\frac{n}{\gcd(d,n)}}\text{.}\)
If \(d\) and \(n\) have no common factors then \(\gcd(d,n) = 1\text{,}\) so \(a \equiv b \pmod n\text{.}\)
Suppose \(ad \equiv bd \pmod n\text{.}\) Then \(a \equiv b \pmod{\frac{n}{\gcd(d,n)}}\text{.}\)
If \(d\) and \(n\) have no common factors then \(\gcd(d,n) = 1\text{,}\) so \(a \equiv b \pmod n\text{.}\)