Modular inverses

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

• 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)

// X is the mod inverse of A
(A * X) ≡ 1 (mod M)
(A * X) mod M = 1

// X lies in range {1, 2, … M-1}, within the range of M
// X cannot be 0 as A*0 (mod M) will never be 1

// The inverse exists only iff A and M are relatively prime (i.e. if gcd(A, M) = 1)

Example

(A * X) mod M = 1
(3 * X) mod 11 = 1

Since (4*3) mod 11 = 1, 4 is modulo inverse of 3(mod 11).

• One might think 15 is valid as “(15*3) mod 11” is also 1,

• but 15 is not in range {1, 2, … 10}, so not valid.

A naive method is to try all numbers from 1 to m. For every number x, check if (A * X) % M is 1.

The Euclidean Algorithm

• Recall that the Greatest Common Divisor (GCD) of two integers A and B is the largest integer that divides both A and B.

• The Euclidean Algorithm is a technique for quickly finding the GCD of two integers.