Paragraph

Suppose \(ad \equiv bd \pmod n\text{.}\) In other words, we have \(ad = bd + kn\) for some integer \(k\text{.}\) Of course \(ad\) is divisible by \(d\text{,}\) as is \(bd\text{.}\) So \(kn\) must also be divisible by \(d\text{.}\) Now if \(n\) and \(d\) have no common factors (other than 1), then we must have \(d \mid k\text{.}\) But in general, if we try to divide \(kn\) by \(d\text{,}\) we don't know that we will get an integer multiple of \(n\text{.}\) Some of the \(n\) might get divided as well. To be safe, let's divide as much of \(n\) as we can. Take the largest factor of both \(d\) and \(n\text{,}\) and cancel that out from \(n\text{.}\) The rest of the factors of \(d\) will come from \(k\text{,}\) no problem.