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

**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 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__

__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 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.