Modular Multiplicative Inverse

The value of the modular inverse of an integer $ a $ modulo $ n $ is the value $ a^{-1} $ such that $ a \cdot a^{-1} \equiv 1 \mod n $

In other words, the modular inverse is a number that, multiplied by $ a $, gives a remainder equal to $ 1 $ in the arithmetic modulo $ n $.

It is common to denote this modular inverse $ u $ and to use these equations $$ u \equiv a^{-1} \mod n \\ a u \equiv 1 \mod n $$

The modular inverse of $ a $ modulo $ n $ exists if and only if $ \operatorname{gcd}(a,n) = 1 $, that is, if $ a $ and $ n $ are coprime.

If $ \operatorname{gcd}(a,n) = d > 1 $, then any linear combination $ a u + n v $ is a multiple of $ d $ and therefore can never be equal to $ 1 $.

If a modular inverse exists, then it is unique modulo $ n $. All solutions are of the form: $ u + k n $ with $ k $ an integer.

To calculate a modular inverse of $ a $ modulo $ n $, use Euclid's extended algorithm.

Euclid's extended algorithm makes it possible to find integers $ u $ and $ v $ such that $ a u + n v = \operatorname{gcd}(a,n) $. Since $ \operatorname{gcd}(a,n) = 1 $, then $ a u + n v = 1 $, reducing this modulo equality $ n $, the term $ n v $ disappears and there remains: $ a u \equiv 1 \mod n $. The value $ u $ is therefore a modular inverse of $ a $ modulo $ n $.

Use the Bezout identity, also available on dCode.

The keyword invmod is an abbreviation for invrse modular.

In programming or computer algebra, invmod(a,n) generally refers to the function that returns the modular inverse if such an inverse exists.

A multiplicative inverse of an element is a number that, when multiplied by that element, gives $ 1 $.

In modulo $ n $ arithmetic, the multiplicative inverse of $ a $ is equal to its modular inverse.

In RSA encryption, the private key $ d $ is calculated as the modular inverse of the public exponent $ e $ modulo $ \varphi(n) $. Without the modular inverse, it would be impossible to construct the decryption key.

The inverse of $ 2 $ modulo an odd number $ n $ is always equal to $ \frac{n+1}{2} $

Indeed: $ 2 \times \frac{n+1}{2} = n + 1 \equiv 1 \mod n $