Division

Intuitively, to divide \(x\) by \(y\) means to find a number \(z\) such that \(y\) times \(z\) is \(x\), but we had trouble adopting this defintion of division because sometimes there is more than one possibility for \(z\) modulo \(n\).

We solved this by only defining division when the answer is unique. We stated without proof that when division defined in this way, one can divide by \(y\) if and only if \(y^{-1}\), the inverse of \(y\) exists.

We shall now show why this is the case. We wish to find all \(z\) such that \(y z = x \pmod{n}\), which by definition means

\[ x = z y + k n \]

for some integer \(k\). But this is precisely the problem we encountered when discussing Euclid’s algorithm! Let \(d = \gcd(y,n)\).

Suppose \(d > 1\). Then no solutions exist if \(x\) is not a multiple of \(d\). Otherwise the solutions for \(z, k\) are

\[ z = r + t n / d, k = s - t y / d \]

for some integers \(r,s\) (that we get from Euclid’s algorithm) and for all integers \(t\). But this means \(z\) does not have a unique solution modulo \(n\) since \(n / d < n\). (Instead \(z\) has a unique solution modulo \(n / d\).)

On the other hand, if \(d = 1\), that is if \(y\) and \(n\) are coprime, then \(x\) is always a multiple of \(d\) so solutions exist. Recall we find them by using Euclid’s algorithm to find \(r, s\) such that

\[ 1 = r y + s n\]

Then the solutions for \(z, k\) are given by

\[ z = x r + t n , k = z s - t y \]

for all integers \(t\). Thus \(z\) has a unique solution modulo \(n\), and division makes sense for this case.

Also, \(r\) satisfies \(r y = 1 \pmod{n}\) so in fact \(y^{-1} = r\). Thus our claims are correct: we can divide \(x\) by \(y\) if and only if \(y\) has an inverse.

We can also see that \(y\) has an inverse if and only if \(\gcd(y, n) = 1\). (Actually, we have only proved some of these statements in one direction, but the other direction is easy.)

Note: even though we cannot always divide \(x\) by \(y\) modulo \(n\), sometimes we still need to find all \(z\) such that \(y z = x\).

Computing Inverses

We previously asked: given \(y \in \mathbb{Z}_n\), does \(y^{-1}\) exist, and if so, what is it?

Our answer before was that since \(\mathbb{Z}_n\) is finite, we can try every possibility. But if \(n\) is large, say a 256-bit number, this cannot be done even if we use the fastest computers available today.

A better way is to use what we just proved: \(y^{-1}\) exists if and only if \(\gcd(y, n)=1\) (which we can check using Euclid’s algorithm), and \(y^{-1}\) can be computed efficiently using the extended Euclidean algorithm.

Example: does \(7^{-1} \pmod {19}\) exist, and if so, what is it? Euclid’s algorithm gives

\[ 19 = 2\times 7 + 5 \]
\[ 7 = 1\times 5 + 2 \]
\[ 5 = 2\times 2 + 1 \]

Thus an inverse exists since \(\gcd(7,19) = 1\). To find the inverse we rearrange these equations so that the remainders are the subjects. Then starting from the third equation, and substituting in the second one gives

\[ \begin{aligned} 1 &=& 5 - 2\times 2 \\ &=& 5 - 2 \times (7 - 1\times 5) \\ &=& (-2)\times 7 + 3\times 5 \end{aligned} \]

Now substituting in the first equation gives

\[ \begin{aligned} 1 &=& (-2)\times 7 + 3\times(19 - 2\times 7) \\ &=& (-8)\times 7 + 3 \times 19 \end{aligned} \]

from which we see that \(7^{-1} = -8 = 11 \pmod{19}\).


Ben Lynn blynn@cs.stanford.edu 💡