Inverse of b mod n: Find, Steps, Examples

[LordCalculus]

What's the basic procedure in finding the inverse of b modulo n? What are the steps? Say, for example, the inverse of 5 modulo 7.

 

[dodo]

Hi,
in your example, you look for the value of x in the equation
5x == 1 (mod 7)
The definition of congruence tells you that 5x-1 must be a multiple of 7. That is,
5x - 1 = 7y
for some integer y. Then
5x - 7y = 1
and you look for integer values of x and y that satisfy this equation; you can throw away the y, and the x is your inverse.

The inverse will exist in your example because 5 and 7 are coprime. This is a general rule: the GCD of the two numbers must be 1. In the last equation, if 5 and 7 had a common factor, then the right-hand side (which is just 1) would have to have that factor too!

To solve this equation, the keyword you have to google for is "extended Euclidean algorithm". The Wikipedia page has all the information, but is not necessarily the clearest explanation. Here are two very simple examples,
http://www.mast.queensu.ca/~math418/m418oh/m418oh04.pdf
In these examples the GCD of the two numbers is not 1, but the method is the same: you obtain two coefficients that solve a linear expression, as in the last equation above.

Hope this helps --

P.S.: Forum admins... is there something wrong with the LaTeX feature? All equations would just show as repetitions of the first one (as if the produced images were going to the same rewritten file, if you wish).