Modular Inverse Finder

Calculate modular multiplicative inverses using the Extended Euclidean Algorithm

Modular Inverse Finder

Find the modular multiplicative inverse using the Extended Euclidean Algorithm. Calculate a⁻¹ mod m where a × a⁻¹ ≡ 1 (mod m).

Value (a)

The number to find the inverse of

Modulus (m)

The modulus (must be coprime with a)

Quick Examples

Understanding Modular Inverse

The modular multiplicative inverse is a fundamental concept in number theory and cryptography. Given integers a and m, the modular inverse of a modulo m is an integer x such that:

a × x ≡ 1 (mod m)

Existence Conditions

A modular inverse exists if and only if gcd(a, m) = 1. When this condition is met, we say that a and m are coprime or relatively prime.

Applications

Cryptography

RSA encryption key generation
Digital signature algorithms
Elliptic curve cryptography
Key exchange protocols

Mathematics

Solving linear congruences
Number theory research
Abstract algebra
Computational mathematics

Extended Euclidean Algorithm

The Extended Euclidean Algorithm is the most efficient method for finding modular inverses. It computes the GCD and finds Bézout coefficients that express the GCD as a linear combination.