# Multiplicative Inverse Modulo Calculator

Table of contents

What is the multiplicative inverse in modular arithmetic?When does the multiplicative modular inverse exist?How to use this multiplicative inverse modulo calculator?Finding the multiplicative modulo inverse with Bézout's identityFAQsThe **multiplicative inverse modulo calculator** is of immeasurable value whenever you need to quickly find the multiplicative inverse modulo for some `m`

, be it for a math assignment, a programming project, or any other scientific endeavor you deal with.

In the brief article below, we'll explain how to find the multiplicative inverse modulo — both by **Bézout's identity** and by **brute force** (depending on how much you care about mathematical subtlety). And to spare you useless work, we'll also tell you **how to check if the multiplicative modular inverse exists** in the first place.

🙋 We assume you're already familiar with the **modulo operation in math**. If this is not the case (or you feel you need a refresher), check out Omni's modulo calculator.

## What is the multiplicative inverse in modular arithmetic?

Let `a`

and `x`

be integers. We say that `x`

is the **modular multiplicative inverse** of `a`

(modulo `m`

) if

`a × x ≡ 1 (mod m)`

.

That is, when `a × x`

and `1`

are congruent modulo `m`

, i.e., when `(a × x) mod m = 1`

.

In even simpler words, the **remainder** from the division of `a × x`

by `m`

must equal `1`

.

❗ It may happen that **the multiplicative inverse modulo does not exist!** For instance, the multiplicative modular inverse of `3`

modulo `6`

does not exist: you may check yourself that for every number `x ∊ {1, 2, 3, 4, 5}`

, the result of `(3 × x) mod 6`

is different from `1`

.

## When does the multiplicative modular inverse exist?

The modular multiplicative inverse of ** a modulo m** exists if and only if

`a`

and `m`

are *coprime*(a.k.a.

*relatively prime*), i.e., if their greatest common factor equals one:

`gcd(a,m) = 1`

.If `m`

is prime, then the multiplicative modular inverse modulo `m`

exists for every non-zero integer `a`

that is not a multiple of `m`

.

🙋 To quickly determine the greatest common divisor of two integers, use Omni's **GCF calculator**.

As you can see, it's easy to verify if the multiplicative modular inverse exists, but **computing it is quite a different story**. The fastest method is to use our multiplicative inverse modulo calculator!

## How to use this multiplicative inverse modulo calculator?

Using this multiplicative inverse modulo calculator is really simple:

- Enter a positive integer
`m`

: the number with which we calculate the**modulo**. - Enter an integer
`a`

: the number whose**multiplicative inverse modulo**`m`

we look for. - Our calculator
**returns the answer immediately**. A short explanation is provided as well.

Are you curious how our tool can solve this modulo problem so quickly? In the next section, we explain the method implemented in our calculator.

## Finding the multiplicative modulo inverse with Bézout's identity

Let `a`

and `m`

be integers. **Bézout's identity** says that there exist two integers `x`

and `y`

such that:

`a×x + m×y = gcd(a, m)`

.

That is, we can represent `gcd(a, m)`

as a **linear combination of a and m** with coefficients

`x`

and `y`

.It turns out we can use this representation to find the multiplicative inverse of `a`

modulo `m`

. Recall that `a`

and `m`

must be coprime, so `gcd(a,m) = 1`

— Bézout's identity says that there exist integers `x`

and `y`

such that:

`a×x + m×y = 1 `

Next, we **apply the mod m operation** to both sides:

`(a×x + m×y) mod m = 1 mod m`

`⇒ a×x + m×y ≡ 1 (mod m)`

The second form is just short-hand for the first form — they mean the same. The left-hand side simplifies to `a×x`

because `m×y`

is divisible by `m`

. That is, we get:

`a×x ≡ 1 (mod m)`

This means that **we have the solution** right in front of our eyes: `x`

is the multiplicative inverse of `a`

modulo `m`

!

🔎 Finding `x`

and `y`

for Bézout's identity is not trivial. The best method is to use the **.**

### How do I find the multiplicative modulo inverse by hand?

To find the multiplicative inverse of `a`

modulo `m`

by brute force:

- Take
**any**number`x`

from the set`{0, 1, ..., m − 1}`

and calculate`a × x`

. - Find the
**remainder**from the division of`a × x`

by`m`

. - If this remainder is
`1`

,**you've found the solution**. - If not, repeat Steps 1–3 for
**a different number**.`x`

- If all numbers from
`{0, 1, ..., m − 1}`

fail, then the multiplicative inverse of`a`

modulo`m`

**does not exists**.

### Is the multiplicative inverse modulo m unique?

**No** — if `x`

is a multiplicative inverse of `a`

modulo `m`

, then **every number** of the form `x + (k×m)`

(where `k`

is an integer) is a multiplicative inverse of `a`

modulo `m`

as well. However, **the solution is unique** in the set `{1, ..., m − 1}`

.

### Does 142 have a multiplicative inverse modulo 76?

**No**, 142 does not have a multiplicative inverse modulo 76. The reason is that these numbers are not **relatively prime**, i.e., their greatest common factor exceeds `1`

. Indeed, we immediately see that both `142`

and `76`

are both divisible by `2`

.

### What numbers have multiplicative inverses modulo 11?

Every integer that is **not a multiple of 11** has a multiplicative inverse modulo

`11`

. This is because `11`

is a prime number, and so it is not coprime only with its multiplicities. Calculating the multiplicative inverses may be tiresome, so don't hesitate to use an online multiplicative inverse modulo calculator.