# 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 \
\&#xNAN;**`(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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://calnix.gitbook.io/zk-notes/abstract-math/modular-arithmetic/modular-inverses.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.