Modular Inverse

Number Theory · Axiom Academy

Finding multiplicative inverses in modular arithmetic 1. Definition and When Inverses Exist The modular inverse of a modulo n is a number a -1 such that: This means that in modulo 12, the number 5 has an inverse (since gcd(5, 12) = 1), but 6 does not (since gcd(6, 12) = 6). 2. Extended Euclidean Algorithm The Extended Euclidean Algorithm is the most efficient method for finding modular inverses. It finds integers x and y such that: When gcd( a , n ) = 1, this becomes: 3. Properties and Applications If a -1 exists, it is unique modulo n ( ab ) -1 ≡ a -1 b -1 (mod n ) when both inverses exist Solving Linear Congruences: To solve ax ≡ b (mod n ), multiply both sides by a -1 RSA Cryptography: Finding decryption exponents requires modular inverses Error-Correcting Codes: Computing syndrome polynomials in Reed-Solomon codes Rational Arithmetic mod p: Enables division in finite fields

This is the written version of the interactive lesson above. See the full Number Theory course.