Finding Units and Inverses

Purpose
We are often interested in the units of a ring because we want to be able to cancel in the same way as we are able to do in over the real numbers. This is an essential feature of solving for unknowns in equations (which is a focus in many courses you most likely have taken).

Proposition: Let $m \in \mathbb{N}$ and $a \in \mathbb{Z}$ . The residue class $a+m\mathbb{Z}$ is invertible in $\mathbb{Z}/m\mathbb{Z}$ if and only if $\gcd(a,m)=1$ .

The proposition above gives us a way of determining if an arbitrary element is invertible. For example, consider the ring $\mathbb{Z}/15\mathbb{Z}$ ,

The element $3+15\mathbb{Z}$ is not invertible since $\gcd(3,15)=3$ .
The element $4+15\mathbb{Z}$ is invertible since $\gcd(4,15)=1$ .

We can determine any unit in this way. Suppose I want to find all units of the ring, then I may do the following:

Step 1: List all positive integers less than $m=15$ .

$\begin{array}{ccccc}&1&2&3&4 \\5&6&7&8&9 \\10&11&12&13&14\end{array}$

Step 2: Note that $15$ has the unique prime factorization: $15=3\cdot 5$ . For every prime dividing $15$ , we remove all of the prime’s multiples from the list:

$\begin{array}{ccccc}&1&2&&4 \\&&7&8& \\&11&&13&14\end{array}$

Therefore, $1+15\mathbb{Z}$ , $2+15\mathbb{Z}$ , $4+15\mathbb{Z}$ , $7+15\mathbb{Z}$ , $8+15\mathbb{Z}$ , $11+15\mathbb{Z}$ , $13+15\mathbb{Z}$ and $14+15\mathbb{Z}$ are the units of $\mathbb{Z}/15\mathbb{Z}$ .

Note that determining the every unit for a larger ring such as $\mathbb{Z}/192423$ , this becomes less effective, unless we have a program which computes this for us.

Exercises

Determine the units of $\mathbb{Z}/12\mathbb{Z}$ .

List all the integers from $1$ to $11$ ,

$\begin{array}{cccccc} & 1 & 2 & 3 & 4 & 5 \\ 6 & 7 & 8 & 9 & 10 & 11 \end{array}$

The unique factorization of $12$ is $12=2^2\cdot 3$ . For each prime $p$ dividing $12$ , we remove all multiples from the list:

$\begin{array}{cccccc} & 1 & & & & 5 \\ & 7 & & & & 11 \end{array}$

Therefore, the units of $\mathbb{Z}/12\mathbb{Z}$ are $1+12\mathbb{Z}$ , $5+12\mathbb{Z}$ , $7+12\mathbb{Z}$ , and $11+12\mathbb{Z}$ .

Determine the units of $\mathbb{Z}/25\mathbb{Z}$ .

Determine the units of $\mathbb{Z}/25\mathbb{Z}$ . \\ List all the integers from $1$ to $24$ ,

$\begin{array}{cccccc} & 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 & 9 \\ 10 & 11 & 12 & 13 & 14 \\ 15 & 16 & 17 & 18 & 19 \\ 20 & 21 & 22 & 23 & 24 \end{array}$

The unique factorization of $25$ is $25=5^2$ . For each prime $p$ dividing $25$ , we remove all multiples from the list:

$\begin{array}{cccccc} & 1 & 2 & 3 & 4 \\ & 6 & 7 & 8 & 9 \\ & 11 & 12 & 13 & 14 \\ & 16 & 17 & 18 & 19 \\ & 21 & 22 & 23 & 24 \end{array}$

Therefore, for each $a$ in the list above, $a+25\mathbb{Z}$ is a unit in $\mathbb{Z}/25\mathbb{Z}$ .

Suppose that we additionally want to find the inverse of each invertible element in $\mathbb{Z}/15\mathbb{Z}$ . We can test each unit with every other unit (including itself). To do this, we take the product of every pair of units and reduce modulo $m=15$ until we obtain $1$ , then we remove the pair from the list and continue.

The integers corresponding to units in $\mathbb{Z}/15\mathbb{Z}$ are: $1$ , $2$ , $4$ , $7$ , $8$ , $11$ , $13$ , $14$ .

$\begin{align*}1\cdot 1 &= 1\equiv 1\mod 15 \end{align*}$

Therefore, the inverse of $1+15\mathbb{Z}$ is itself (this will occur for all $m$ !)

$\begin{align*}2\cdot 2 &= 4 \equiv 4 \mod 15 \\2\cdot 4 &= 8 \equiv 8 \mod 15 \\2 \cdot 7 &= 14 \equiv 14\mod 15 \\2 \cdot 8 &= 16 \equiv 1 \mod 15 \end{align*}$

Therefore, $2+15\mathbb{Z}$ and $8+15\mathbb{Z}$ are inverses of each other.

$\begin{align*}4\cdot 4 &= 16 \equiv 1 \mod 15\end{align*}$

Therefore, the inverse of $4+15\mathbb{Z}$ is itself.

$\begin{align*}7\cdot7 &=49 \equiv 4 \mod 15 \\7\cdot 11 &= 77 \equiv 2 \mod 15 \\7\cdot 13 &= 91 \equiv 1 \mod 15 \end{align*}$

Therefore, $7+15\mathbb{Z}$ and $13+15\mathbb{Z}$ are inverses of each other.

$\begin{align*}11\cdot 11&= 121\equiv 1 \mod 15 \end{align*}$

Therefore, the inverse of $11+15\mathbb{Z}$ is itself.

$\begin{align*}14\cdot 14&= 196 \equiv 1 \mod 15\end{align*}$

Therefore, the inverse of $14+15\mathbb{Z}$ is itself.

Exercises

Determine the units and their inverses of $\mathbb{Z}/20\mathbb{Z}$ .

List all the integers from $1$ to $19$ ,

$\begin{array}{cccccc} & 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 & 9 \\ 10 & 11 & 12 & 13 & 14 \\ 15 & 16 & 17 & 18 & 19 \\ \end{array}$

The unique factorization of $20$ is $20=2^2\cdot 5$ . For each prime $p$ dividing $20$ , we remove all multiples from the list:

$\begin{array}{cccccc} & 1 & & 3 & \\ & & 7 & & 9 \\ & 11 & & 13 & \\ & & 17 & & 19 \\ \end{array}$

Therefore, for each $a$ in the list above, $a+20\mathbb{Z}$ is a unit in $\mathbb{Z}/20\mathbb{Z}$ . The inverse of the unit $1+20\mathbb{Z}$ is itself. \\

$\begin{align*} 3\cdot 3 &= 9 \equiv 9 \mod 20 \\ 3\cdot 7 &= 21 \equiv 1 \mod 20 \end{align*}$

Therefore, $3+20\mathbb{Z}$ and $7+20\mathbb{Z}$ are inverses of each other. \\

$\begin{align*} 9\cdot 9 &= 81 \equiv 1 \mod 20 \end{align*}$

Therefore, $9 + 20\mathbb{Z}$ is its own inverse. \\

$\begin{align*} 11\cdot 11 &= 121 \equiv 1 \mod 20 \end{align*}$

Therefore, $11 + 20\mathbb{Z}$ is its own inverse. \\

$\begin{align*} 13\cdot 13 &= 169 \equiv 9 \mod 20 \\ 13\cdot 17 &= 221 \equiv 1 \mod 20 \end{align*}$

Therefore, $13+20\mathbb{Z}$ and $17+20\mathbb{Z}$ are inverses of each other. \\

$\begin{align*} 19\cdot 19 &= 361 \equiv 1 \mod 20 \end{align*}$

Therefore, $19 + 20\mathbb{Z}$ is its own inverse.

You may not be interested in every unit of a particular ring (especially for larger rings); however, you may want to determine if an element is invertible and find its inverse.

For example, is $25+63\mathbb{Z}$ invertible in $\mathbb{Z}/63\mathbb{Z}$ ?

$\begin{array}{rcccc}&&q_i&u_i&v_i \\i=0: &&& 0 & 1 \\i=1: & 63=25\cdot 2+13 & 2 & 1 &-2 \\i=2: & 25=13\cdot 1 + 12 & 1 & -1 & 3 \\i=3: & 13 = 12\cdot 1 + 1 & 1 & 2 &-5 \\i=4: & 12 = 1\cdot 12\end{array}$

Therefore, $1=63\cdot(2) + 25\cdot(-5)$ . Therefore, $-5+63\mathbb{Z}=58+63\mathbb{Z}$ is the inverse of $25+63\mathbb{Z}$ .

Exercises

Find the inverse of $13+101\mathbb{Z}$ , if it exists.

$\begin{array}{rcccc} &&q_i&u_i&v_i \\ i=0: &&& 0 & 1 \\ i=1: & 101=13\cdot 7+10 & 7 & 1 &-7 \\ i=2: & 13=10\cdot 1 + 3 & 1 & -1 & 8 \\ i=3: & 10 = 3\cdot 3 + 1 & 3 & 4 &-31 \\ i=4: & 3 = 1\cdot 3 \end{array}$

Therefore, $\gcd(101,13)=1=101\cdot(4) + 13\cdot(-31)$ . Therefore, $-31+101\mathbb{Z}=70+101\mathbb{Z}$ is the inverse of $13 + 101\mathbb{Z}$ .

Find the inverse of $27+1235\mathbb{Z}$ , if it exists.

$\begin{array}{rcccc} &&q_i&u_i&v_i \\ i=0: &&& 0 & 1 \\ i=1: & 1235=27\cdot 45+20 & 45 & 1 &-45 \\ i=2: & 27=20\cdot 1 + 7 & 1 & -1 & 46 \\ i=3: & 20 = 7\cdot 2 + 6 & 2 & 3 &-137 \\ i=4: & 7 = 6\cdot 1 + 1 & 1 & -4 & 183 \\ i=5: & 6 = 1 \cdot 6 \end{array}$

Therefore, $\gcd(1235,27)=1=1235\cdot(-4) + 27\cdot(183)$ . Therefore, $183 + 1235\mathbb{Z}$ is the inverse of $27 + 1235\mathbb{Z}$ .

Find the inverse of $119+714\mathbb{Z}$ , if it exists.

$\begin{array}{rcccc} &&q_i&u_i&v_i \\ i=0: &&& 0 & 1 \\ i=1: & 714=119\cdot 6 & & 1 & \\ \end{array}$

Therefore, $\gcd(119,714)=119\not=1$ Therefore, $119+714\mathbb{Z}$ is not invertible.

Find the inverse of $235+1952\mathbb{Z}$ , if it exists.

$\begin{array}{rcccc} &&q_i&u_i&v_i \\ i=0: &&& 0 & 1 \\ i=1: & 1952=235\cdot 8+72 & 8 & 1 &-8 \\ i=2: & 235 = 72\cdot 3+19 & 3 & -3 & 25 \\ i=3: & 72 = 19\cdot 3+15 & 3 & 10 &-83 \\ i=4: & 19 = 15\cdot 1+4 & 1 & -13 & 108 \\ i=5: & 15 = 4\cdot 3 + 3 & 3 & 49 & -407 \\ i=6: & 4=3\cdot 1 + 1 & 1 &-62 & 515 \\ i=7: & 3=1\cdot 3 \end{array}$

Therefore, $1=1952\cdot(-62) + 235\cdot(515)$ . Therefore, $515+1952\mathbb{Z}$ is the inverse of $235+1952\mathbb{Z}$ .

Malachi Alexander

UCSC Graduate Student

Finding Units and Inverses