Number Theory

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 $yz=x(modn)$, which by definition means

$$x=zy+kn$$

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+tn/d,k=s-ty/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=ry+sn$$

Then the solutions for $z,k$ are given by

$$z=zr+tn,k=zs-ty$$

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

Also, $r$ satisfies $ry=1(modn)$ 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 $yz=x$.

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}(mod19)$ 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 (\mathrm{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{array}{ccc}1& =& 5-2\times 2\\ & =& 5-2\times (7-1\times 5)\\ & =& (-2)\times 7+3\times 5\end{array}$$

Now substituting in the first equation gives

$$\begin{array}{ccc}1& =& (-2)\times 7+3\times (19-2\times 7)\\ & =& (-8)\times 7+3\times 19\end{array}$$

from which we see that $7^{-1}=-8=11(mod19)$.