✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · SCI-MAT-002-075

Modular Inverses

A modular inverse of an integer a modulo n is an integer x whose product with a is congruent to 1 modulo n. Such an inverse exists exactly when a and n are relatively prime.

a x ≡ 1 (mod n) ⇔ gcd(a, n) = 1 for an inverse to exist

Explanation

In ordinary arithmetic, the multiplicative inverse of a nonzero number a is 1/a. In modular arithmetic, the multiplicative inverse of a modulo n is an integer x satisfying ax ≡ 1 (mod n). A modular inverse exists if and only if the greatest common divisor of a and n is 1. When the inverse exists, it is unique modulo n. The extended Euclidean algorithm is a standard method for finding it. For example, the inverse of 3 modulo 7 is 5 because 3 × 5 = 15 ≡ 1 (mod 7). Not every integer has a modular inverse: 2 has no inverse modulo 6 because gcd(2, 6) = 2. Modular inverses are essential for solving modular equations and performing division-like operations in modular systems.

Variables

A

The integer whose modular inverse is required.

X

A modular inverse of a modulo n.

N

The positive modulus.

Gcd(a, n)

The greatest common divisor of a and n.

Example or application

Problem

Find the multiplicative inverse of 4 modulo 9.

Solution

We need an integer x such that 4x ≡ 1 (mod 9). Testing x = 7 gives 4 × 7 = 28 = 3 × 9 + 1. Therefore, 4 × 7 ≡ 1 (mod 9).

Answer

The inverse of 4 modulo 9 is 7.

Text

The multiplicative inverse allows a factor to be cancelled from a congruence only when that factor is relatively prime to the modulus. Modular division is therefore not always possible.

Key Points

  • A modular inverse satisfies ax ≡ 1 (mod n).

  • An inverse exists exactly when gcd(a, n) = 1.

  • A modular inverse is unique modulo n when it exists.

  • The extended Euclidean algorithm can calculate modular inverses.

  • Modular division requires multiplication by an existing inverse.

  • An integer may have no inverse for a particular modulus.

Applications

  • Solving linear congruences.

  • RSA cryptographic calculations.

  • Finite-field arithmetic.

  • Modular division in computational mathematics.

  • Cryptographic key generation and related algorithms.

Learning Outcomes

  • Define a modular multiplicative inverse.

  • Determine whether an inverse exists using the greatest common divisor.

  • Find simple modular inverses.

  • Explain the role of the extended Euclidean algorithm.

Practice Questions

  • Find the inverse of 3 modulo 11.

  • Determine whether 6 has an inverse modulo 15.

  • Find the inverse of 7 modulo 10.

  • Explain why 2 has no inverse modulo 8.

  • Use the extended Euclidean algorithm to find the inverse of 17 modulo 43.

Related Concepts

  • Greatest Common Divisor

  • Extended Euclidean Algorithm

  • Linear Congruences

  • Modular Multiplication

  • Euler's Theorem

Common Mistakes

  • Assuming every nonzero integer has a modular inverse.

  • Checking whether a is nonzero instead of checking gcd(a, n) = 1.

  • Confusing an ordinary reciprocal with a modular inverse.

  • Dividing both sides of a congruence without verifying that the inverse exists.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Kenneth H. Rosen, Elementary Number Theory and Its Applications
  • David M. Burton, Elementary Number Theory

Suggest a correction or source · More in Arithmetic & Number Theory