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

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

$\square$

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.

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.

$\square$

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.

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.

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

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

$\square$

We denote the inverse of $[u]$ by $[u]^{-1}$. Note well that this notation only makes sense if $[u] \in \U_n$.

Theorem 3.4.9 The product of any two elements of $\U_n$ is an element of $\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$.

$\square$

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

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