Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Inverse modulo

  1. Oct 16, 2006 #1
    Hi,
    I need help with this problem.

    Show that if a and m are relatively prime positive integers, then the inverse of a modulo m is unique modulo m.
    [hint: assume that there are 2 solutions b and c of the congruence ax==1(mod m). No need to prove that b==c (mod m) ]

    I have just started:

    a*b==1(mod m) and c*a==1(mod m)-->a*b==c*a(mod m)
    -->b==c (mod m)
    then ??
    Can I have some help please?
    B
     
  2. jcsd
  3. Oct 16, 2006 #2

    StatusX

    User Avatar
    Homework Helper

    b=c (mod m) is what you're trying to prove. The problem is deriving this from a*b=a*c (mod m). You can't just cancel a like in ordinary multiplication (for example, 3*1=3*4 (mod 9), but 1[itex]\neq[/itex]4(mod 9)). a*b=a*c (mod m) is equivalent to saying that m divides a*b-a*c=a*(b-c). What can you conclude from this given that a and m are relatively prime?
     
  4. Oct 16, 2006 #3
    we can say that gcd(a,m)=1 and a*b=a*c (mod m)
    --> b=c(mod m) (according a theorem we saw in class)..
    Am I right?
    B
     
  5. Oct 16, 2006 #4

    StatusX

    User Avatar
    Homework Helper

    Then you're done. Given that theorem, it's a pretty trivial problem.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook