• Support PF! Buy your school textbooks, materials and every day products Here!

Inverse modulo

  • Thread starter brad sue
  • Start date
  • #1
281
0
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
 

Answers and Replies

  • #2
StatusX
Homework Helper
2,564
1
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?
 
  • #3
281
0
StatusX said:
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?
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
 
  • #4
StatusX
Homework Helper
2,564
1
Then you're done. Given that theorem, it's a pretty trivial problem.
 

Related Threads for: Inverse modulo

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
817
  • Last Post
Replies
1
Views
3K
Top