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

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

• If $a(b-c)=mn$, for some $m$, and $(a,n)=1$, then what can you say about $a$ and $m$? If $a$ is a factor of $mn$, and $(a,n)=1$, then can you say $a$ divides $m$? Now the answer should be clear. – Teresa Lisbon Aug 1 '16 at 9:14
• Note that you've used $r$ twice here. In general, those will be different, and should therefore be denied by different letters. – Arthur Aug 1 '16 at 9:18
• @астонвіллаолофмэллбэрг Yes i got it. Thanks – Gathdi Aug 1 '16 at 9:23
• @Gathdi Welcome. – Teresa Lisbon Aug 1 '16 at 9:25

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

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

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

• I know nothing of rings yet – Gathdi Aug 1 '16 at 10:24
• @Gathdi: OK. I just meant that in this case, it's almost obvious. I've changed my answer accordingly. – Bernard Aug 1 '16 at 10:35

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$

• BTW you can write math like this $n\mid ab-ac$ (which is entered as $n\mid ab-ac$). For some basic information about writing math at this site see e.g. here, here, here and here. – Martin Sleziak Sep 15 '16 at 15:42
• BTW the way your answer is currently written it is not clear where you use that fact that $n$ and $a$ are coprime (i.e. $\gcd(n,a)=1$). It is not true that $n\mid a(b-c)$ and $n\nmid a$ implies $n\mid b-c$. – Martin Sleziak Sep 15 '16 at 15:43
• Any example how it is not true would be really helpful. – jnyan Sep 15 '16 at 15:57
• Take $n=4$, $a=2$, $b=2$, $c=0$. Clearly $4\mid 2\cdot 2$ and $4\nmid2$. – Martin Sleziak Sep 15 '16 at 15:59