# Modular Inverses?

1. Oct 10, 2007

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

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

thanks

2. Oct 10, 2007

### Hurkyl

Staff Emeritus
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. Oct 10, 2007

### 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

4. Oct 10, 2007

### Hurkyl

Staff Emeritus
Well, if you mean what I think you mean... then doesn't Euclid's theorem come with an algorithm for doing computation?

5. Oct 10, 2007

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

6. Oct 10, 2007

### BenTheMan

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

7. Oct 10, 2007

### smoothman

thnx :D just what i wanted :)

8. Oct 11, 2007

### matt grime

It is more than that - it gives a way to express the HCF of x and y as ax+by.

9. Oct 11, 2007

### 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$$