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