# Thread: if k*a=k*b(mod m), gcd(k,m)=1 => a=b(mod m), is this true?

1. ## if k*a=k*b(mod m), gcd(k,m)=1 => a=b(mod m), is this true?

Greetings, was going over some of my old notes the other day and came across something which I can't quite work it out in my head.....

the offending statement...

Code:
 given k*a = k*b ( mod m ), if k and m are co-prime, then a = b ( mod m )
which is fair enough, but the example that is given confuses me somewhat...

Code:
20 = 40 (mod 10), dividing by 2 gives  10 = 20 (mod 10) which holds...
but dividing by 5 gives  4 = 8 (mod 10) which doesn't hold.
This would imply that gcd(2,10)=1, but gcd(5,10) != 1 so 5 and 10 are not co-prime....

10 = 5 * 2
5 = ( 2 * 2 ) + 1
2 = ( 2 * 1 )

10 = 2 * 5
2 = ( 2 * 1 )

But what I can't get in my head is...

by the definition of co-prime, two numbers m,n are said to be co-prime if they share no proper factors ( i.e gcd(m,n) = 1 ).

For 5 and 10, their greatest factor ( other than itselt 5 ) is 1, since all that go into 10 and 5 properly are 5 & 1, but under the same assumption couldn't you say this for 2 and 10, since the only numbers that go into 2 & 10, are 2 & 1.

This would make them both co-prime, yet this would imply that the 'offending statement' is not true....

I have a funny feeling I am missing something obvious here.... help would be appreciated...

Many thanks.

2. ## Converse Confusion

In modular arithmetic, $\displaystyle a^{-1}$ exists $\displaystyle (\bmod m)$ if and only if $\displaystyle a$ and $\displaystyle m$ are coprime.

Suppose $\displaystyle ka\equiv kb (\bmod m)$. Since $\displaystyle (k,m)=1$, there exists an element $\displaystyle k^{-1} (\bmod m)$. Multiplying on both sides gives $\displaystyle k^{-1}ka \equiv k^{-1}kb (\bmod m)$ so $\displaystyle a \equiv b (\bmod m)$.

As for your example, $\displaystyle 20 \equiv 40 (\bmod 10)$ and $\displaystyle 10 \equiv 20 (\bmod 10)$. This absolutely holds, but that is not to say that one implies the other. Remember basic logic, if there is an earthquake in India and the stock market crashes in America, one did not necessarily imply the other . Similarly $\displaystyle ka \equiv kb (\bmod m)$ AND $\displaystyle a \equiv b (\bmod m)$ does not imply $\displaystyle (k,m)=1$. That would be the converse of the above correct theorem, and the converse of a true statement cannot be assumed to be true.

When you are "dividing by two" that is actually an illegal operation in modulo. You are implying that there exists a number $\displaystyle 2^{-1} (\bmod 10)$, where in fact this number does not exist. Likewise, in your second example, $\displaystyle 5^{-1}$ does not exist $\displaystyle (\bmod 10)$. Therefore if $\displaystyle ka \equiv kb (\bmod m)$ and $\displaystyle a \equiv b (\bmod m)$ where $\displaystyle (k,m) \neq 1$, this can only be attributed to coincidence, not as proof that the converse holds.

3. Ok, many thanks Media_Man, that has cleaned up 90% of my confusion...

As you said the example does not prove that gcd(k,m) = 1..... so there are cases when
$\displaystyle ka \equiv kb (\bmod m)$, and
$\displaystyle a \equiv b (\bmod m)$ in which k and m are not co-prime.. i.e 2.

However, if they are co-prime, it does hold.... (which is in fact what the statement says originally ...misread, and thought it implied something )

Many Thanks..