Inverse Modulo Calculator

A modular multiplicative inverse of an integer a modulo m is an integer x whose product with a leaves remainder 1 when divided by m. In congruence language, a times x is congruent to 1 modulo m. This calculator finds the least nonnegative inverse using the extended Euclidean algorithm and then displays a multiplication check. The modulus must be an integer greater than one. An inverse exists exactly when a and m are coprime, meaning their greatest common divisor is 1. If they share a larger factor, every product involving a remains divisible by that factor modulo m and can never produce remainder 1. For example, 6 has no inverse modulo 15 because their greatest common divisor is 3. In contrast, 3 has inverse 4 modulo 11 because 3 times 4 equals 12, which leaves remainder 1 after division by 11. The extended Euclidean algorithm does more than compute a greatest common divisor. It also finds coefficients x and y satisfying ax plus my equals the greatest common divisor. When that divisor is 1, reducing x modulo m gives the modular inverse. If x is negative, adding enough copies of m places it in the standard range from zero through m minus one without changing its congruence class. Modular inverses replace division in modular arithmetic. Ordinary division cannot simply be applied to residue classes because different integers represent the same residue. Dividing by a modulo m means multiplying by the inverse of a, provided that inverse exists. This technique is central to solving linear congruences, simplifying modular fractions, applying the Chinese remainder theorem, and deriving many number-theory algorithms. Cryptography uses modular inverses extensively. RSA key generation computes an exponent inverse modulo a totient-related value, while elliptic-curve calculations use inverses when evaluating point formulas over finite fields. Coding theory, checksums, pseudorandom generators, and computer algebra also rely on efficient inverse calculations. Real cryptographic implementations use carefully designed big-integer and constant-time routines rather than browser number arithmetic, but the underlying number theory is the same. The inverse is unique modulo m, not as an ordinary integer. If 4 is an inverse of 3 modulo 11, then 15, negative 7, and every number differing from 4 by a multiple of 11 represent the same inverse residue. The calculator reports 4 because the least nonnegative representative is easiest to compare and reuse. To verify a result, multiply the original integer by the displayed inverse, divide by the modulus, and check that the remainder is 1. For negative inputs, the same rule applies because residues can always be normalized into the standard range. If the tool reports that no inverse exists, independently compute the greatest common divisor; any value above 1 proves the obstruction.