> For the complete documentation index, see [llms.txt](https://calnix.gitbook.io/zk-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://calnix.gitbook.io/zk-notes/abstract-math/modular-arithmetic/modular-inverses.md).

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

```solidity
// 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.

{% hint style="info" %}
A naive method is to try all numbers from 1 to m. For every number x, check if \
**`(A * X) % M`** is 1.
{% endhint %}

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