Related: Uva 571 Jugs ()
In modular arithmetic, the modular multiplicative inverse of an integer a modulo m is an integer x such that
The multiplicative inverse of a modulo m exists if and only if a and m are coprime (i.e., if gcd(a, m) = 1). If the modular multiplicative inverse of a modulo m exists, the operation of division by amodulo m can be defined as multiplying by the inverse of a, which is in essence the same concept as division in the field of reals.
Suppose we wish to find modular multiplicative inverse x of 3 modulo 11.
This is the same as finding x such that
Working in we find one value of x that satisfies this congruence is 4 because
- No prime number divides both a and b.
- There exist integers x and y such that ax + by = 1 (see Bézout's identity).
- The integer b has a multiplicative inverse modulo a: there exists an integer y such that by ≡ 1 (mod a). In other words, b is a unit in the ring Z/aZ of integers modulo a.
- Every pair of congruence relations for an unknown integer x, of the form x ≡ k (mod a) and x ≡ l (mod b), has a solution, as stated by the Chinese remainder theorem; in fact the solutions are described by a single congruence relation modulo ab.
- The least common multiple of a and b is equal to their product ab, i.e. LCM(a, b) = ab.
A number of conditions are individually equivalent to a and b being coprime: