Under what condition does $ac\equiv bc\ (mod\ n)$ imply that $a\equiv b\ (mod\ n)$? I took some notes in class today, and it appears I wrote something down wrong. I wonder if somebody can tell me what it should be...

If $ac\equiv bc\ (mod\ n)$ and $c$ and $d$ are relatively prime, then $a\equiv b\ (mod\ n)$.

The dead giveaway here is that there is no $d$ in my equation. So I'm wondering if the prof miswrote, or if I did...
The question is - what condition has to be met for this to be true, using the variable labels that I have here... $a,b,c,n$?
 A: The $d$ should be $n$.  This is because $c$ is invertible modulo $n$ if and only if it is relatively prime to $n$ (by the Euclidean algorithm, more or less).
If $c$ has an inverse modulo $n$, then we can multiply by the inverse on both sides to get $a\equiv b \pmod n$.
If $c$ and $n$ are not relatively prime, then for any $a$ we have $ac\equiv (a+\frac{n}{c})c \pmod n$, and it is possible for both $a$ and $a+\frac{n}{c}$ to be in the range $\{0,\ldots,n-1\}$.  For example $2\cdot 2\equiv 7\cdot 2 \pmod{10}$.
A: If $ac \equiv bc$ (mod $n$) and $c$ and $n$ are relatively prime, then $a \equiv b$ (mod $n$).
A: $ac \equiv bc \ (mod n) $ means $n$ divides $ac-bc$ so $ac-bc = nk$ for some integer $k$. I f you divide both sides by $c \neq 0$, then you must have $a-b = nk/c$, thus $nk/c = n m$ where $m$ is an integer if you want this to hold. Any $k/c$ which is an integer will satisfy this.
A: Hint $\rm\ n\mid (a\!-\!b)c\!\iff\! n\mid (a\!-\!b)\,gcd(c,n)\:$ is equivalent to $\rm\:n\mid a\!-\!b\ $ iff $\rm\ gcd(c,n)=1.$
Indeed, in $\rm\:\Bbb Z/n,\:$ $\rm\,c\:$ is cancelable $\rm\iff c\:$ is invertible $\rm\!\iff gcd(c,n) = 1.\:$ More generally  a finite ring is a field iff it is a domain.
