Modular Inverses?

  • Thread starter smoothman
  • Start date
  • #1
39
0
Hi is there a general formula to find the inverse modulo of "a modulo n"...
i know its denoted as [itex]a^{-1}[/itex] and
[itex]a.a^{-1} = 1 mod n[/itex]

for example if a=29 and n = 78 then the inverse is 35 since: 29.35 = 1 mod 78...

(a)
but HOW DO U CALCULATE THE INVERSE? is there a formula?? please help me out here?

(b)
and how can this be used to solve 43 modulo 125, hence solve 43x = 3 mod 125

thanks
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Well, if you unroll the definition, you have

ua = 1 (mod n)

if and only if you can find a v such that

ua + vn = 1.

Does that look familiar at all?
 
  • #3
39
0
thats euclids theorem im guessing?

could u show me how to calculate for a = 29 and n =78???
so that u get the inverse of 29 as 35??
then ill try part B and see if i can do it :) thanks
 
  • #4
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
thats euclids theorem im guessing?
Well, if you mean what I think you mean... then doesn't Euclid's theorem come with an algorithm for doing computation?
 
  • #5
39
0
yea but thats for just finding HCF...
i need to know if theres a formula for finding the inverse
you said :

"if and only if you can find a v such that
ua + vn = 1."

to do this.. do i have to manually go through all the possibilites or is there an algorithm etc? thnx :)
 
  • #6
478
0
search wikipedia or google for ``diophantine equation''. There is an algorithm.
 
  • #7
39
0
thnx :D just what i wanted :)
 
  • #8
matt grime
Science Advisor
Homework Helper
9,395
3
yea but thats for just finding HCF...
It is more than that - it gives a way to express the HCF of x and y as ax+by.
 
  • #9
1,056
0
There is another way. Using the Euler phi function, we can determine the n such that 29^n==1 Mod 78 for example. In this particular case it is 2(1-1/2)*3(1-1/3)*13(1-1/13) = 24. So that:

[tex]29^{23}\equiv\frac{1}{29} Mod 78[/tex]
 

Related Threads on Modular Inverses?

Replies
1
Views
828
  • Last Post
Replies
6
Views
572
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
5
Views
572
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
7
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
5
Views
2K
Top