1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Inverse modulo
  1. Modulo a prime (Replies: 1)

  2. Congruences / modulo (Replies: 3)

Loading...