Finding inverses in modular arithmetic

[PsychonautQQ]

Hey PF!

Is there a systematic way to calculate the inverse of a number in a modular setting (modular setting? is that what I call it? lol).

How about 108x == 1 (mod 625), wolfram alpha calculated x = 272, how could I have arrived at this number besides guess and check?

 

[micromass]

There are two nice methods.

The first is by applying the Bezout theorem. This states that if $a$ and $b$ are integers, then there are integers $p$ and $q$ such that $pa+bq = \text{gcd}(a,b)$. In this case we take $a=108$ and $b=625$. The gcd is $1$ (which is a necessary and sufficient condition for finding inverses). So we search for integers $p$ and $q$ such that $108p + 625q=1$. Our $p$ will be the inverse (just look at the equation (mod 625)).

How to find $p$ and $q$? Well, we have the Euclidean algorithm for finding the gcd. So let's do that:

$625 = 108\cdot 5 + 85$
$108 = 85\cdot 1 + 23$
$85 = 23\cdot 3 + 16$
$23 = 16\cdot 1 + 7$
$16 = 7\cdot 2 + 2$
$7 = 2\cdot 3 + 1$
See http://en.wikipedia.org/wiki/Euclidean_algorithm for the details if this is unfamiliar. So we see indeed that the gcd is $1$. Now let us do the Euclidean algorithm in reverse:

$$\begin{eqnarray*}<br /> 1 & = & 7 - 2\cdot 3\\<br /> & = & 7 - (16 - 7\cdot 2)\cdot 3\\<br /> & = & 7\cdot (1 + 2\cdot 3) - 16\cdot 3\\<br /> & = & 7\cdot 7 - 16\cdot 3\\<br /> & = & (23 - 16\cdot 1)\cdot 7 - 16\cdot 3\\<br /> & = & 23\cdot 7 - 16\cdot (1\cdot 7 + 3)\\<br /> & = & 23\cdot 7 - 16\cdot 10\\<br /> & = & 23\cdot 7 - (85 - 23\cdot 3)\cdot 10\\<br /> & = & 23\cdot (7 + 3\cdot 10) - 85\cdot 10\\<br /> & = & 23\cdot 37 - 85\cdot 10\\<br /> & = & (108 - 85\cdot 1)\cdot 37 - 85\cdot 10\\<br /> & = & 108\cdot 37 - 85\cdot (1\cdot 37 +10)\\<br /> & = & 108\cdot 37 - 85\cdot 47\\<br /> & = & 108\cdot 37 - (625 - 108\cdot 5)\cdot 47\\<br /> & = & 108\cdot (37 + 5\cdot 47) - 625\cdot 47\\<br /> & = & 108\cdot 272 - 625\cdot 47<br /> \end{eqnarray*}$$

Thus we get
$$1 = 108\cdot 272 - 625\cdot 47$$
Looking at this equation in (mod 625), we get $108\cdot 272 = 1$. So the inverse of 108 is 272.

A second method is by Euler's theorem (the generalization of Fermat's little theorem): This states that if $\text{gcd}(a,n)=1$, then $a^{\varphi(n)} = 1$ in (mod n). In our case, we get $108^{\varphi(625)} = 1$ in (mod 625). So the inverse is $108^{\varphi(625)-1}$. Now we need to calculate the Euler totient function $varphi$. There are several methods, but let us use this one: http://en.wikipedia.org/wiki/Euler's_totient_function#Euler.27s_product_formula
So since $625 = 5^4$, we get
$$\varphi(625) = 625\cdot (1 - \frac{1}{5}) = 625 - 125 = 500$$
So the inverse is $108^{499}$. This is an easier method to calculate the inverse, but it is more annoying since it leaves us with a tough exponential to calculate. A somewhat similar method but with smaller exponential can be found here http://en.wikipedia.org/wiki/Carmichael_function