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

**lemonsf** · May 13th 2009, 05:02 AM

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.

**Media_Man** · May 13th 2009, 05:41 AM

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

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

As for your example, $20 \equiv 40 (\bmod 10)$ and $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 $ka \equiv kb (\bmod m)$ AND $a \equiv b (\bmod m)$ does not imply $(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 $2^{-1} (\bmod 10)$ , where in fact this number does not exist. Likewise, in your second example, $5^{-1}$ does not exist $(\bmod 10)$ . Therefore if $ka \equiv kb (\bmod m)$ and $a \equiv b (\bmod m)$ where $(k,m) \neq 1$ , this can only be attributed to coincidence, not as proof that the converse holds.

**lemonsf** · May 13th 2009, 06:39 AM

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 $ka \equiv kb (\bmod m)$ , and
$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..

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

LinkBack

Thread Tools

Display

if ka=kb(mod m), gcd(k,m)=1 => a=b(mod m), is this true?

Converse Confusion

Similar Math Help Forum Discussions

prove whether the set property is true, false, or sometimes true and sometimes false?

Prove whether the set property is always true, always false, or sometimes true or fal

help which one is not true

True or False. Prove if true show counter example if false.

is that true?

Search Tags