# 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? – J. M. isn't a mathematician 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 = .$$ In Euclid's algorithm, we would next divide $322$ by $57$, getting a quotient of $5$ and a remainder of $37$: $$322 - 5\cdot  = .$$ Then divide 57 by 37, getting a quotient of $1$ and a remainder of $20$: $$ - 1\cdot = .$$ Divide 37 by 20, getting a quotient of $1$ and a remainder of $17$: $$-1\cdot = .$$ Divide $20$ by $17$, getting a quotient of 1 and a remainder of $3$: $$-1\cdot=.$$ Divide $17$ by $3$, getting a quotient of $5$ and a remainder of $2$: $$-5\cdot=.$$ Divide $3$ by $2$, getting a quotient of $1$ and a remainder of $1$: $$ -1\cdot=.$$ 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, put the expression found to be equal to $2$ in the line before it: \begin{align} -1\cdot & =  \\ {[}3{]}-1(-5\cdot) & =  \end{align} Simplify, getting linear combination of REMAINDERS: $$6-1 =1.$$ Now in place of the remainder $3$, put the expression found to be equal to it: $$6(-1)-1 = 1.$$ Simplify, getting linear combination of REMAINDERS: $$6-7 = 1.$$ Now in place of the remainder $17$, put the expression found to be equal to it: $$6 - 7(-1)=1.$$ Simplify, getting linear combination of REMAINDERS: $$13-7=1.$$ Now in place of the remainder $20$, put the expression found to be equal to it: $$13(-1)-7=1.$$ Simplify, getting linear combination of REMAINDERS: $$13-20=1.$$ Now in place of the remainder $37$, put the expression found to be equal to it: $$13-20(322-5)=1.$$ Simplify, getting linear combination of REMAINDERS: $$113-20=1.$$ Now in place of the remainder $57,$ put the expression found to be equal to it: $$113(-2)-20=1.$$ Simplify, getting linear combination of REMAINDERS: $$113-246=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.


There is an algorithm besides the extended Euclidean algorithm that can be used to solve

$$\tag 1 ax \equiv b \pmod{p} \quad \text{where } p \text{ is prime} \land p \nmid a \land p \nmid b$$

An outline for the algorithm's logic was given here.

Here is a Python program that calculates $$3789 x \equiv 1234 \pmod{7919}$$; it ends with

$$\tag {ANS} 3789 x \equiv 1234 \pmod{7919} \; \text{ iff } \; x \equiv 4498 \pmod{7919}$$

We take the output of the program and paste it into our Latex interpreter:

Multiply by $$2$$:

$$\quad 7578 x \equiv 2468 \pmod{7919}$$
$$\quad -341 x \equiv 2468 \pmod{7919}$$
$$\quad 341 x \equiv 5451 \pmod{7919}$$

Multiply by $$23$$:

$$\quad 7843 x \equiv 125373 \pmod{7919}$$
$$\quad -76 x \equiv 6588 \pmod{7919}$$
$$\quad 76 x \equiv 1331 \pmod{7919}$$

Multiply by $$104$$:

$$\quad 7904 x \equiv 138424 \pmod{7919}$$
$$\quad -15 x \equiv 3801 \pmod{7919}$$
$$\quad 15 x \equiv 4118 \pmod{7919}$$

Multiply by $$528$$:

$$\quad 7920 x \equiv 2174304 \pmod{7919}$$
$$\quad 1 x \equiv 4498 \pmod{7919}$$

Python Program

a = 3789
b = 1234
p = 7919

while 1:
q, r = divmod(p,a)
s_L = q * a
s_R = (q + 1) * a
M = q
left = True
if p - s_L > s_R - p:
M = q + 1
left = False
print()
print('Multiply by $$', M,'$$:',)
print()
print('$$\quad', M*a, 'x \equiv', M*b, '\pmod{7919}$$<br>')
if left:
a = M*a - p
b = M*b % p
print('$$\quad',a, 'x \equiv', b, '\pmod{7919}$$<br>')
a = -a
b = -b % p
print('$$\quad',a, 'x \equiv', b, '\pmod{7919}$$<br>')
else:
a = M*a - p
b = M*b % p
print('$$\quad',a, 'x \equiv', b, '\pmod{7919}$$<br>')
if a == 1:
break

raise SystemExit


This Python prints out a table of all the inverses; the output for both $$\text{mod } 41$$ and $$\text{mod } 210$$ is given

Python Program

def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
return -1 # modular inverse does not exist
else:
return x % m

while True:
print()
mod_n = input('modulus n: ')
if mod_n == '':
print()
print('...done')
break
mod_n = int(mod_n)
exclude_list = []
for num in range(1, mod_n):
if num in exclude_list:
continue
daInv = modinv(num, mod_n)
if daInv > 0:
print(num, daInv)
exclude_list.append(daInv)


*** OUTPUT ***

modulus n: 41
1 1
2 21
3 14
4 31
5 33
6 7
8 36
9 32
10 37
11 15
12 24
13 19
16 18
17 29
20 39
22 28
23 25
26 30
27 38
34 35
40 40

modulus n: 210
1 1
11 191
13 97
17 173
19 199
23 137
29 29
31 61
37 193
41 41
43 127
47 143
53 107
59 89
67 163
71 71
73 187
79 109
83 167
101 131
103 157
113 197
121 151
139 139
149 179
169 169
181 181
209 209

modulus n:

...done