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

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!

• 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$. – Dietrich Burde Jul 8 '19 at 8:43
• @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? – 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$$
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$$.