# Modular Inverses?

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)

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

thanks

Hurkyl
Staff Emeritus
Gold Member
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?

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
Staff Emeritus
Gold Member
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?

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

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

thnx :D just what i wanted :)

matt grime
$$29^{23}\equiv\frac{1}{29} Mod 78$$