modedivision

Modedivision, or modular division, is the operation of dividing numbers within the arithmetic of a modulus m. It is defined by the rule a divided by b modulo m equals a times the multiplicative inverse of b modulo m, written as a * b^{-1} mod m, provided that b has an inverse modulo m.

Existence and uniqueness depend on the divisor. An inverse of b modulo m exists if and only if the greatest common divisor gcd(b, m) equals 1. In that case, a * b^{-1} mod m is well defined and unique modulo m. If gcd(b, m) > 1, modular division in the standard sense is not defined; however, the linear congruence b x ≡ a (mod m) may still have solutions, and there can be multiple solutions or none depending on gcd(b, m) dividing a.

Computation methods include the extended Euclidean algorithm, which yields integers s and t such that b s + m t = gcd(b, m). When gcd(b, m) = 1, s mod m is the modular inverse of b, and a / b mod m = a * (s mod m) mod m. If the modulus m is prime, the inverse can also be computed as b^{m-2} mod m using Fermat’s little theorem.

Example: compute 3 / 4 mod 7. The inverse of 4 modulo 7 is 2, since 4 * 2 ≡ 1 (mod 7). Therefore 3 / 4 mod 7 = 3 * 2 ≡ 6 (mod 7).

Applications of modedivision appear in cryptography, solving linear congruences, and algorithms that require division in modular arithmetic, such as key generation in public-key systems and various number-theoretic computations.