prove or disprove if $ab\equiv ac \bmod m$ then $b\equiv c \bmod m$

there is a theorem said that this equality holds when gcd(a,m)=1 so I try to find a counterexample to disprove this for example

$2.9 \equiv 2.3 \bmod 9$ because gcd(2,9)=1
then $9\equiv 3 \bmod 6$ holds

but $4.6 \equiv 4.3 \bmod 2$ and gcd(4,2)=2
then $6\equiv 3 \bmod 2$ this not holds

$2.6 \equiv 2.2 \bmod 2$ and gcd(2,2)=2
but $6\equiv 2 \bmod 2$ this holds although gcd (a,m) not 1?

$4.6 \equiv 4.2 \bmod 2$ and gcd(4,2)=2
but $6\equiv 2 \bmod 2$ , $2k=4$ why this holds when gcd (a,m) not 1 too?

is this also related to multiplicative inverse? and one more thing I want to ask

if gcd($a,b$)$=1$, then I can write this as $ax+by=1$ for some integers $x$ and $y$. Is gcd($x,y$) has to be $1$ or coprime? if yes why is that? thanks!

  • 4
    $\begingroup$ It may still be true without $a$ and $m$ being coprime, but in general isn't. Consider $2\cdot 2\equiv 2\cdot 3\bmod 2$, but $2\not\equiv 3\bmod 2$. $\endgroup$ – Dietrich Burde Jul 8 '19 at 8:43
  • $\begingroup$ @DietrichBurde if in general it isnt, so this only holds when gcd(a,m)=1? and i have to disprove when gcd(a,m) is not 1 and prove when gcd (a,m)=1 only? $\endgroup$ – fiksx Jul 8 '19 at 9:01

In general if we have that $$ab\equiv ac\mod{m}\\ \implies ab=ac+qm$$ Now, if $a\neq0$ and gcd($a,m$)$=z$ $$\implies a(b-c)=qm \\ \implies a|qm \\ \implies (\frac{a}{z})|q \\ \implies a(b-c-(\frac{q}{(\frac{a}{z})})(\frac{m}{z}))=0 \enspace \text{because} \enspace a\neq 0\\ \implies b\equiv c \enspace \text{mod} \enspace \frac{m}{z}$$ Now, if $z=1$, we have $$b\equiv c \enspace \text{mod} \enspace m$$

The answer of the second Question:

Suppose, gcd($x,y$)$=d>1$.
Therfore, $x$ and $y$ can be expressed as $x=dr$ and $y=ds$, for some $r,s\in \mathbb{N}$.

Now, We have $$ax+by=1\\ \implies adr+bds=1\\ \implies d(ar+bs)=1\\ \implies d|(ax+by)\\ \implies d|1 \\ \implies d=1$$ This is a contradiction because $d>1$

Therefore, gcd ($x,y$)$=1$.

  • $\begingroup$ @fiksx I hope this helps $\endgroup$ – Kumar Jul 8 '19 at 10:46

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.