Modular Inverses?

[smoothman]

Hi is there a general formula to find the inverse modulo of "a modulo n"...
i know its denoted as a^{-1} and
a.a^{-1} = 1 mod n

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

[Hurkyl]

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?

[smoothman]

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

[Hurkyl]

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?

[smoothman]

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 :)

[BenTheMan]

search wikipedia or google for ``diophantine equation''. There is an algorithm.

[smoothman]

thnx :D just what i wanted :)

[matt grime]

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.

[robert Ihnot]

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:

29^{23}\equiv\frac{1}{29} Mod 78