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.

Inspiring from this thread Is there a formula for solving the congruence equation $ax^2 + bx + c=0$?

I want to get rid of the confusion when dividing both side of congruence.

I'm always confused about modulo arithmetic, so today I really want to make it clear.
If $a \equiv b \pmod{m}$ then obviously, $ac \equiv bc \pmod{m}$.
But it doesn't always work for division. What is the reason behind? Whenever I see division, I'm totally freak out. Multiplication makes sense to me, but not division. Could anyone walk me through this obstacle?

Another question is,
According to Arturo Magidin:

"dividing" by $2a$ means multiplying by the modular inverse of $2a$ modulo p"

Does it always work for any modulo $m$ or $m$ has to be prime?

Thank you

share|improve this question

1 Answer 1

up vote 8 down vote accepted

This comes down to the following general result:

Theorem. Let $R$ be a ring. Then $$ax = ay\text{ implies }x=y \Longleftrightarrow az=0\text{ implies }z=0.$$

Proof. $\Rightarrow)$ Assume that whenever $ax=ay$, we can conclude $x=y$. Suppose $az=0$. Then $az=a0$, so this implies $z=0$.

$\Leftarrow)$ Suppose that whenever $az=0$, we have $z=0$. If $ax=ay$, then $a(x-y) = ax-ay = 0$, so $x-y = 0$; therefore, $x=y$. QED

That is, cancellation works whenever what you are cancelling is not a zero divisor (and more specifically, cancellation on the left/right works when what you are cancelling is not a left/right zero divisor).

In particular, when you are working in modular arithmetic $$ab\equiv ac\pmod{m}\text{ implies }b\equiv c\pmod{m}\Longleftrightarrow az\equiv0\pmod{m}\text{ implies } z\equiv 0\pmod{m}.$$

Proposition. Let $a$ and $m$ be positive integers. Then $\gcd(a,m)=1$ if and only if $az\equiv 0\pmod{m}$ implies $z\equiv 0\pmod{m}$.

Proof. If $\gcd(a,m)=1$ and $az\equiv 0\pmod{m}$, then $m|az$ and $\gcd(m,a)=1$, which implies $m|z$. Therefore $z\equiv 0\pmod{m}$.

Conversely, suppose $az\equiv 0\pmod{m}$ implies $z\equiv 0\pmod{m}$. Let $d=\gcd(a,m)$, and write $a=dk$, $m=d\ell$. Then $a\ell = dk\ell = mk\equiv 0\pmod{m}$, so $\ell\equiv0\pmod{m}$. Therefore, $m|\ell$, Since $m=k\ell$, $k=1$. QED.

Corollary. Let $a$, $b$, $c$, and $m$ be positive integers. Then $ab\equiv ac\pmod{m}$ implies $b\equiv c\pmod{m}$ if and only if $\gcd(a,m) = 1$.

So, first, you should not think of this as "division", but as "cancellation" (for example, one can cancel in the integers, even though there is no "division"). And you should think of "division" in general not as an entirely separate operation, but really as "multiplying by the multiplicative inverse". For example, in the rationals, you don't "really" divide by $3$, you multiply by $\frac{1}{3}$, which is the (unique) rational which, when multiplied by $3$, gives $1$; that is, the multiplicative inverse of $3$.

share|improve this answer
    
Thank you very much. –  Chan Apr 4 '11 at 3:33

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.