What is an inverse?
Recall that a number multiplied by its inverse equals 1. From basic arithmetic we know that

the inverse of a number
, e.g., the inverse ofA
is1/A
sinceA * 1/A = 1
5
is1/5
; 
all real numbers other than 0 have an inverse; and

multiplying a number by the inverse of
e.g.,A
is equivalent to dividing byA
,10/5
is the same as10* 1/5
.
What is a modular inverse?
In modular arithmetic, we do not have a division operation. We do, however, have modular inverses.

The modular inverse of
A (mod C)
isA^1
. 
(A * A^1) ≡ 1 (mod C)
or, equivalently,(A * A^1) mod C = 1
. 
Only the numbers coprime to C—numbers that share no prime factors with C—have a modular inverse:
mod C
.
How to find a modular inverse
A naive method of finding a modular inverse for A (mod C)
is below:
Step 1. Calculate A * B mod C
for B
values 0
through C1
.
Step 2. The modular inverse of A mod C
is the B
value that makes A * B mod C = 1
.
Note that the term B mod C
can only have an integer value 0
through C1
, so testing larger values for B
is redundant.
Example: A=3 C=7
Step 1. Calculate A * B mod C
for B
values 0
through C1
3 * 0 ≡ 0 (mod 7)
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7)
< Found inverse!
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)
Step 2. The modular inverse of A mod C
is the B
value that makes A * B mod C = 1
.
5
is the modular inverse of 3 mod 7
since 5*3 mod 7 = 1
.
Simple!
Let's do one more example where we don't find an inverse.
Example: A=2 C=6
Step 1. Calculate A * B mod C
for B
values 0
through C1
.
2 * 0 ≡ 0 (mod 6)
2 * 1 ≡ 2 (mod 6)
2 * 2 ≡ 4 (mod 6)
2 * 3 ≡ 6 ≡ 0 (mod 6)
2 * 4 ≡ 8 ≡ 2 (mod 6)
2 * 5 ≡ 10 ≡ 4 (mod 6)
Step 2. The modular inverse of A mod C
is the B
value that makes A * B mod C = 1
.
No value of B
makes A * B mod C = 1
. Therefore, A
has no modular inverse, mod 6
. This is because 2
is not coprime to 6
; they share the prime factor 2
.
This method seems slow ...
There is a much faster method for finding the inverse of A (mod C)
that we will discuss in the articles on the Extended Euclidean Algorithm. First, let's do some exercises!