Modular Inverses

Multiplicative inverse

Let $S$ be our set that has some notion $a · b$ of multiplication and a neutral element $1 ∈ S$, such that $1 · a = a$ for all elements $a ∈ S$. Then a multiplicative inverse $a^{−1}$ of an element $a ∈ S$ is defined as follows:

$$a · a^{−1} = 1.$$

If $a$ is number such that the multiplicative inverse $a^{−1}$ exists, then we define division by a simply as multiplication by the inverse:

$$b/a := b · a^{−1}.$$

In modular $n$ arithmetic, a number $r$ has a multiplicative inverse if and only if $n$ and $r$ are coprime. Since $gcd(n, r) = 1$ in that case, we know from the Extended Euclidean Algorithm that there are numbers $s$ and $t$, such that the following equation holds:

$$1 = s · n + t · r$$

If we take the modulus $n$ on both sides, the term $s · n$ vanishes, which tells us that $t \mod n$ is the multiplicative inverse of $r$ in modular $n$ arithmetic.

The situation where the modulus is a prime number is of particular interest, because in these cases, all remainder classes must have modular inverses, since $gcd(r, n) = 1$ for prime $n$ and any $r < n$. In fact, Fermat’s Little Theorem provides a way to compute multiplicative inverses in this situation, since, in case of a prime modulus $p$ and $r < p$, we get the following:

$$r^p ≡ r \mod p ⇔ \\ r^{p−1} ≡ 1 \mod p ⇔\\ r · r^{p−2} ≡ 1 \mod p.$$

This tells us that the multiplicative inverse of a residue class $r$ in modular $p$ arithmetic is precisely $r^{p−2}$.

Additive inverse

The definition of multiplicative inverse has an analog definition for addition called the additive inverse. In the case of integers, the neutral element with respect to addition is 0, since $a + 0 = 0$ for all integers $a ∈ Z$. The additive inverse always exists, and is given by the negative number $−a$, since $a + (−a) = 0$.