2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Teresa Lisbon Aug 1 '16 at 9:14
  • $\begingroup$ Note that you've used $r$ twice here. In general, those will be different, and should therefore be denied by different letters. $\endgroup$ – Arthur Aug 1 '16 at 9:18
  • $\begingroup$ @астонвіллаолофмэллбэрг Yes i got it. Thanks $\endgroup$ – Gathdi Aug 1 '16 at 9:23
  • $\begingroup$ @Gathdi Welcome. $\endgroup$ – Teresa Lisbon Aug 1 '16 at 9:25
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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

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 $

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ – Martin Sleziak Sep 15 '16 at 15:42
  • 1
    $\begingroup$ 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$. $\endgroup$ – Martin Sleziak Sep 15 '16 at 15:43
  • $\begingroup$ Any example how it is not true would be really helpful. $\endgroup$ – jnyan Sep 15 '16 at 15:57
  • $\begingroup$ Take $n=4$, $a=2$, $b=2$, $c=0$. Clearly $4\mid 2\cdot 2$ and $4\nmid2$. $\endgroup$ – Martin Sleziak Sep 15 '16 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.