2
$\begingroup$

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!

$\endgroup$
2
  • 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$ Jul 8, 2019 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, 2019 at 9:01

1 Answer 1

2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @fiksx I hope this helps $\endgroup$
    – Kumar
    Jul 8, 2019 at 10:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .