At the end of section 3.2 we saw that $\Z_n$ is in some arithmetic ways different than $\Z$. Much of this can be traced to the fact that not all elements of $\Z_n$ have multiplicative inverses (you may have noticed that when we discussed simple arithmetic in $\Z_n$ we left out division). Here we develop a "slimmed down'' version of $\Z_n$ that behaves nicely with respect to division.
Definition 3.4.1 The integers $a$ and $b$ are relatively prime if $(a,b)=1$. $\square$
Theorem 3.4.2 Suppose $a$ and $b$ are integers and $b$ is positive. The following statements are equivalent:
a) $a$ and $b$ are relatively prime,
b) there are integers $x$ and $y$ such that $ax+by=1$,
c) there is an integer $x$ such that $ax\equiv 1 \pmod b.$
Proof. (a) $\Rightarrow$ (b) follows from the Extended Euclidean Algorithm. To prove (b) $\Rightarrow$ (c), note that if $ax+by=1$, then $ax-1=(-y)b$, so $ax\equiv 1 \pmod b$. Finally, to prove (c) $\Rightarrow$ (a), if $ax\equiv 1\pmod b$, then there is a $z$ such that $ax=bz+1$, or $ax-bz=1$. If $g=(a,b)$, then $g\vert a$ and $g\vert b$, so $g\vert ax-bz=1$, which means $g=1$.$\qed$
Definition 3.4.3 If $n$ is a positive integer, let $\U_n\subseteq \Z_n$ consist of those $[u]$ such that for some $[v]$, $[u]\cdot [v]=[1]$, namely, those elements of $\Z_n$ that have multiplicative inverses. $\square$
The invertible elements of $\Z_n$ are sometimes called units—hence the $\U$. We say $[v]$ is an inverse (or reciprocal) of $[u]$. If we translate the last result into the language of $\Z_n$ we have the following:
Corollary 3.4.4 If $n$ is a positive integer, then $[u]\in \U_n$ if and only if $u$ and $n$ are relatively prime.
Proof. Immediate.$\qed$
Example 3.4.5 $\U_5=\{[1],[2],[3], [4]\}$. $[2]$ and $[3]$ are inverses of each other, while $[1]$ and $[4]$ are their own inverses. $\square$
Example 3.4.6 $\U_{14}=\{[1],[3],[5],[9],[11],[13]\}$. $[3]$ and $[5]$ are inverses, as are $[9]$ and $[11]$; $[1]$ and $[13]$ are their own inverses. $\square$
In these examples it was easy to find an inverse by inspection. In general, this can be done by the Extended Euclidean Algorithm.
Example 3.4.7 $[17]\in \U_{37}$. We apply the Extended Euclidean Algorithm to find: $ -13\cdot 17 + 6\cdot 37 = 1$, so $[-13]=[24]$ is an inverse for $[17]$. $\square$
We have referred to "an'' inverse, but there is only one.
Theorem 3.4.8 If $[u]\in \U_n$ then the inverse of $[u]$ is unique and is also an element of $\U_n$.
Proof. Suppose $[v_1]$ and $[v_2]$ are both inverses of $[u]$. Then $$ [v_1]=[v_1]\cdot[1]=[v_1]\cdot[u]\cdot[v_2] =[1]\cdot[v_2]=[v_2], $$ which implies uniqueness. Observe that if $[u]\cdot[v]= [1]$, then $[v]\cdot[u] = [1]$ so $[v]$ has an inverse, namely $[u]$, and so it is in $\U_n$.$\qed$
We denote the inverse of $[u]$ by $[u]^{-1}$. Note well that this notation only makes sense if $[u] \in \U_n$.
Proof. Suppose $[u_1]$ and $[u_2]$ are in $\U_n$ with inverses $[v_1]$ and $[v_2]$. Then $$ ([u_1]\cdot[u_2])\cdot([v_1]\cdot[v_2])=([u_1]\cdot[v_1]) \cdot([u_2]\cdot[v_2])=[1]\cdot [1]=[1], $$ so $[u_1]\cdot[u_2]$ has an inverse, namely $[v_1]\cdot[v_2]$, and so it is in $\U_n$.$\qed$
Example 3.4.10 Here is a multiplication table for $\U_9$:
| $\times$ | $[1]$ | $[2]$ | $[4]$ | $[5]$ | $[7]$ | $[8]$ |
|---|---|---|---|---|---|---|
| $[1]$ | $[1]$ | $[2]$ | $[4]$ | $[5]$ | $[7]$ | $[8]$ |
| $[2]$ | $[2]$ | $[4]$ | $[8]$ | $[1]$ | $[5]$ | $[7]$ |
| $[4]$ | $[4]$ | $[8]$ | $[7]$ | $[2]$ | $[1]$ | $[5]$ |
| $[5]$ | $[5]$ | $[1]$ | $[2]$ | $[7]$ | $[8]$ | $[4]$ |
| $[7]$ | $[7]$ | $[5]$ | $[1]$ | $[8]$ | $[4]$ | $[2]$ |
| $[8]$ | $[8]$ | $[7]$ | $[5]$ | $[4]$ | $[2]$ | $[1]$ |
$\square$
Notice that every row contains a $[1]$, as it must, allowing us to read off inverses: $[1]^{-1}=[1]$, $[2]^{-1}=[5]$, $[4]^{-1}=[7]$, $[8]^{-1}=[8]$.
In $\Z_n$ we can add, subtract and multiply, but we cannot always divide. Since division by $[x]$ is the same as multiplication by $[x]^{-1}$, in $\Z_n$ we can divide by precisely those elements which are in $\U_n$. Thus, if $p$ is a prime, algebra in $\Z_p$ is much like algebra in $\R$ or $\Q$. (Why?)
Exercises 3.4
Ex 3.4.1 Construct multiplication tables for $\U_5$ and $\U_{{14}}$.
Ex 3.4.2 Use the Extended Euclidean Algorithm to compute $[u]^{-1}$ in $\U_n$ where
| a) $u=5$, $n=13$, | b) $u= 13$, $n=19$. |
Ex 3.4.3 Using the fact that in $\U_{{39}}$, $[4]^{-1}= [10]$, find $[16]^{-1}$.
Ex 3.4.4 Suppose $g=\gcd(a,b)$. Since $g$ divides $a,b$ there are integers $a'$ and $b'$ with $a=a'g$, $b=b'g$. Prove that $a'$ and $b'$ are relatively prime.
Ex 3.4.5 How many elements are there in $\U_{243}$? ($243=3^5$)
Ex 3.4.6 Suppose $n$ is positive and $n\vert ab$. If $n$ and $a$ are relatively prime, prove $n\vert b$. (Hint: in $\Z_n$, $[a] \cdot [b]=[0]$.)
Ex 3.4.7 If $[u]\in \U_n$, prove that for every $[y]\in \U_n$ there is a unique $[x]\in \U_n$ such that $[u]\cdot [x]= [y]$. Prove the following consequence of this exercise that we will use in a later section: If $[u]\in\U_n$ and if $[a_1], …, [a_k]$ is a list of all the elements of $\U_n$, then so is $[u][a_1], …, [u][a_k]$.
Ex 3.4.8 Suppose $[u]\in \U_n$.
a) Show that there are distinct positive integers $i$ and $j$ such that $[u]^i=[u]^j$. (Hint: How many elements are in the set $\{[u]^i:i\in \N\}$?)
b) Use part (a) to show that there is a positive integer $k$ such that $[u]^k=[1]$.
c) What is $[u]^{k-1}$?
Ex 3.4.9 Suppose $[u]\in\U_n$. It is easy to see that $[u]^i[u]^j=[u]^{i+j}$ and $([u]^i)^j=[u]^{ij}$ if $i$ and $j$ are positive integers. Define $[u]^0=[1]$ and $[u]^{-k}=([u]^{-1})^k$ if $k$ is a positive integer. Prove that $[u]^{-k}=([u]^k)^{-1}$ when $k$ is a positive integer, and that $[u]^i[u]^j=[u]^{i+j}$ and $([u]^i)^j=[u]^{ij}$ for all integers $i$ and $j$.