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

The inverse of of a number A is 1/A since A * 1/A = 1
e.g. the inverse of 5 is 1/5 
All real numbers other than 0 have an inverse

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

The modular inverse of A (mod C) is A^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:
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 next articles on the Extended Euclidean Algorithm. First, let's do some exercises!
Share a tip
Thank the author
Have something that's not a tip or thanks about this content?
This discussion area is not meant for answering homework questions.