Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
if $c$ and $n$ are coprime you can divide by $c$ –  yoyo Mar 18 '13 at 22:06

4 Answers 4

up vote 4 down vote accepted

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.