What a modular inverse means

An integer x is a multiplicative inverse of a modulo m when ax leaves remainder 1 after division by m. The notation is ax ≡ 1 (mod m). Multiplying both sides of a congruence by this inverse plays the role of division, but only inside the modular system and only when the inverse exists.

The inverse is a residue class, so infinitely many integers represent it. If 38 is the least nonnegative inverse modulo 43, then 38 + 43k is also an inverse for every integer k. This calculator reports the unique representative from 0 through m − 1.

Worked example: inverse of 17 modulo 43

The Euclidean algorithm begins with 43 = 2 × 17 + 9. Then 17 = 1 × 9 + 8, 9 = 1 × 8 + 1, and 8 = 8 × 1 + 0. The last nonzero remainder is 1, proving that 17 and 43 are coprime and that an inverse exists.

Back-substitution gives 1 = 9 − 8 = 9 − (17 − 9) = 2 × 9 − 17 = 2 × (43 − 2 × 17) − 17. Therefore 1 = 2 × 43 − 5 × 17. The coefficient of 17 is −5, and its least nonnegative residue modulo 43 is −5 + 43 = 38.

The direct certificate is 17 × 38 = 646. Because 646 = 15 × 43 + 1, the product has remainder 1. This multiplication check is short enough to include whenever a modular inverse is reported.

Solving ax ≡ b modulo m

If a has an inverse, multiply both sides by a⁻¹. The solution is x ≡ a⁻¹b (mod m). In the default case b = 1, so x ≡ 38. If b were 7, the raw product would be 266 and the normalized solution would be 8 because 266 = 6 × 43 + 8.

When gcd(a,m) is greater than one, an inverse does not exist, but the general congruence may still have solutions. Let d = gcd(a,m). If d does not divide b, there is no solution. If d divides b, divide a, b, and m by d, solve the reduced congruence, and lift its d solution classes modulo the original m.

This calculator centers on inverses and therefore reports the inverse-based single residue only when gcd equals one. It also states the divisibility result for a noncoprime coefficient so “no inverse” is not confused with “no congruence solution.”

Why normalization matters

JavaScript and some programming languages return a signed remainder for negative inputs. Mathematical modular arithmetic normally uses the least nonnegative residue r satisfying 0 ≤ r < m. The calculator normalizes with ((value % m) + m) % m.

For example, −5 mod 43 is 38, not −5 in the selected representation. Both integers belong to the same residue class because they differ by 43. Normalization makes comparisons, table indexes, cryptographic steps, and final answers consistent.

A negative a is handled the same way. The inverse of −17 modulo 43 is the negative of the inverse of 17, normalized: −38 ≡ 5. Checking (−17) × 5 = −85 = −2 × 43 + 1 confirms it.

Extended Euclidean algorithm

The ordinary Euclidean algorithm tracks remainders to find the GCD. The extended version simultaneously tracks coefficients s and t so each remainder equals sa + tm. When the remainder becomes the GCD, the accompanying coefficients form a Bézout identity.

Its running time grows roughly with the number of digits, making it far better than trying every residue for large inputs. The quotient tape shows the ordinary division path; the Bézout panel gives the final extended result. Both should agree on the GCD.

The input cap of one billion keeps every integer product safely within ordinary browser precision for this educational calculator. Cryptographic systems use integers hundreds or thousands of bits long and require arbitrary-precision, constant-time implementations rather than floating-point numbers.

Prime and composite moduli

When m is prime, every nonzero residue has an inverse because none shares a factor with m. When m is composite, only residues coprime to m are units. Modulo 12, for example, 5 has inverse 5 because 25 ≡ 1, while 6 has no inverse because gcd(6,12) = 6.

Euler’s theorem gives a theoretical inverse a^(φ(m)−1) modulo m when gcd(a,m)=1. For a prime p, Fermat’s little theorem gives a^(p−2) mod p. These exponent methods are useful in some computational settings, but the extended Euclidean algorithm works without factoring m and directly supplies a proof certificate.

Applications and boundaries

Other uses include modular division in competitive programming, cyclic scheduling, checksums, affine ciphers, and combinatorial formulas.

Security boundary: This calculator demonstrates arithmetic. It does not generate keys, protect secrets, avoid timing leakage, or validate a cryptographic protocol.

Units in a residue ring

The invertible residue classes modulo m form the multiplicative group of units. Their count is Euler’s totient φ(m). Modulo 10, the units are 1, 3, 7, and 9; each is coprime to 10. The remaining nonzero classes 2, 4, 5, 6, and 8 have no multiplicative inverse.

Some units are self-inverse. Modulo 10, 3 × 7 ≡ 1, so 3 and 7 are inverse partners, while 1 and 9 are their own inverses. In general, applying the inverse operation twice returns the original residue: (a⁻¹)⁻¹ ≡ a.

The cancellation law depends on being a unit. From ac ≡ bc (mod m), one may cancel c only when gcd(c,m)=1, or with a more careful reduction of the modulus. Ordinary-looking cancellation by a zero divisor can discard valid residue classes or create a false conclusion.

Chinese remainder construction example

Suppose x ≡ 2 (mod 3) and x ≡ 3 (mod 5). The combined modulus is 15. For the first congruence, use M₁ = 15/3 = 5 and find the inverse of 5 modulo 3, which is 2. For the second, use M₂ = 15/5 = 3 and find the inverse of 3 modulo 5, which is 2.

A constructive solution is x = 2 × 5 × 2 + 3 × 3 × 2 = 38. Normalizing modulo 15 gives x ≡ 8. Check: 8 leaves remainder 2 modulo 3 and remainder 3 modulo 5. The modular inverses make each constructed term equal one in its intended modulus and zero in the other.

Pairwise-coprime moduli guarantee one solution class modulo their product. Noncoprime moduli require compatibility checks and may combine to a smaller least-common-multiple modulus. Do not apply the pairwise-coprime formula without checking.

Noncoprime linear congruence example

Consider 6x ≡ 8 (mod 14). The GCD of 6 and 14 is 2, and 2 divides 8, so solutions exist even though 6 has no inverse modulo 14. Divide the entire congruence by 2 to obtain 3x ≡ 4 (mod 7). The inverse of 3 modulo 7 is 5, giving x ≡ 20 ≡ 6 (mod 7).

Lifting back to modulus 14 gives two classes: x ≡ 6 and x ≡ 13. Substitution confirms 6 × 6 = 36 ≡ 8 and 6 × 13 = 78 ≡ 8 modulo 14. The number of classes equals the original GCD.

By contrast, 6x ≡ 9 (mod 14) has no solution because the left side and modulus share factor 2 while 9 is odd. This divisibility test should come before any attempted division.

Programming precision and safe products

JavaScript numbers store integers exactly only through 2⁵³ − 1. Even when a, b, and m are individually exact, a product such as a × inverse can exceed that boundary. This calculator caps inputs at one billion so its displayed certificate products remain within a practical exact range for the intended examples.

Arbitrary-precision languages and BigInt can handle much larger integers, but cryptographic software adds another requirement: execution patterns should not leak secrets through timing, memory access, or branches. A mathematically correct classroom implementation is not automatically secure.

When porting the algorithm, define the remainder convention explicitly, avoid floating division when calculating integer quotients, test zero and negative inputs, and verify against known Bézout identities. Property-based tests can generate coprime pairs and assert that normalized a × inverse equals one.

Common mistakes and audit rules

Do not divide ordinary integers and round. The inverse of 17 modulo 43 is not 1/17 as a decimal. Do not assume every nonzero a has an inverse under a composite modulus. Check the GCD first. Do not report a negative coefficient without stating the residue convention.

Verify three facts: the reported inverse lies from 0 through m − 1, gcd(a,m)=1, and the normalized product equals one. For a solved ax ≡ b congruence, substitute x and check that normalized ax equals normalized b.

Swapping a and m changes the problem. Although the Euclidean GCD is symmetric, “inverse of a modulo m” is not symmetric because the modulus defines the residue system.

Frequently asked questions

References

NIST CSRC glossary — modular arithmetic

Wolfram MathWorld — modular inverse and extended Euclidean method

Wolfram MathWorld — Bézout’s identity