Modular Inverse Calculator (Extended Euclidean Algorithm)

Modular Inverse Calculator (Extended Euclidean Algorithm) | Online Free Tool | Elysia Tools

Tool usage guide

Learn when to use this tool, what it supports, and how real users apply it.

Key facts

Category: Math & Numbers
Input types: text, select
Output type: text
Sample coverage: 4
API ready: Yes

Overview

The Modular Inverse Calculator computes the multiplicative inverse a⁻¹ mod m using the Extended Euclidean Algorithm, supporting standard integers as well as large RSA-scale values up to 10⁵¹². It automatically derives Bézout coefficients, confirms whether gcd(a, m) equals 1, validates the identity a × a⁻¹ ≡ 1 (mod m), and optionally displays the full step-by-step division and reduction table.

When to use

Generating or verifying private key exponents in RSA key generation routines.
Solving linear congruences, Diophantine equations, or finding decryption keys in classical affine ciphers.
Debugging number theory assignments and modular arithmetic proofs that require step-by-step Bézout identity tracking.

How it works

1Enter the value to invert (a) and the modulus (m, where m ≥ 2); negative values for a are automatically reduced modulo m.
2Select your preferred output style: a concise result with verification or a full Extended Euclidean step-by-step table.
3The algorithm calculates gcd(a, m) and computes Bézout coefficients s and t such that a·s + m·t = gcd(a, m).
4If gcd(a, m) = 1, the calculator outputs the normalized modular inverse along with the identity verification a × a⁻¹ ≡ 1 (mod m); otherwise, it reports that no inverse exists.

Use cases

Cryptographic key pair calculation where the private exponent d satisfies d ≡ e⁻¹ (mod φ(n)).
Finding decryption multipliers for classical modular ciphers such as the affine cipher.
Academic problem-solving in discrete mathematics and computational number theory.

Examples

1. RSA Private Key Generation

Cryptography Student

Background

Working through textbook RSA key generation with public exponent e = 17 and totient φ(n) = 3120.

Problem

Calculate the private decryption exponent d = 17⁻¹ mod 3120 with step-by-step derivation.

How to use

Set Value a to 17, Modulus m to 3120, and choose 'Show extended Euclid steps' under Output style.

a = 17, m = 3120, style = steps

Outcome

Receives the step table showing gcd(17, 3120) = 1, Bézout identity 17 × (-367) + 3120 × 2 = 1, and the resulting modular inverse 2753 verified by 17 × 2753 = 46801 = 15 × 3120 + 1.

2. Affine Cipher Decryption Key

Security Analyst

Background

Decrypting ciphertext encoded with an affine cipher using multiplicative key a = 7 over modulus m = 26.

Problem

Find the multiplicative decryption inverse 7⁻¹ mod 26.

How to use

Input 7 for Value a, 26 for Modulus m, and select 'Result and verification' for Output style.

FAQ

When does a modular inverse exist?

A modular inverse a⁻¹ mod m exists if and only if a and m are coprime, meaning gcd(a, m) = 1.

How are negative values for a handled?

Negative values of a are automatically reduced modulo m to their positive canonical equivalent before computing the inverse.

What is the maximum supported number size?

The calculator supports large integers up to RSA dimensions (10⁵¹²).

What are Bézout coefficients in the output?

They are the integers s and t satisfying Bézout's identity, a·s + m·t = gcd(a, m), where s reduced modulo m yields the modular inverse.

What does the verification step check?

It multiplies a by the computed inverse a⁻¹ and confirms that the product modulo m equals 1.

a = 7, m = 26, style = result

Run this tool

Examples that match this tool

Continue with connected tools and hubs

Learn when to use this tool, what it supports, and how real users apply it.

Key facts

Overview

When to use

How it works

Use cases

Examples

1. RSA Private Key Generation

2. Affine Cipher Decryption Key

FAQ

Web Image Processing Python Samples

Android Image Processing Java Samples

Android Image Processing Kotlin Samples

Web Image Processing Rust Samples

Boolean Algebra Simplifier (Karnaugh Map)

Dilution Ratio Converter (1:X ↔ 1/X ↔ %)

Extended Euclidean Algorithm (ax + by = gcd(a, b))

Modular Arithmetic Calculator (Add / Subtract / Multiply / Inverse / Power)