Modular Inverse and Extended Euclidean Calculator

Find gcd, Bézout coefficients, and modular inverse using the extended Euclidean algorithm.

Number TheoryCryptographyComputer Science Math

Calculate

a
modulus m
Please enter valid values.

What this calculator teaches

The extended Euclidean algorithm finds integers x and y such that ax + my = gcd(a,m). When gcd(a,m)=1, x is the modular inverse of a modulo m.

This is essential for modular arithmetic, RSA cryptography, coding theory, and competitive programming.

Formula & Symbols

ConceptFormulaMeaning
Bézout identityax + my = gcd(a,m)Extended Euclidean result.
Modular inversea^{-1} mod mA number x such that ax ≡ 1 (mod m).
Existence conditiongcd(a,m)=1Inverse exists only when a and m are coprime.

Step-by-Step Examples

Example 1
Inverse of 17 mod 43
  • Use Euclidean algorithm to find gcd(17,43).
  • Because gcd=1, an inverse exists.
  • Extended steps give 17·38 + 43·(-15)=1.
✓ 17⁻¹ mod 43 = 38.

Where students use this

🎓
High school and college
Use the tool to check homework and understand each step.
📊
Data and modeling
Connect formulas to tables, graphs, and real values.
🧪
Science and engineering
Use math results inside physics, chemistry, and engineering problems.
💻
Computer science
Apply the same logic to algorithms, systems, and numerical work.

Common Mistakes to Avoid

⚠️
Assuming inverse always exists

A modular inverse exists only when gcd(a,m)=1.

⚠️
Forgetting positive representative

If x is negative, add m until it is between 0 and m−1.

⚠️
Using division in modular arithmetic carelessly

Division modulo m means multiplying by a modular inverse, when it exists.

Frequently Asked Questions

What is a modular inverse? ▾
It is a number that multiplies with a to give remainder 1 modulo m.
When does the inverse exist? ▾
Only when a and m are coprime.
What is gcd? ▾
The greatest common divisor is the largest positive integer dividing both numbers.
Why is this used in cryptography? ▾
Public-key systems such as RSA rely heavily on modular inverses.

Related Math Calculators

🔢 Modular Arithmetic Calculator🔢 Prime Number Checker🔢 Prime Factorization Calculator🔢 Binary Converter

Formula Explorer connections

Interpretation: This formula uses integer divisibility, modular arithmetic, finite fields or coding relationships. Assumption: Inputs are usually integers with specific modulus or coprimality requirements. Cryptographic examples are educational and not a substitute for vetted security libraries.

Parity Bit Calculator →Prime Factorization Calculator – Factor Any Number →Prime Number Checker – Is This Number Prime? →Math Formula Explorer →