1.22: The Groups Um

Definition \(\PageIndex{1}\)

Let \(m>0\). A residue class \([a]\in\mathbb{Z}_m\) is called a unit if there is another residue class \([b]\in\mathbb{Z}_m\) such that \([a][b]=[1]\). In this case \([a]\) and \([b]\) are said to be inverses of each other in \(\mathbb{Z}_m\).

Theorem \(\PageIndex{1}\)

Let \(m>0\). A residue class \([a]\in\mathbb{Z}_m\) is a unit if and only if \(\gcd(a,m)=1\).

Proof

Let \([a]\) be a unit. Then there is some \([b]\) such that \([a][b]=[1]\). Hence \([ab]=[1]\) so \(ab\equiv 1\pmod m\). So by Theorem 1.20.2, \(\gcd(a,m)=1\).

To prove the converse, let \(\gcd(a,m)=1\). Then by Theorem 1.20.1, there is an integer \(a^\ast\) such that \(aa^{\ast}\equiv 1\pmod m\). Hence, \([aa^\ast]=[1]\). So \([a][a^\ast]=[aa^\ast]=[1]\), and we can take \(b=a^\ast\).

We see from Theorem 1.20.6 that if \([a]=[b]\) (i.e., \(a\equiv b\pmod m\)) then \(\gcd(a,m)=1\Leftrightarrow\gcd(b,m)=1\). So in checking whether or not a residue class is a unit, we can use any representative of the class.

The elements \([1]\) and \([m-1]\) are always units in \(\mathbb{Z}_m\) (see Exercise \(\PageIndex{1}\)). The collection all units in \(\mathbb{Z}_m\) will be our next focus.

Definition \(\PageIndex{2}\)

The set of all units in \(\mathbb{Z}_m\) is denoted by \(U_m\) and is called the group of units of \(\mathbb{Z}_m\). See Appendix C for the definition of a group.

Theorem \(\PageIndex{2}\)

Let \(m>0\), then \[U_m=\{[i]\mid 1\le i\le m\text{ and }\gcd(i,m)=1\}.\nonumber \]

Proof

We know that if \([a]\in\mathbb{Z}_m\) then \([a]=[i]\) where \(0\le i\le m-1\). If \(m=1\) then \(\mathbb{Z}_m=\mathbb{Z}_1=\{[0]\}=\{[1]\}\) and since \([1][1]=[1]\), \([1]\) is a unit, \(U_1=\{[1]\}\) and the theorem holds. If \(m\ge 2\), then \(\gcd(i,m)=1\) can only happen if \(1\le i\le m-1\), since \(\gcd(0,m)=\gcd(m,m)=m\ne 1\). So the theorem follows from Theorem \(\PageIndex{1}\) and the above remarks.

Theorem \(\PageIndex{3}\)

(\(U_m\) is a group\(^{1}\) under multiplication.)

1. If \([a],[b]\in U_m\) then \([a][b]\in U_m\).
2. For all \([a]\), \([b]\), \([c]\) in \(U_m\) we have \(([a][b])[c]=[a]([b][c])\).
3. \([1][a]=[a][1]=[a]\) for all \([a]\in U_m\).
4. For each \([a]\in U_m\) there is a \([b]\in U_m\) such that \([a][b]=[1]\).
5. For all \([a],[b]\in U_m\) we have \([a][b]=[b][a]\).

Proof

See Exercise \(\PageIndex{2}\).

Example \(\PageIndex{1}\)

Using Theorem \(\PageIndex{2}\) we see that \[\begin{split} U_{15} &=\{[1],[2],[4],[7],[8],[11],[13],[14]\} \\ &=\{[1],[2],[4],[7],[-7],[-4],[-2],[-1]\}. \end{split}\]

Note that using representatives for residue classes modulo \(15\) with the smallest possible absolute value simplifies multiplication somewhat. (It is easier to multiply by one of \(-1\), \(-2\), \(-4\) or \(-7\), usually, than to multiply by one of \(14\), \(13\), \(11\), or \(8\).) Rather than write out the entire multiplication table, we just find the inverse of each element of \(U_{15}\): \[\begin{aligned} [1][1] &=[1] \\ [2][-7] &=[2][8]=[1] \\ [4][4] &=[1] \\ [7][-2] &=[7][13]=[1] \\ [-4][-4] &=[11][11]=[1] \\ [-1][-1] &=[14][14]=[1].\end{aligned}\]

Corollary \(\PageIndex{1}\)

If \(m>0\), \[|U_m|=\phi(m),\nonumber \] where \(\phi\) denotes Euler’s totient function.

Recall that \(\phi\) was introduced in Section 1.15. Observe that

\(U_1\)	\(=\)	\(\{[1]\}\)	and	\(\phi(1)\)	\(=\)	\(1\)
\(U_2\)	\(=\)	\(\{[1]\}\)	and	\(\phi(2)\)	\(=\)	\(2-1=1\)
\(U_3\)	\(=\)	\(\{[1],[2]\}\)	and	\(\phi(3)\)	\(=\)	\(3-1=2\)
\(U_4\)	\(=\)	\(\{[1],[3]\}\)	and	\(\phi(4)\)	\(=\)	\(2^2-2^1 = 2\)
\(U_5\)	\(=\)	\(\{[1],[2],[3],[4]\}\)	and	\(\phi(5)\)	\(=\)	\(5-1=4\)
\(U_6\)	\(=\)	\(\{[1],[5]\}\)	and	\(\phi(6)\)	\(=\)	\((2-1)(3-1)=2\)
\(U_7\)	\(=\)	\(\{[1],[2],[3],[4],[5],[6]\}\)	and	\(\phi(7)\)	\(=\)	\(7-1=6\).

Exercises

Exercise \(\PageIndex{1}\)

Given \(m \geq 2\), show that \([1]\) and \([m-1]\) are always units in \(\mathbb{Z}_m\).

(Hint: Use the fact that \([m-1]=[-1]\).)

Exercise \(\PageIndex{2}\)

Prove Theorem \(\PageIndex{3}\).

Exercise \(\PageIndex{3}\)

List the elements of \(U_7\) in at least two different ways (i.e., using two different sets of representatives for the names) and find the inverse of each element, as in Example \(\PageIndex{1}\).

Exercise \(\PageIndex{4}\)

Find the sets \(U_m\), for \(8\le m\le 20\). Note that \(|U_m|=\phi(m)\). Use Theorem 1.15.6 to calculate \(\phi(m)\) and check that you have the right number of elements for each set \(U_m\), \(8\le m\le 20\).

Exercise \(\PageIndex{5}\)

Using the fact that \([3]\) and \([19]\) are elements of \(U_{20}\), use addition and multiplication of residue classes (NOT subtraction or division, which we have not defined) to solve the congruences for \([x]\) below. Assume that the modulus is \(m=20\).

1. \([3][x] + [11] = [4]\)
2. \([19][x] + [2] = [7]\)

Footnotes

[1] Actually (1){(4) are all that is required for \(U_n\) to be a group. Property (5) says that \(U_n\) is an Abelian group. See Appendix C.