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$.