The first step is relatively slow but only needs to be done once. Modular multiplicative inverses are used to obtain a solution of a system of linear congruences that is guaranteed by the Chinese Remainder Theorem. For example, the system ≡ 4 (mod 5) ≡ 4 (mod 7) ≡ 6 (mod 11) has common solutions since 5,7 and 11 are pairwise coprime. A solution is given by = (7 × 11) × 4 + (5 × 11) × 4 + (5 × 7) × 6 where = 3 is the modular multiplicative inverse of 7 × 11 (mod 5), = 6 is the modular multiplicative inverse of 5 × 11 (mod 7) and = 6 is the modular multiplicative inverse of 5 × 7 (mod 11). Thus, = 3 × (7 × 11) × 4 + 6 × (5 × 11) × 4 + 6 × (5 × 7) × 6 = 3504 and in its unique reduced form ≡ 3504 ≡ 39 (mod 385) since 385 is the LCM of 5,7 and 11. Also, the modular multiplicative inverse figures prominently in the definition of the Kloosterman sum. See also Inversive congruential generator – a pseudo-random number generator that uses modular multiplicative inverses Rational reconstruction (mathematics) Notes References External links Guevara Vasquez, Fernando provides a solved example of solving the modulo multiplicative inverse using Euclid's Algorithm Modular arithmetic Binary operations