Unique Inverse of a Modulo m When a and m are Relatively Prime

[brad sue]

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

 

[StatusX]

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\neq4(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?

 

[brad sue]

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\neq4(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?

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

 

[StatusX]

Then you're done. Given that theorem, it's a pretty trivial problem.