Multiplicative Inverse Modulo Calculator
Find the least nonnegative integer x that satisfies a × x ≡ 1 (mod m), verify whether an inverse exists, and inspect the Euclidean algorithm steps.
Inputs
Required base-10 integer from – 1,000,000,000 to 1,000,000,000. Signs are allowed; commas, decimals, and exponent notation are not.
Required positive integer from 2 to 1,000,000,000. The modulus must be greater than 1.
Existence test: the inverse exists exactly when gcd(a, m) = 1.
Result
Least nonnegative inverse
38
17 × 38 ≡ 1 (mod 43)
Because 17 and 43 are coprime, the inverse exists and is unique from 0 through 42.
Normalized a
17
Greatest common divisor
1
Verification residue
1
Bézout coefficient for m
– 15
The multiplicative inverse of 17 modulo 43 is 38.
Euclidean algorithm steps
| Step | Dividend | Divisor | Quotient | Remainder |
|---|---|---|---|---|
| 1 | 43 | 17 | 2 | 9 |
| 2 | 17 | 9 | 1 | 8 |
| 3 | 9 | 8 | 1 | 1 |
| 4 | 8 | 1 | 8 | 0 |
The final nonzero remainder is 1, so an inverse exists. Back-substitution gives 17 × 38 + 43 × ( – 15) = 1.
How to use this multiplicative inverse modulo calculator
What this calculator does
This calculator finds the least nonnegative integer x for which a × x ≡ 1 (mod m). In practical terms, it finds the number that “undoes” multiplication by a inside arithmetic modulo m. It also checks the necessary and sufficient existence condition, displays a Bézout identity, verifies the remainder, and lists the Euclidean divisions used to obtain the greatest common divisor. The result is an exact integer identity for the entered values; it is not a probability, approximation, or cryptographic security assessment.
When to use it
Use the calculator when solving linear congruences, checking homework in elementary number theory, implementing modular division in software, or working through small examples from public-key cryptography and coding theory. A modular inverse is also a building block in the Chinese remainder theorem and in algorithms that operate over finite fields. For a formal definition and compact mathematical notation, see the MathWorld explanation of modular inverses.
How to calculate
- The calculator opens with the ready-to-use demonstration a = 17 and m = 43. Its result and a validated Excel workbook are available immediately.
- Replace Integer a with the integer whose inverse you need. Negative values are accepted and are first reduced to their least nonnegative residue modulo m.
- Replace Modulus m with a positive integer greater than 1. Results update live as soon as both fields contain valid integers.
- Read Least nonnegative inverse first. Then use the GCD, verification residue, Bézout coefficient, and Euclidean algorithm table to audit the result.
- Select Download Excel to export the current inputs, outputs, identity, and algorithm steps. Selecting Reset clears the demonstration values and results; Excel export remains disabled until a complete valid pair is entered again.
Input guide
Integer a is required. Enter a plain base-10 integer from – 1,000,000,000 through 1,000,000,000, such as 17 or – 26. A plus or minus sign is allowed, but commas, decimal points, percent signs, and scientific notation are rejected rather than silently reinterpreted. Increasing or decreasing a does not create a simple monotonic change in the inverse because only the residue class a mod m matters. A common mistake is to assume that a nonzero a always has an inverse; it does not when a and m share a factor.
Modulus m is required. Enter a plain base-10 integer from 2 through 1,000,000,000, such as 43. The modulus defines the repeating residue system and the allowed least nonnegative answer range from 0 through m – 1. A larger modulus expands that range but does not guarantee existence. The most common validation mistake is entering 0, 1, a negative number, or a formatted value such as 1,000.
Output guide
Least nonnegative inverse is the unique representative from 0 through m – 1 when an inverse exists. If the GCD is greater than 1, the calculator reports that no inverse exists instead of inventing a value. Normalized a is the least nonnegative residue of the entered integer and explains why values such as – 26 and 17 can behave identically modulo 43. Greatest common divisor is the existence test: exactly 1 means invertible; any larger value means no inverse.
Verification residue is (normalized a × inverse) mod m. It must be exactly 1 whenever an inverse is displayed. Bézout coefficient for m is the integer y in a × x + m × y = 1; it may be negative and is supporting evidence, not a second inverse. The summary pills repeat the existence status, normalized input, GCD, and number of Euclidean divisions. The table columns show each Step, Dividend, Divisor, integer Quotient, and Remainder. The final nonzero remainder equals the GCD.
Worked example
With the startup values a = 17 and m = 43, the Euclidean algorithm gives 43 = 2×17 + 9, 17 = 1×9 + 8, 9 = 1×8 + 1, and 8 = 8×1 + 0. The final nonzero remainder is 1, so the inverse exists. Back-substitution produces 17×38 + 43×( – 15) = 1. Reducing both sides modulo 43 removes the multiple of 43 and leaves 17×38 ≡ 1 (mod 43). Therefore the displayed least nonnegative inverse is exactly 38, and the verification residue is exactly 1.
How the method works
The calculator uses the extended Euclidean algorithm. The ordinary Euclidean algorithm repeatedly divides and keeps the remainder until the remainder becomes zero; the preceding nonzero remainder is the GCD. The extended version tracks coefficients that express that GCD as a linear combination of the original values. LibreTexts provides a detailed treatment of the GCD, integers modulo n, and extended Euclidean method.
When the GCD is 1, the tracked coefficient of a satisfies a Bézout identity. Reducing that coefficient modulo m yields the least nonnegative inverse. This method is efficient because the number of divisions grows logarithmically with the size of the inputs rather than requiring a brute-force test of every possible residue. For implementation details and sign handling, consult the extended Euclidean algorithm reference at CP-Algorithms.
Interpretation and edge cases
If a is 0 modulo m, the GCD equals m, so no inverse exists. If m is prime, every value of a that is not a multiple of m has an inverse. For composite moduli, many nonzero residues are still non-invertible. A negative input is safe: the calculator normalizes it before computing and presents the standard least nonnegative representative.
The downloadable workbook mirrors the current canonical calculation rather than copying rounded text from the screen. It includes typed input and output cells, the congruence and Bézout identity, the complete division table, and a literal-text safety fixture so spreadsheet software does not interpret leading formula characters as formulas.
Practical check: when an inverse is shown, multiply it by the normalized value of a and divide by m. The remainder must be 1. If it is not, at least one input was copied incorrectly.