# Calculating the Modular Multiplicative Inverse without all those strange looking symbols

I am sure all those symbols are really easy for you guys to understand, but I would appreciate it if someone could bring it down to earth for me.

How could I do this on a basic calculator? or with a few lines of programmer's code which probably would look strange to you :)

Particularly, I had a hard time knowing why the (mod m) was off to the right and separate, and I am still not sure what the triple-lined equals symbol is all about. Not that I care, but if it is simple, I don't mind reading it that way, if not, I would prefer calculator instructions.

-
Let's be a bit concrete: what calculator are you using? –  Guess who it is. Sep 24 '11 at 13:22
I would like to keep it to the basic functions plus, minus, divide, remainder (modulus), power-of, and if I have to repeat a function many times to get to the final result, I can program that in no problem. If additional functions are necessary, that is fine. I am not sure what I need, but the Modular Multiplicative Inverse and Extended Euclidean are not something I understand. I am hoping that getting the mod_inverse can be broken down to a lower level. The calculator I am using is just a programming language that is capable of mod_inverse directly, but I would like to know what tha means. –  musicwithoutpaper Sep 24 '11 at 13:28

"Particularly, I had a hard time knowing why the (mod m) was off to the right and separate, and I am still not sure what the triple-lined equals symbol is all about."

The notation $(57 \equiv 62) \pmod 5$ means 57 and 62 are congruent to each other modulo 5, i.e. they both leave the same remainder on division by 5. See Modular arithmetic. That notation was introduced by Carl Friedrich Gauss in his book Disquisitiones Arithmeticae published in 1801, and has been standard since that time.

Later when computer programmers started doing modular arithmetic, they introduced a new notation: $57 \bmod 5$ means the remainder when 57 is divided by 5.

Just remember which notation is which and don't confuse them with each other.

The Wikipedia article might benefit from a concrete example or two.

Alright, suppose you want the inverse of 322 when the modulus is the prime number 701. Since 701 is prime, the gcd of 701 and any number that is not a multiple of 701 is 1. We will see that this implies there is a solution to the Diophantine equation $701x+322y=1$ (and if the gcd were something other than 1, there would be a solution if instead of "$=1$" we put "$=\text{whatever that other number is}$").

So apply the Euclidean algorithm, but remember the quotients. Divide 701 by 322; get a quotient of 2 and a remainder of 57: $$701-2\cdot322 = [57].$$ In Euclid's algorithm, we would next divide 322 by 57, getting a quotient of 5 and a remainder of 37: $$322 - 5\cdot [57] = [37].$$ Then divide 57 by 37, getting a quotient of 1 and a remainder of 20: $$[57] - 1\cdot[37] = [20].$$ Divide 37 by 20, getting a quotient of 1 and a remainder of 17: $$[37]-1\cdot[20] = [17].$$ Divide 20 by 17, getting a quotient of 1 and a remainder of 3: $$[20]-1\cdot[17]=[3].$$ Divide 17 by 3, getting a quotient of 5 and a remainder of 2: $$[17]-5\cdot[3]=[2].$$ Divide 3 by 2, getting a quotient of 1 and a remainder of 1: $$[3] -1\cdot[2]=[1].$$ So according to Euclid's algorithm, the gcd is 1, and if that is all we wanted, we'd have needed only the remainders and not the quotients. But now we use the results above it solve $701x+322y=1$. This will imply that $(322y\equiv1)\pmod {701}$, i.e. the multiplicative inverse of 322 is $y$, when the modulus is 701.

I've put square brackets around the numbers found to be REMAINDERS but NOT around the QUOTIENTS.

In place of the remainder 2, in the last line, but the expression found to be equal to 2 in the line before it: \begin{align} [3]-1\cdot[2] & = [1] \\ {[}3{]}-1([17]-5\cdot[3]) & = [1] \end{align} Simplify, getting linear combination of REMAINDERS: $$6[3]-1[17] =1.$$ Now in place of the remainder 3, put the expression found to be equal to it: $$6([20]-1[17])-1[17] = 1.$$ Simplify, getting linear combination of REMAINDERS: $$6[20]-7[17] = 1.$$ Now in place of the remainder 17, put the expression found to be equal to it: $$6[20] - 7([37]-1[20])=1.$$ Simplify, getting linear combination of REMAINDERS: $$13[20]-7[37]=1.$$ Now in place of the remainder 20, put the expression found to be equal to it: $$13([57]-1[37])-7[37]=1.$$ Simplify, getting linear combination of REMAINDERS: $$13[57]-20[37]=1.$$ Now in place of the remainder 37, put the expression found to be equal to it: $$13[57]-20(322-5[57])=1.$$ Simplify, getting linear combination of REMAINDERS: $$113[57]-20[322]=1.$$ Now in place of the remainder 57, put the expression found to be equal to it: $$113([701]-2[322])-20[322]=1.$$ Simplify, getting linear combination of REMAINDERS: $$113[701]-246[322]=1.$$ THEREFORE $(-246\cdot322\equiv1) \pmod{701}$.

Or in other words $(455\cdot322 \equiv1)\pmod{701}$.

So modulo 701, the multiplicative inverse of 322 is 455.

-
That is good to know. I would still like to know how I could calculate this myself. –  musicwithoutpaper Sep 24 '11 at 14:30
I'll add a concrete example. –  Michael Hardy Sep 24 '11 at 14:49
Done. One should add this: very loosely speaking, the statement "A is the same as B modulo C" means A is the same as B except for differences explained by C. The earliest use of this language was by Gauss, when he said, e.g. 57 is the same as 62 modulo 5, i.e. they leave the same remainder on division by 5. The terminology also has many other uses in mathematics. –  Michael Hardy Sep 24 '11 at 15:17

Here's old JS code I had for computing the modular inverse of a with respect to the modulus m, based on a modification of the usual Euclidean algorithm. I must admit that I've forgotten the provenance of this algorithm, so I'd appreciate if somebody could point me to where this modification first appeared:

function modinv(a,m) {
var v = 1;
var d = a;
var u = (a == 1);
var t = 1-u;
if (t == 1) {
var c = m % a;
u = Math.floor(m/a);
while (c != 1 && t == 1) {
var q = Math.floor(d/c);
d = d % c;
v = v + q*u;
t = (d != 1);
if (t == 1) {
q = Math.floor(c/d);
c = c % d;
u = u + q*v;
}
}
u = v*(1 - t) + t*(m - u);
}
return u;
}
-

Consider the element $a \in \mathbb{Z}/m\mathbb{Z}$. It is not hard to show that $a^{-1}$ exists in $\mathbb{Z}/m\mathbb{Z}$ if and only if the gcd of $a$ and $m$ is 1, that is, $a$ and $m$ are coprime. Using Euler's theorem (also sometimes called Fermat's theorem), $a^{\varphi(m)} \equiv 1 \pmod{m}$ for all $a$ coprime to $m$ where $\varphi(m)$ is Euler's totient function. Therefore $$a^{-1} \equiv a^{\varphi(m) - 1} \pmod{m}.$$

So I guess an pseudo-algorithm for computing the inverse of $a \in \mathbb{Z}/m\mathbb{Z}$ could be:

1. Compute the gcd of $a$ and $m$. If this is not equal to 1, exit. Else continue.
2. Compute $\varphi(m)$. One way is to count the number of integers less than $m$, relatively prime to $m$, another way is to use $m$'s prime factorization. There are other much faster ways I think, but these two methods are the most obvious ones.
3. Compute $a^{\varphi(m) - 1}$.
4. Reduce mod $m$.
5. Repeat Step 4 until the result is in $\{0, 1, \ldots, m - 1\}$.
-
Just a note: Euler's Theorem, which states that for $\gcd(a,n) = 1$, we have $$a^{\varphi(n)} \equiv 1\pmod{n},$$ is a generalization of Fermat's Little Theorem, which states that $$a^{p-1} \equiv 1 \pmod{p},$$ whenever $\gcd(a,p) = 1$. They are not the same. –  JavaMan Sep 24 '11 at 17:04

One need not understand congruence arithmetic to understand the extended Euclidean algorithm as applied to computing modular inverses. By Bezout's Identity there are integers $\rm\:x,y\:$ such that $\rm\:m\ x + n\ y\:=\:gcd(m,n) = 1\:,\:$ i.e. $\rm\ n\ y = 1 - m \ x\:.\:$ So, mod $\rm\:m\!:\ n\ y = 1\ \Rightarrow\ y = 1/n\:.\:$ To compute $\rm\:x,y\:$ one may use an extended form of the Euclidean algorithm that is analogous to identity-augmented elimination in linear algebra, e.g. see below from one of my old posts.

For example, to solve  m x + n y = gcd(m,n) one begins with
two rows  [m   1    0], [n   0    1], representing the two
equations  m = 1m + 0n,  n = 0m + 1n. Then one executes
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns,

Here is an example:  d =  x(80) + y(62)  proceeds as:

in equation form   | in row form
---------------------+------------
80 =   1(80) + 0(62) | 80   1   0
62 =   0(80) + 1(62) | 62   0   1
row1 -   row2  ->  18 =   1(80) - 1(62) | 18   1  -1
row2 - 3 row3  ->   8 =  -3(80) + 4(62) |  8  -3   4
row3 - 2 row4  ->   2 =   7(80) - 9(62) |  2   7  -9
row4 - 4 row5  ->   0 = -31(80) -40(62) |  0 -31  40

Above the row operations are those resulting from applying
the Euclidean algorithm to the numbers in the first column,

row1 row2 row3 row4 row5
namely:  80,  62,  18,   8,   2  = Euclidean remainder sequence
|    |
for example   62-3(18) = 8, the 2nd step in Euclidean algorithm

becomes:   row2 -3 row3 = row4  on the identity-augmented matrix.

In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as the identity, and is multiplied by each elementary
row operation matrix, hence it accumulates the product of all
the row operations, namely:

[  7 -9] [ 80  1  0]  =  [2   7  -9]
[-31 40] [ 62  0  1]     [0 -31  40]

row 1 is the particular  solution  2 =   7(80) -  9(62)
row 2 is the homogeneous solution  0 = -31(80) + 40(62),
so the general solution is any linear combination of the two:

n row1 + m row2  ->  2n = (7n-31m) 80 + (40m-9n) 62

The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field,
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form,
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.
-