# 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$?

-
if $c$ and $n$ are coprime you can divide by $c$ –  yoyo Mar 18 '13 at 22:06

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}$.

-

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

-

$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.

-

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.

-