## [Modular Inversion](/modular-inversion-0) Definition The procedure of finding an integer x such that a·x ≡ 1 (mod m) when such x exists; equivalently finding the multiplicative inverse of a modulo m, typically computed via the Extended Euclidean Algorithm when gcd(a,m)=1. ## Principle Principle Because a has an inverse modulo m exactly when gcd(a,m)=1, compute gcd(a,m) and Bézout coefficients; the coefficient corresponding to a reduced modulo m gives the inverse. ## Demonstration Demonstration Find inverse of 3 modulo 11. Since gcd(3,11)=1 and 3·4 = 12 ≡ 1 (mod 11), the inverse is 4. Using the Extended Euclidean Algorithm also yields the coefficient 4 as the Bézout solution for 3 and 11. ## Misapplication Misapplication Attempting to compute an inverse when gcd(a,m) ≠ 1 (e.g., asking for the inverse of 6 modulo 9), or using floating‑point arithmetic that loses exact divisibility information. ## Consequence Consequence A correct modular inverse enables division in modular arithmetic, solving linear congruences and supporting cryptographic operations like signature creation and verification. ## Reversal Reversal The reversal asks for values for which an inverse does not exist: when gcd(a,m) > 1 the correct response is existence of multiple solutions to a·x ≡ b or none, not a single inverse; inversion cannot proceed. ## Boundary Boundary Defined only in rings where multiplicative inverses may exist; for Z/mZ an inverse exists iff a is coprime to m. For non-prime moduli one must check gcd; in noncommutative rings left and right inverses may differ. ## Semantic Tension Semantic Tension Close to the concept of multiplicative inverse in a field; tension arises because Z/mZ is a field only when m is prime, so 'modular inverse' in composite moduli requires the coprimality condition and is not automatic. ## Synthesis Synthesis Modular inversion is the application of gcd testing and Bézout coefficient extraction to obtain an integer that acts as the multiplicative inverse of a modulo m whenever the numbers are coprime.