# 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 💡