5
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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