Modular Inverse: Definition, Formula & Example

A modular inverse of an integer a modulo n is an integer x that satisfies:

ax ≡ 1 (mod n)

For example, the modular inverse of 3 modulo 7 is 5 because:

3 × 5 = 15

and:

15 ≡ 1 (mod 7)

since:

15 = 7 × 2 + 1

Therefore:

3⁻¹ ≡ 5 (mod 7)

A modular inverse does not always exist. The essential condition is:

GCF(a,n) = 1

So a must be coprime to the modulus n.

Modular inverses are important in modular arithmetic because they provide the modular equivalent of division and are used to solve congruences, work with residue classes, and support many number-theory algorithms.

What Is a Modular Inverse?

In ordinary arithmetic, the multiplicative inverse of a nonzero number a is:

1/a

because:

a × 1/a = 1

In modular arithmetic, we usually work with integers rather than fractions. The modular inverse of a is therefore an integer x such that the product leaves remainder 1 modulo n.

The defining condition is:

a × x ≡ 1 (mod n)

For example, modulo 11:

4 × 3 = 12

and:

12 mod 11 = 1

Therefore:

4⁻¹ ≡ 3 (mod 11)

The inverse is understood relative to a modulus. The integer 4 does not have one universal modular inverse; its inverse depends on the chosen modulus.

Modular Inverse Formula

The modular inverse problem is:

Find x such that ax ≡ 1 (mod n)

This congruence is equivalent to saying:

ax – 1

is divisible by n.

Therefore there is some integer k such that:

ax – 1 = kn

Rearrange:

ax + n(-k) = 1

This is a linear integer equation.

A solution exists exactly when:

GCF(a,n) = 1

because Bézout’s identity says that integers x and y satisfying:

ax + ny = 1

exist precisely when a and n are coprime.

When Does a Modular Inverse Exist?

An integer a has a modular inverse modulo n if and only if:

GCF(a,n) = 1

For example:

a = 3

n = 8

Since:

GCF(3,8) = 1

an inverse exists.

Test:

3 × 3 = 9

and:

9 ≡ 1 (mod 8)

Therefore:

3⁻¹ ≡ 3 (mod 8)

Now consider:

a = 4

n = 10

Since:

GCF(4,10) = 2

no modular inverse exists.

Why Coprimality Is Necessary

Suppose:

ax ≡ 1 (mod n)

Then:

ax – kn = 1

for some integer k.

Any common factor of a and n must divide:

ax

and:

kn

so it must divide their difference:

1

The only positive divisor of 1 is 1.

Therefore:

GCF(a,n) = 1

must hold.

This proves that coprimality is necessary for a modular inverse.

Example: Inverse of 2 Modulo 5

Find x such that:

2x ≡ 1 (mod 5)

Test residues:

2 × 1 = 2

2 × 2 = 4

2 × 3 = 6 ≡ 1 (mod 5)

Therefore:

2⁻¹ ≡ 3 (mod 5)

Check:

2 × 3 = 6

6 mod 5 = 1

Example: Inverse of 3 Modulo 7

Solve:

3x ≡ 1 (mod 7)

Test:

3 × 1 ≡ 3

3 × 2 ≡ 6

3 × 3 ≡ 2

3 × 4 ≡ 5

3 × 5 ≡ 1

Therefore:

3⁻¹ ≡ 5 (mod 7)

Example: Inverse of 5 Modulo 12

Check:

GCF(5,12) = 1

so an inverse exists.

Test:

5 × 5 = 25

and:

25 = 12 × 2 + 1

Therefore:

5⁻¹ ≡ 5 (mod 12)

In this case, 5 is its own inverse modulo 12.

Self-Inverse Residues

A residue a is self-inverse modulo n when:

a² ≡ 1 (mod n)

For example, modulo 8:

3² = 9 ≡ 1

so:

3⁻¹ ≡ 3 (mod 8)

Likewise:

5² = 25 ≡ 1 (mod 8)

and:

7² = 49 ≡ 1 (mod 8)

Thus 3, 5, and 7 are all self-inverse modulo 8.

Method 1: Find an Inverse by Testing Residues

For a small modulus, directly test:

x = 1,2,3,…,n-1

until:

ax mod n = 1

Find the inverse of:

7 modulo 10

Since:

GCF(7,10) = 1

an inverse exists.

Test:

7 × 1 = 7

7 × 2 = 14 ≡ 4

7 × 3 = 21 ≡ 1

Therefore:

7⁻¹ ≡ 3 (mod 10)

This method is easy for small moduli but inefficient for large ones.

Method 2: Use the Extended Euclidean Algorithm

For larger values, the extended Euclidean algorithm is usually more efficient.

Suppose we want:

17⁻¹ mod 43

We need integers x and y satisfying:

17x + 43y = 1

First apply the Euclidean algorithm:

43 = 17 × 2 + 9

17 = 9 × 1 + 8

9 = 8 × 1 + 1

The GCD is 1, so an inverse exists.

Now work backward.

From:

1 = 9 – 8

and:

8 = 17 – 9

we get:

1 = 9 – (17 – 9)

= 2 × 9 – 17

Since:

9 = 43 – 2 × 17

substitute:

1 = 2(43 – 2 × 17) – 17

= 2 × 43 – 5 × 17

Therefore:

-5 × 17 ≡ 1 (mod 43)

So:

x ≡ -5 (mod 43)

Convert to the canonical positive residue:

-5 + 43 = 38

Therefore:

17⁻¹ ≡ 38 (mod 43)

Check:

17 × 38 = 646

and:

646 = 43 × 15 + 1

Why the Extended Euclidean Algorithm Works

If:

GCF(a,n) = 1

Bézout’s identity guarantees integers x and y such that:

ax + ny = 1

Reduce both sides modulo n.

Since:

ny ≡ 0 (mod n)

we obtain:

ax ≡ 1 (mod n)

Therefore the coefficient x of a is a modular inverse.

If x is negative, reduce it modulo n to obtain the standard residue between:

0 and n – 1

Example: Inverse of 11 Modulo 26

First check:

GCF(11,26) = 1

Use Euclidean division:

26 = 11 × 2 + 4

11 = 4 × 2 + 3

4 = 3 × 1 + 1

Work backward:

1 = 4 – 3

3 = 11 – 4 × 2

So:

1 = 4 – (11 – 2 × 4)

= 3 × 4 – 11

Now:

4 = 26 – 2 × 11

Therefore:

1 = 3(26 – 2 × 11) – 11

= 3 × 26 – 7 × 11

Thus:

-7 × 11 ≡ 1 (mod 26)

So:

-7 ≡ 19 (mod 26)

Therefore:

11⁻¹ ≡ 19 (mod 26)

Check:

11 × 19 = 209

209 = 26 × 8 + 1

Example Where No Inverse Exists

Find the inverse of:

6 modulo 15

Calculate:

GCF(6,15) = 3

Since:

3 ≠ 1

there is no modular inverse.

To see why directly, products of 6 modulo 15 include:

6 × 1 ≡ 6

6 × 2 ≡ 12

6 × 3 ≡ 3

6 × 4 ≡ 9

6 × 5 ≡ 0

Then the pattern repeats.

The residue 1 never appears.

Therefore:

6 has no inverse modulo 15

Modular Inverse and Prime Moduli

If p is a prime number, every nonzero residue modulo p has a modular inverse.

Why?

For:

1 ≤ a ≤ p – 1

a prime p has no positive common factor with a other than 1.

Therefore:

GCF(a,p) = 1

So every nonzero residue is invertible.

For modulus 7:

1,2,3,4,5,6

all have inverses.

Examples:

1⁻¹ ≡ 1

2⁻¹ ≡ 4

3⁻¹ ≡ 5

4⁻¹ ≡ 2

5⁻¹ ≡ 3

6⁻¹ ≡ 6

all modulo 7.

Inverse Pairs Modulo 7

The inverse relationships can be checked:

1 × 1 = 1

2 × 4 = 8 ≡ 1

3 × 5 = 15 ≡ 1

6 × 6 = 36 ≡ 1

Thus inverse pairs need not be different. Some residues are their own inverses.

Solving ax ≡ b (mod n)

A modular inverse is especially useful for solving linear congruences.

Suppose:

ax ≡ b (mod n)

and:

GCF(a,n) = 1

Multiply both sides by:

a⁻¹

Then:

a⁻¹ax ≡ a⁻¹b (mod n)

Since:

a⁻¹a ≡ 1

we obtain:

x ≡ a⁻¹b (mod n)

This is the modular version of dividing both sides by a.

Example: Solve 3x ≡ 4 (mod 7)

We know:

3⁻¹ ≡ 5 (mod 7)

Multiply both sides by 5:

x ≡ 5 × 4 (mod 7)

x ≡ 20 (mod 7)

Reduce:

20 mod 7 = 6

Therefore:

x ≡ 6 (mod 7)

Check:

3 × 6 = 18

18 mod 7 = 4

Example: Solve 5x ≡ 7 (mod 12)

First find the inverse of 5 modulo 12.

Since:

5 × 5 = 25 ≡ 1 (mod 12)

we have:

5⁻¹ ≡ 5

Multiply:

x ≡ 5 × 7 (mod 12)

x ≡ 35 (mod 12)

Reduce:

35 mod 12 = 11

Therefore:

x ≡ 11 (mod 12)

Check:

5 × 11 = 55

55 mod 12 = 7

When a Linear Congruence Has Multiple Solutions

Consider:

6x ≡ 9 (mod 15)

Here:

GCF(6,15) = 3

so 6 has no inverse modulo 15.

But the congruence may still have solutions because:

3 divides 9

Divide the equation and modulus by 3 carefully:

2x ≡ 3 (mod 5)

Now:

2⁻¹ ≡ 3 (mod 5)

so:

x ≡ 3 × 3

≡ 9

≡ 4 (mod 5)

Therefore the original solutions modulo 15 are:

x ≡ 4, 9, 14 (mod 15)

This shows why lack of a modular inverse does not always mean a linear congruence has no solutions. It means ordinary inverse-based isolation cannot be applied directly.

Modular Inverse and GCF

The greatest common factor is the fastest existence test:

Inverse exists ⇔ GCF(a,n) = 1

For example:

GCF(14,25) = 1

so an inverse exists.

But:

GCF(14,21) = 7

so no inverse exists modulo 21.

Coprimality is therefore not a side condition—it is the exact criterion for invertibility.

Modular Inverse and Multiples

The mapped multiples relationship appears in the defining congruence.

If:

ax ≡ 1 (mod n)

then:

ax – 1

must be a multiple of n.

For example:

4 × 3 – 1 = 11

and:

11

is a multiple of 11.

Therefore:

4 × 3 ≡ 1 (mod 11)

So the inverse condition can always be interpreted as the product being exactly one more than a multiple of the modulus.

Modular Inverse and Remainders

A modular inverse condition:

ax ≡ 1 (mod n)

can also be written:

ax mod n = 1

For example:

7 × 8 = 56

and:

56 mod 11 = 1

Therefore:

7⁻¹ ≡ 8 (mod 11)

The inverse can be verified with one remainder calculation.

Modular Inverse and Prime Factorization

Prime factorization can quickly reveal whether two integers are coprime.

Consider:

a = 14

n = 25

Factor:

14 = 2 × 7

25 = 5²

They share no prime factor.

Therefore:

GCF(14,25) = 1

and a modular inverse exists.

Now compare:

a = 14

n = 35

Since:

14 = 2 × 7

35 = 5 × 7

they share 7.

Therefore no inverse of 14 exists modulo 35.

Modular Inverse and Negative Residues

A modular inverse may first appear as a negative integer.

For example, the extended Euclidean algorithm may produce:

-3a + 2n = 1

Then:

-3a ≡ 1 (mod n)

So:

a⁻¹ ≡ -3 (mod n)

The standard nonnegative representative is:

n – 3

assuming n > 3.

Both residues represent the same modular inverse class.

Example: Negative Inverse Representation

Suppose:

8 × (-3) = -24

Modulo 25:

-24 ≡ 1 (mod 25)

because:

-24 + 25 = 1

Therefore:

8⁻¹ ≡ -3 (mod 25)

Equivalently:

8⁻¹ ≡ 22 (mod 25)

Check:

8 × 22 = 176

176 mod 25 = 1

Uniqueness of the Modular Inverse

If a modular inverse exists, it is unique modulo n.

Suppose:

ax ≡ 1 (mod n)

and:

ay ≡ 1 (mod n)

Subtract:

a(x-y) ≡ 0 (mod n)

Since:

GCF(a,n) = 1

a is invertible, so:

x-y ≡ 0 (mod n)

Therefore:

x ≡ y (mod n)

There may be infinitely many integer representatives:

x, x+n, x+2n, …

but they all belong to one residue class.

Inverse of 1

For every positive modulus n > 1:

1 × 1 ≡ 1 (mod n)

Therefore:

1⁻¹ ≡ 1 (mod n)

The residue 1 is always self-inverse.

Inverse of -1

Similarly:

(-1)(-1) = 1

Therefore:

(-1)⁻¹ ≡ -1 (mod n)

In the canonical residue range:

-1 ≡ n – 1 (mod n)

So:

(n-1)⁻¹ ≡ n-1 (mod n)

Modular Inverse and Powers

If a is invertible modulo n, then powers of a are also invertible.

If:

a⁻¹ ≡ b (mod n)

then:

(a^k)⁻¹ ≡ b^k (mod n)

because:

a^k b^k = (ab)^k

and:

ab ≡ 1

so:

(ab)^k ≡ 1

This can simplify inverse calculations involving large powers.

Example: Inverse of a Power

Suppose modulo 7:

3⁻¹ ≡ 5

Then:

(3²)⁻¹ ≡ 5²

≡ 25

≡ 4 (mod 7)

Since:

3² = 9 ≡ 2 (mod 7)

this predicts:

2⁻¹ ≡ 4 (mod 7)

Check:

2 × 4 = 8 ≡ 1

Correct.

Modular Inverse and Division

Ordinary division:

a/b

is not automatically meaningful modulo n.

If b has an inverse, modular division can be interpreted as multiplication by that inverse:

a / b ≡ a × b⁻¹ (mod n)

For example, modulo 7:

4/3

means:

4 × 3⁻¹

Since:

3⁻¹ ≡ 5

we get:

4 × 5 = 20

20 mod 7 = 6

Therefore:

4/3 ≡ 6 (mod 7)

Why Fractions Are Different in Modular Arithmetic

An ordinary fraction such as:

3/4

is a rational number.

In modular arithmetic, the symbol /4 can only be interpreted through an inverse if 4 is invertible under the selected modulus.

For example, modulo 7:

GCF(4,7) = 1

so:

4⁻¹ ≡ 2

and modular division by 4 is possible.

Modulo 8:

GCF(4,8) = 4

so 4 has no inverse.

The ordinary mixed numbers framework therefore should not be substituted directly for modular division.

Modular Inverse and Nth Roots

The mapped nth roots topic is mathematically different from modular inversion.

A modular inverse solves:

ax ≡ 1 (mod n)

An nth root solves a power relationship such as:

x^k = a

In advanced modular arithmetic, one may ask whether:

x^k ≡ a (mod n)

has a solution, but finding such a modular root is not the same operation as finding:

a⁻¹ mod n

The inverse specifically concerns multiplication to residue 1.

Modular Inverse and Mass-to-Volume Conversion

The mapped milligrams to milliliters page uses ordinary real-number division through density:

Volume = Mass / Density

That kind of division is not modular inversion.

A modular inverse exists within a residue system and depends on coprimality with a modulus.

The two calculations therefore use different mathematical domains despite both involving an idea analogous to division.

Small Inverse Table Modulo 11

Every nonzero residue modulo 11 is invertible because 11 is prime.

For example:

5 × 9 = 45

and:

45 mod 11 = 1

so 9 is the inverse of 5 modulo 11.

Common Modular Inverse Mistake: Skipping the GCF Check

Before searching for an inverse, check:

GCF(a,n)

If the result is greater than 1, no inverse exists.

For example:

8 modulo 12

has:

GCF(8,12) = 4

Therefore searching through all residues is unnecessary:

8 has no modular inverse modulo 12

Common Mistake: Using 1/a as the Modular Inverse

The modular inverse is normally an integer residue, not the ordinary fraction:

1/a

For example, modulo 7:

3⁻¹ ≡ 5

not:

1/3

because:

3 × 5 ≡ 1 (mod 7)

The symbol 3⁻¹ must be interpreted according to the modular context.

Common Mistake: Forgetting the Modulus

Saying:

“The inverse of 3 is 5”

is incomplete in modular arithmetic.

The correct statement is:

The inverse of 3 modulo 7 is 5.

Modulo 8:

3⁻¹ ≡ 3

Modulo 10:

3⁻¹ ≡ 7

The modulus changes the answer.

Common Mistake: Accepting a Product With the Wrong Remainder

Suppose someone claims:

4⁻¹ ≡ 2 (mod 7)

Check:

4 × 2 = 8

and:

8 mod 7 = 1

So the claim is correct.

But modulo 9:

4 × 2 = 8

and:

8 mod 9 = 8

Therefore 2 is not the inverse of 4 modulo 9.

Always verify:

ax mod n = 1

Common Mistake: Dividing a Congruence Without an Inverse

From:

4x ≡ 8 (mod 12)

you cannot simply divide everything by 4 and keep modulus 12.

Since:

GCF(4,12) = 4

4 is not invertible modulo 12.

The original congruence has several solutions.

Careless cancellation can discard valid residue classes.

How to Check a Modular Inverse

Suppose:

19⁻¹ ≡ 4 (mod 25)

Multiply:

19 × 4 = 76

Now divide by 25:

76 = 25 × 3 + 1

Therefore:

76 mod 25 = 1

So:

4 is indeed the modular inverse of 19 modulo 25

This direct multiplication check is usually the fastest verification.

Frequently Asked Questions

What is a modular inverse?

The modular inverse of a modulo n is an integer x satisfying:

ax ≡ 1 (mod n)

When does a modular inverse exist?

Exactly when:

GCF(a,n) = 1

What is the inverse of 3 modulo 7?

5

because:

3 × 5 = 15 ≡ 1 (mod 7)

What is the inverse of 2 modulo 5?

3

because:

2 × 3 = 6 ≡ 1 (mod 5)

What is the inverse of 4 modulo 11?

3

because:

4 × 3 = 12 ≡ 1 (mod 11)

Does 6 have an inverse modulo 15?

No.

GCF(6,15) = 3

so no modular inverse exists.

How do you find a modular inverse for large numbers?

Use the extended Euclidean algorithm to find integers x and y satisfying:

ax + ny = 1

The coefficient x is the inverse modulo n.

Is a modular inverse unique?

Yes, modulo n. Different integer representatives differ by multiples of n.

Can a modular inverse be negative?

A calculation may produce a negative representative. Add or subtract multiples of the modulus to obtain the standard nonnegative residue.

Why are modular inverses useful?

They allow modular division, solve linear congruences, and support many algorithms in number theory and cryptography.

Final Example

Find the modular inverse of:

23 modulo 100

First check:

GCF(23,100) = 1

so the inverse exists.

Use the Euclidean algorithm:

100 = 23 × 4 + 8

23 = 8 × 2 + 7

8 = 7 × 1 + 1

Work backward:

1 = 8 – 7

Since:

7 = 23 – 2 × 8

we get:

1 = 8 – (23 – 2 × 8)

= 3 × 8 – 23

Now:

8 = 100 – 4 × 23

Substitute:

1 = 3(100 – 4 × 23) – 23

= 3 × 100 – 13 × 23

Therefore:

-13 × 23 ≡ 1 (mod 100)

So:

23⁻¹ ≡ -13 (mod 100)

Convert to the canonical residue:

-13 + 100 = 87

Therefore:

23⁻¹ ≡ 87 (mod 100)

Check:

23 × 87 = 2,001

and:

2,001 = 100 × 20 + 1

The remainder is exactly 1.

The central modular inverse rule is:

ax ≡ 1 (mod n)

with the existence condition:

GCF(a,n) = 1

When the numbers are small, testing residues can find the inverse quickly. For larger values, the extended Euclidean algorithm provides a systematic and efficient method.