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

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

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

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

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\).