To prove that if $ab\equiv ac\bmod n$ and $(a,n)=1$ then $b\equiv c\bmod n$

Question

To prove that if $ab \equiv ac\bmod n$ and $(a,n)=1$ then $b\equiv c \bmod n$

I write as

$1=ar+ns$

$ac=ab+nq$

I have to prove $c=b+nr$

How do I manipulate equations to reach conclusion

Thanks

Answer 1

I think your notation is a little wrong. I think what you're asking is:

If $$ab \equiv ac \mod{n}$$ and $(a,n)=1$, then $b \equiv c \mod{n}$

As you suggest, write $a(b-c)=nq$ and $1=ar+ns$.

Multiplying through by $r$, we have $ar(b-c)=nqr$, so $(1-ns)(b-c)=nqr$.

It follows that $b-c=n(qr+s(b-c))$, so $b-c$ is divisible by $n$.

Answer 2

$$ac=ab+nq$$ means $a(c-b)=nq$, in other words $n$ divides $a(c-b)$. But $$1=ar+ns$$ so either $n=\pm1$ or $n$ does not divide $a$.

If $n=\pm1$ then as $b=c+(b-c)(1)=c+(c-b)(-1)$, we have $b\equiv c\pmod n$.

If $n$ does not divide $a$, but $n$ divides $a(c-b)$, then $n$ must divide $c-b$, i.e. again $b\equiv c\pmod n$.

Answer 3

As $\gcd(a,n)=1$, we have a Bézout's relation: $\; ua+vn=1$, so $ua\equiv 1\mod n$.

Now $\quad ab\equiv ac\implies uab\equiv uac\iff 1\cdot b\equiv 1\cdot c\mod n$.

Answer 4

n divides ab-ac or a(b-c).

n cannot divide a.

That implies n divides (b-c)

Edit: since $ n | a *(b-c)$ , prime factorisation of $ a * (b-c) $ should contain or include prime factorisation of $ n$.

Since $a, n$ are co-prime, $a$ does not contain any prime factors of $n$, thus $ b-c $ should contain all the prime factorisation of $n$, meaning $ n | b-c $