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 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; and

  • 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. We do, however, 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 Cnumbers that share no prime factors with Chave 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 C-1.

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 C-1, 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 C-1

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 C-1.

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!