SI242: Exploring multiplicative inverse mod n

Additive inverses and multiplicative inverses mod n

Additive inverses of elements of $\mathbb{Z}_n$ are actually quite easy to compute. Here's the rule: $-x$ in $\mathbb{Z}_n$ is 0 if $x = 0$ and $\underbrace{n - x}_{\text{integer $-$}}$ otherwise.

So, for example, in $\mathbb{Z}_{32}$, $-9$ is $32-9=23$. And, indeed, we see that $9 + 23$ is 0 in $\mathbb{Z}_{32}$.

Recall that the multiplicative inverse of $x$ in $\mathbb{Z}_n$ is a number $y$ such that $x*y = 1$ in $\mathbb{Z}_n$. We denote the multiplicative inverse of $x$ by $x^{-1}$. This is just notation, there is no actual expoentiation intended here! The situation with multiplicative inverses is more complicated than with additive inverses. For starters, zero never has a multiplicative inverse. But for different values of $x$ and $n$, $x$ may or may not have a multiplicative mod $n$. We saw that last class. For instance $2$ does not have a multiplicative inverse mod 4, but 3 does. In $\mathbb{Z}_{11}$, every non-zero number has a multiplicative inverse.

In-class activity This had you using your programming skillz to investigate when numbers fail to have inverses mod $n$. You generated a lot of data, and then made a hypothesis: for a given $n$ and $x$ in $\mathbb{Z}_n$, what determines whether $x$ has a multiplicative inverse in $\mathbb{Z}_n$? What folks came up with was this:

Hypothesis: If $x$ and $n$ have a common divisor greater than 1 (remember, 1 is a common divisor of any pair of numbers), then $x$ has no multiplicative inverse mod $n$.

Proving the hypothesis

Of course, even thought the data our computer programs produced all supports the hypothesis, to be sure it is always true we have to prove it!

If $x$ and $n$ have a common divisor $g$ such that $1 \lt g$, then $x$ has no multiplicative inverse mod $n$.

Let $y$ be an arbitrary but fixed value in $\mathbb{Z}_n$. Then $x*y$ in $\mathbb{Z}_n$ is the remainder when we divide $x*y$ by $n$, so let $r$ be that remainder and $q$ the quotient.
$x*y = q*n + r$
$x*y + -q*n = r$
By the from Problem 1 of HW09, since $g$ is a common divisor of $x$ and $n$, $g|x*y + -q*n$, and since $x*y + -q*n = r$, we know $g|r$. So by the "Divisors are smaller" theorem, $g \leq r$, and since $1 \lt g$ that means $1 \lt r$. So, for any $y$, $x*y \bmod n \neq 1$, and that means $x$ has no multiplicative inverse.