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 \gt 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 \lt 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 = z 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

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

Now substituting in the first equation gives

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

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