Results 1 to 3 of 3

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

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    2

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Converse Confusion

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2009
    Posts
    2

    Talking

    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..
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: October 5th 2011, 01:45 PM
  2. Replies: 1
    Last Post: October 4th 2011, 03:19 AM
  3. help which one is not true
    Posted in the Geometry Forum
    Replies: 1
    Last Post: April 11th 2010, 11:53 PM
  4. True or False. Prove if true show counter example if false.
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: March 2nd 2010, 11:54 AM
  5. is that true?
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: October 2nd 2009, 08:00 PM

Search Tags


/mathhelpforum @mathhelpforum