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 18.2, \(\gcd(a,m)=1\).

To prove the converse, let \(\gcd(a,m)=1\). Then by Theorem 18.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\).

Note that from Theorem 18.6 we see 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.

Exercise \(\PageIndex{1}\)

Show that \([1]\) and \([m-1]\) are always units in \(\mathbb{Z}_m\).

Hint

\([m-1]=[-1]\).

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 A 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]\).

Exercise \(\PageIndex{2}\)

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

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 absolute least residue modulo \(15\) simplifies multiplication somewhat. Rather than write out the entire multiplication table, we just find the inverse of each element of \(U_{15}\): \[\begin{aligned} \left[1\right]\left[1\right]&=[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}\]

Exercise \(\PageIndex{3}\)

Find the elements of \(U_7\) in both least nonnegative and absolute least residue form and find the inverse of each element, as in the example above.

Definition \(\PageIndex{3}\)

If \(X\) is a set, the number of elements in \(X\) is denoted by \(|X|\).

Example \(\PageIndex{2}\)

\(|\{1\}|=1\), \(|\{0,1,3,9\}|=4\), \(|\mathbb{Z}_m|=m\) if \(m>0\).

Definition \(\PageIndex{4}\)

If \(m\ge 1\), \[\phi(m)=|\{i\in\mathbb{Z}\mid 1\le i\le m\text{ and }\gcd(i,m)=1\}|.\nonumber \] The function \(\phi\) is called the Euler phi function or the Euler totient function.

Corollary \(\PageIndex{1}\)

If \(m>0\), \[|U_m|=\phi(m).\nonumber\] Note that \[\begin{aligned} U_1 &=\{[1]\}\text{ so }\phi(1)=1 \\ U_2 &=\{[1]\}\text{ so }\phi(2)=1 \\ U_3 &=\{[1],[2]\}\text{ so }\phi(3)=2 \\ U_4 &=\{[1],[3]\}\text{ so }\phi(4)=2 \\ U_5 &=\{[1],[2],[3],[4]\}\text{ so }\phi(5)=4 \\ U_6 &=\{[1],[5]\}\text{ so }\phi(6)=2 \\ U_7 &=\{[1],[2],[3],[4],[5],[6]\}\text{ so }\phi(7)=6.\end{aligned}\]

Generally \(\phi(m)\) is not easy to calculate. However, the following theorems show that once the prime factorization of \(m\) is given, computing \(\phi(m)\) is easy.

Theorem \(\PageIndex{4}\)

If \(a>0\) and \(b>0\) and \(\gcd(a,b)=1\), then \[\phi(ab)=\phi(a)\phi(b).\nonumber\]

Theorem \(\PageIndex{5}\)

If \(p\) is prime and \(n>0\) then \[\phi\left(p^n\right)=p^n-p^{n-1}.\nonumber\]

Proof

We want to count the number of elements in the set \(A=\{1,2,\dotsc,p^n\}\) that are relatively prime to \(p^n\). Let \(B\) be the set of elements of \(A\) that have a factor \(>1\) in common with \(A\). Note that if \(b\in B\) and \(\gcd\left(b,p^n\right)=d>1\), then \(d\) is a factor of \(p^n\) and \(d>1\) so \(d\) has \(p\) as a factor. Hence \(b=pk\), for some \(k\), and \(p\le b\le p^n\), so \(p\le kp\le p^n\). It follows that \(1\le k\le p^{n-1}\). That is, \[B=\left\{p,2p,3p,\dotsc,kp,\dotsc,p^{n-1}p\right\}.\nonumber \] We are interested in the number of elements of \(A\) not in \(B\). Since \(|A|=p^n\) and \(|B|=p^{n-1}\), this number is \(p^n-p^{n-1}\). That is, \(\phi\left(p^n\right)=p^n-p^{n-1}\).

Theorem \(\PageIndex{6}\)

Let \(p_1,p_2,\dotsc,p_k\) be distinct primes and let \(n_1,n_2,\dotsc,n_k\) be positive integers, then \[\phi\left(p_1^{n_1}p_2^{n_2}\dotsm p_k^{n_k}\right)=\left(p_1^{n_1}-p_1^{n_1-1}\right)\dotsm\left(p_k^{n_k}-p_k^{n_k-1}\right).\nonumber \]

Before discussing the proofs of these three theorems, let’s illustrate their use:

\[\begin{gathered} \phi(12)=\phi\left(2^2\cdot 3\right)=\left(2^2-2^1\right)\left(3^1-3^0\right)=2\cdot 2=4 \\ \begin{split} \phi(9000)=\phi\left(2^3\cdot 5^3\cdot 3^2\right) &=\left(2^3-2^2\right)\left(5^3-5^2\right)\left(3^2-3^1\right) \\ &=4\cdot 100\cdot 6=2400. \end{split}\end{gathered}\] Note that if \(p\) is any prime then \[\phi(p)=p-1.\nonumber \]

I will sketch a proof of Theorem \(\PageIndex{4}\) in Exercise \(\PageIndex{6}\) below. Now I give the proof of Theorem \(\PageIndex{5}\).

The proof of Theorem \(\PageIndex{6}\) follows from Theorem \(\PageIndex{4}\) and Theorem \(\PageIndex{5}\). The proof is by induction on \(n\) and is quite similar to the proof of Theorem 14.1 (2), so I omit the details.

Exercise \(\PageIndex{4}\)

Find the sets \(U_m\), for \(8\le m\le 20\). Note that \(|U_m|=\phi(m)\). Use Theorem \(\PageIndex{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}\)

Show that if \[m=p_1^{n_1}p_2^{n_2}\dotsm p_k^{n_k}\nonumber \] where \(p_1,\dotsc,p_k\) are distinct primes and each \(n_i\ge 1\), then \[\phi(m)=m\left(1-\frac1{p_1}\right)\left(1-\frac1{p_2}\right)\dotsm\left(1-\frac1{p_k}\right).\nonumber \]

Exercise \(\PageIndex{6}\)

Let \(a\) and \(b\) be relatively prime positive integers. Write \(n=ab\). Define the mapping \(f\) by the rule \[f([x]_n) = ([x]_a,[x]_b).\nonumber \] Here we denote the residue class of \(x\) modulo \(m\) by \([x]_m\). First illustrate each of the following for the special case \(a=3\) and \(b=5\). Then prove each in general. (The proof is difficult and is optional.)

1. \(f : \mathbb{Z}_n \to \mathbb{Z}_a \times \mathbb{Z}_b\) is one-to-one and onto. (This is called the Chinese Remainder Theorem.)
2. \(f : U_n \to U_a \times U_b\) is also a one-to-one, onto mapping.
3. Conclude from (2) that \(\phi(ab) = \phi(a)\phi(b)\).

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