Basic Number Theory 16: unit group structure in modular arithmetic

[Nick]

Let \(n\) be a positive integer. The set
\[ \mathbb{Z}/n\mathbb{Z}=\{\bar{0},\bar{1},\bar{2},\ldots,\overline{n-1}\} \]
of integers modulo \(n\) forms a group under addition modulo \(n\).
It does not form a group under multiplication modulo \(n\) (unless \(n=1\)) because not every element has a multiplicative inverse.
Those elements which do have such an inverse are called the units in the integers modulo \(n\), and the subset containing all the units
\[ \left(\mathbb{Z}/n\mathbb{Z}\right)^*
=\{\bar{a}\in\mathbb{Z}/n\mathbb{Z}:\gcd(a,n)=1\} \]
is a group under multiplication (modulo \(n\)).
Its order (i.e. the number of elements in the group) is \(\phi(n)\), where \(\phi\) is Euler's phi function (also known as Euler's totient function).
If we take a prime number \(p\), then every positive integer smaller than \(p\) is coprime to \(p\), so we get \(\phi(p)=p-1\) and
\[ \left(\mathbb{Z}/p\mathbb{Z}\right)^*=\{\bar{1},\bar{2},\bar{3},\ldots,
\overline{p-1}\}. \]
We saw last time that this is actually a cyclic group, i.e. there exists an integer \(a\) such that
\[ \left(\mathbb{Z}/p\mathbb{Z}\right)^*=\{\bar{a}^0=\bar{1},\bar{a}^1=\bar{a},
\bar{a}^2,\bar{a}^3,\ldots, \bar{a}^{p-2}\}. \]
Such an integer \(a\) is called a primitive root modulo \(p\).
We have proved that a primitive root modulo \(p\) exists for every prime number \(p\), but there is no simple method known for finding them.
(For relatively small prime numbers, we can just try all possibilities, of course.)

The next logical step is to analyze the structure of \(\left(\mathbb{Z}/p^m\mathbb{Z}\right)^*\), i.e. the units in the integers modulo \(p^m\) where \(p\) is a prime number and \(m\) any positive integer.
Once we understand this, the Chinese Remainder Theorem immediately shows how the units fit together in \(\left(\mathbb{Z}/n\mathbb{Z}\right)^*\) for all positive integers \(n\).

Let \(a,b\) be any numbers. You are probably familiar with the following equations:
\[\begin{eqnarray*}
(a+b)^2 & = & a^2+2ab+b^2 \\
(a+b)^3 & = & a^3+3a^2b+3ab^2+b^3 \\
(a+b)^4 & = & a^4+4a^3b+6a^2b^2+4ab^3+b^4 \\
(a+b)^5 & = & a^5+5a^4b+10a^3b^2+10a^2b^3+5ab^4+b^5 \\
& \vdots &
\end{eqnarray*}\]
The constants involved come from Pascal's triangle, in which each entry is the sum of the two entries directly above it (left and right).

More formally, for each non-negative integer \(n\), we define \(n\) factorial, written \(n!\), by
\[ n!=1\cdot 2\cdot 3\cdot\ldots\cdot n \]
Thus \(0!=1\) (the product of no integers is defined to be 1), \(1!=1\), \(2!=1\times 2=2\), \(3!=1\cdot 2\cdot 3=6\), \(4!=1\cdot 2\cdot 3\cdot 4=24\), etc.
For any integers \(r,n\) with \(0\leq r\leq n\), we then define
\[ \binom{n}{r}=\frac{n!}{r!(n-r)!}. \]
Take any non-negative integer \(n\).
From the above definition, we immediately get \(\binom{n}{0}=1\) and \(\binom{n}{n}=1\).
And for any integer \(r\) with \(0<r<n\) we also have
\[\begin{eqnarray*}
\binom{n-1}{r-1}+\binom{n-1}{r}
& = & \frac{(n-1)!}{(r-1)!(n-r)!}+\frac{(n-1)!}{r!(n-1-r)!} \\
& = & \frac{r((n-1)!)+(n-r)((n-1)!)}{r!(n-r)!} \\
& = & \frac{n!}{r!(n-r)!}=\binom{n}{r}
\end{eqnarray*}\]
(the Pascal triangle property).
In particular, it follows for all integers \(r,n\) with \(0\leq r\leq n\) that \(\binom{n}{r}\) is a positive integer (even though we used a fraction in the definition).
For any numbers \(a,b\), the well known binomial theorem (or binomial expansion) states that
\[ (a+b)^n=\sum_{i=0}^n\binom{n}{i}a^{n-i}b^i
=a^n+na^{n-1}b+\binom{n}{2}a^{n-2}b^2+\binom{n}{3}a^{n-3}b^3
+\ldots +\binom{n}{n-1}ab^{n-1}+b^n \]
(you can prove this by induction on \(n\) if you have not seen it before).

Lemma 91
Let \(p\) be a prime number. Then, for all integers \(r\) with \(0<r<p\), \(\binom{p}{r}\) is divisible by \(p\).

proof
Take any integer \(r\) with \(0<r<p\).
Then \(p\) divides \(p!\) but \(p\) does not divide \(r!\) (since \(r<p\) and \(p\) is prime) and it doesn't divide \((p-r)!\) either (since \(p-r<p\) too)
hence \(p\) divides \(\frac{p!}{r!(p-r)!}=\binom{p}{r}\). ∎

Lemma 92
Let \(p\) be a prime number and \(m\) a positive integer.
For all integers \(a,b\), if \(a\equiv b\pmod{p^m}\) then \(a^p\equiv b^p\pmod{p^{m+1}}\).

proof
For any integers \(a,b\), if \(a\equiv b\pmod{p^m}\) then \(a=b+cp^m\) for some integer \(c\) and
\[ a^p=(b+cp^m)^p=b^p+pb^{p-1}cp^m+\binom{p}{2}b^{p-2}(cp^m)^2+\ldots
+pb(cp^m)^{p-1}+(cp^m)^p. \]
Now \(p^{m+1}|pb^{p-1}cp^m\) and, for each \(i\in\{2,3,\ldots,p\}\), we have \(im\geq m+m\geq m+1\) (as \(m\geq 1\))
so \(p^{m+1}|\binom{p}{i}b^{p-i}(cp^m)^i\), hence \(a^p\equiv b^p\pmod{p^{m+1}}\). ∎

Lemma 93
Let \(p\) be an odd prime number and \(m\geq 2\) an integer.
Then, for all integers \(a\),
\[ (1+ap)^{p^{m-2}}\equiv 1+ap^{m-1}\pmod{p^m}. \]

proof
Take any integer \(a\).
Induction on \(m\).
In the case \(m=2\), both sides of the equation are just \(1+ap\).
Take any integer \(N>2\) and suppose the lemma holds for all \(n<N\).
In the case \(n=N\), by our assumption we have \((1+ap)^{p^{m-3}}\equiv 1+ap^{m-2}\pmod{p^{m-1}}\),
so by lemma 92 we get \((1+ap)^{p^{m-2}}\equiv (1+ap^{m-2})^p\pmod{p^{m}}\),
and \((1+ap^{m-2})^p=1+pap^{m-2}+\binom{p}{2}(ap^{m-2})^2+\ldots +p(ap^{m-2})^{p-1}+(ap^{m-2})^p\).
For each \(i\in\{2,3,\ldots,p-1\}\), \(p|\binom{p}{i}\) by lemma 91,
and \(i(m-2)\geq m+m-4\geq m-1\) (since \(i\geq 2\) and \(m\geq 3\))
so \(p^m|\binom{p}{i}(ap^{m-2})^i\).
Also \(p(m-2)\geq m+2m-6\geq m\) (as \(p\geq 3\), \(m\geq 3\))
so \(p^m|(ap^{m-2})^p\) too.
Hence \((1+ap)^{p^{m-2}}\equiv 1+pap^{m-2}=1+ap^{m-1}\pmod{p^m}\).
The result follows by mathematical induction. ∎

Lemma 94
Let \(p\) be an odd prime number and \(m\geq 2\) an integer.
Then, for all integers \(a\) not divisible by \(p\), \(\overline{1+ap}\) has order \(p^{m-1}\) in the group \(\left(\mathbb{Z}/p^m\mathbb{Z}\right)^*\).

proof
Take any integer \(a\) not divisible by \(p\).
Then
\[\begin{eqnarray*}
(1+ap)^{p^{m-1}} & \equiv & (1+ap^{m-1})^p\pmod{p^m} \\
& \equiv & 1^p=1\pmod{p^m}
\end{eqnarray*}\]
by lemma 93 then lemma 92, so \(\overline{1+ap}\) is a unit in the integers modulo \(p^m\) and its order divides \(p^{m-1}\) (proposition 75).
And, by lemma 93 again, \((1+ap)^{p^{m-2}} \equiv 1+ap^{m-1}\not\equiv 1\pmod{p^m}\) since \(a\) is not divisible by \(p\),
hence \(\overline{1+ap}\) has order \(p^{m-1}\). ∎

The following two propositions answer the question we are considering
(we have to treat 2 separately from all the other prime numbers).

Proposition 95
For all odd prime numbers \(p\) and all positive integers \(m\),
the unit group \((\mathbb{Z}/p^m\mathbb{Z})^*\) of the integers modulo \(p^m\) is cyclic.

proof
In the case \(m=1\), we proved this in theorem 90.
Suppose \(m\geq 2\).
We claim there exists an integer \(b\) such that \(\bar{b}\in(\mathbb{Z}/p\mathbb{Z})^*\) has order \(p-1\) but \(b^{p-1}\not\equiv 1\pmod{p^2}\).
As \((\mathbb{Z}/p\mathbb{Z})^*\) is cyclic (theorem 90 again), there exists an integer \(a\) such that \(\bar{a}\in(\mathbb{Z}/p\mathbb{Z})^*\) has order \(\phi(p)=p-1\).
In particular, \(a\) is not divisible by \(p\).
If \(a\not\equiv 1\pmod{p^2}\) then taking \(b=a\) suffices.
If instead \(a\equiv 1\pmod{p^2}\), let \(b=a+p\).
Then in \((\mathbb{Z}/p\mathbb{Z})^*\) we have \(\bar{b}=\bar{a}\) so \(\bar{b}\) has order \(p-1\).
And
\[\begin{eqnarray*}
b^{p-1} & = & (a+p)^{p-1}\equiv a^{p-1}+(p-1)a^{p-2}p\pmod{p^2} \\
& \equiv & 1+(p-1)a^{p-2}p\pmod{p^2} \\
& \not\equiv & 1\pmod{p^2}
\end{eqnarray*}\]
since \(a\) is not divisible by \(p\). This proves the claim.

Now \(b\) is not divisible by \(p\), so \(\bar{b}\) is a unit in \(\mathbb{Z}/p^m\mathbb{Z}\).
Let \(n\geq 1\) be its order in this group (which is finite since the group is finite).
Then \(b^n\equiv 1\pmod{p^m}\) so \(b^n\equiv 1\pmod{p}\) too, and \(\bar{b}\) has order \(p-1\) in \((\mathbb{Z}/p\mathbb{Z})^*\)
so \(p-1|n\) (proposition 75).
Also \(b^{p-1}\equiv 1\pmod{p}\) so \(b^{p-1}=1+cp\) for some integer \(c\),
and \(b^{p-1}\not\equiv 1\pmod{p^2}\) so \(p\) does not divide \(c\).
By lemma 94, \(\overline{1+cp}\) has order \(p^{m-1}\) in the group \(\left(\mathbb{Z}/p^m\mathbb{Z}\right)^*\).
And \((1+cp)^n=b^{n(p-1)}\equiv 1\pmod{p^m}\) so \(p^{m-1}|n\).
Thus \(p-1\) and \(p^{m-1}\) are coprime and each divide \(n\),
so \(\phi(p^m)=(p-1)p^{m-1}\) divides \(n\).
But \(n|\phi(p^m)\) as well (corollary 84) so \(n=\phi(p^m)\) (proposition 2)
hence \((\mathbb{Z}/p^m\mathbb{Z}\) is cyclic, generated by \(\bar{b}\). ∎

Proposition 96
Let \(m\geq 3\) be an integer.
Then
\[ \left(\mathbb{Z}/2^m\mathbb{Z}\right)^*
=\{\bar{1},\bar{5},\bar{5}^2,\bar{5}^3,\ldots,\bar{5}^{2^{m-2}-1},
-\bar{1},-\bar{5},-(\bar{5}^2),-(\bar{5}^3),\ldots,-(\bar{5}^{2^{m-2}-1}) \} \]
and all the elements listed above are distinct.

proof
We claim
\[ 5^{2^{m-3}}\equiv 1+2^{m-1}\pmod{2^m}. \]
Induction on \(m\).
In the case \(m=3\), we have \(5=1+2^2\).
Take any \(M>3\) and suppose the claim holds for all \(m<M\).
In the case \(m=M\), by our assumption and lemma 92,
\[ 5^{2^{m-3}}\equiv (1+2^{m-2})^2\equiv 1+2^{m-1}\pmod{2^m} \]
since \(2(m-2)=m+m-4\geq m\).
The claim follows by mathematical induction.

Thus \(5^{2^{m-3}}\not\equiv 1\pmod{2^m}\)
but \(5^{2^{m-2}}\equiv (1+2^{m-1})^2\equiv 1\pmod{2^m}\) since \(2(m-1)=m+(m-2)> m\),
so \(\bar{5}\) has order \(2^{m-2}\) in the group \((\mathbb{Z}/2^m\mathbb{Z})^*\),
and it follows that the first \(2^{m-2}\) elements listed are distinct (proposition 75).
Also, for any integer \(n\), if \(5^n\equiv -1\pmod{2^m}\) then \(5^n\equiv -1\pmod{4}\), but \(5^n\equiv 1\pmod{4}\), a CONTRADICTION.
It follows that all \(2^{m-1}\) elements listed are distinct.
As \(\phi(2^m)=2^{m-1}\), these are all the elements of \((\mathbb{Z}/2^m\mathbb{Z})^*\). ∎

To see more clearly what this tells us, we introduce an important concept.
Let \(G,H\) be groups. An isomorphism from \(G\) to \(H\) is a function
\(f:G\rightarrow H\) such that \(f\) is bijective and, for all \(x,y\in G\), \(f(xy)=f(x)f(y)\).
More informally, \(f\) pairs the elements of \(G\) off with the elements of \(H\) and preserves the binary operation:
if \(xy=z\) in \(G\) then \(f(x)f(y)=f(z)\) in \(H\).
We say \(G\) is isomorphic with \(H\), and write \(G\cong H\), if there exists an isomorphism from \(G\) to \(H\).

Example
Here are the addition table for the integers modulo 6
and the multiplication table for the units in the integers modulo 7.

Addition modulo 6    Multiplication modulo 7
   0 1 2 3 4 5          1 2 3 4 5 6
  ┏━━━━━━━━━━━━        ┏━━━━━━━━━━━━
0 ┃0 1 2 3 4 5       1 ┃1 2 3 4 5 6
1 ┃1 2 3 4 5 0       2 ┃2 4 6 1 3 5
2 ┃2 3 4 5 0 1       3 ┃3 6 2 5 1 4
3 ┃3 4 5 0 1 2       4 ┃4 1 5 2 6 3
4 ┃4 5 0 1 2 3       5 ┃5 3 1 6 4 2
5 ┃5 0 1 2 3 4       6 ┃6 5 4 3 2 1

In the second table, if we write the numbers in the order 1,3,2,6,4,5 instead of 1,2,3,4,5,6, we get the following:

Multiplication modulo 7
   1 3 2 6 4 5
  ┏━━━━━━━━━━━━
1 ┃1 3 2 6 4 5
3 ┃3 2 6 4 5 1
2 ┃2 6 4 5 1 3
6 ┃6 4 5 1 3 2
4 ┃4 5 1 3 2 6
5 ┃5 1 3 2 6 4

This table has the same pattern as the first one: take the table for addition modulo 6 and replace every occurrence of 0 with 1 and (simultaneously) replace every 1 with 3 and every 3 with 6, and you get the table for multiplication modulo 7 (with rows and columns in this order).
Thus \(\mathbb{Z}/6\mathbb{Z}\) is isomorphic with \((\mathbb{Z}/7\mathbb{Z})^*\).
Properties of the first group which depend solely on its addition automatically translate to properties about the second group and its multiplication.
For example, \((\mathbb{Z}/7\mathbb{Z})^*\) has an element of order 6 because \(\mathbb{Z}/6\mathbb{Z}\) has an element of order 6.
If we are only interested in their properties as groups, then there is no need to distinguish between them, and they can be viewed as two concrete instances of the same underlying, abstract group.

Proposition 97
The relation \(\cong\) is an equivalence relation on any set of groups.

proof
For any group \(G\), the identity function \(i_G:G\rightarrow G,x\mapsto x\) is an isomorphism so \(G\cong G\).
Take any groups \(G,H\) and suppose \(G\cong H\).
Then there exists an isomorphism \(f:G\rightarrow H\).
In particular, \(f\) is bijective so it has an inverse \(f^{-1}:H\rightarrow G\) (proposition 25) and \(f^{-1}\) is also bijective (corollary 27).
Take any \(x,y\in H\) and let \(a=f^{-1}(x)\) and \(b=f^{-1}(y)\).
Then \(f(a)=x\) and \(f(b)=y\), and\(f\) is an isomorphism so
\[ f^{-1}(xy)=f^{-1}(f(a)f(b))=f^{-1}(f(ab))=ab=f^{-1}(x)f^{-1}(y). \]
Hence \(f^{-1}\) is also an isomorphism and therefore \(H\cong G\).
Finally, take any groups \(G,H,K\), and suppose \(G\cong H\) and \(H\cong K\).
Then there exist isomorphisms \(f:G\rightarrow H\) and \(g:H\rightarrow K\).
In particular, \(f,g\) are each bijective so their composition \(g\circ f:G\rightarrow K\) is also bijective (exercise 29).
And, for any \(x,y\in G\),
\[ (g\circ f)(xy)=g(f(xy)=g(f(x)f(y))=g(f(x))g(f(y))=(g\circ f)(x)(g\circ f)(y)
\]
so \(g\circ f\) is an isomorphism and \(G\cong K\). ∎

Proposition 98
Any two cyclic groups of the same finite order are isomorphic.

proof
Let \(n\) be a positive integer, \(G\) a cyclic group of order \(n\) generated by \(g\in G\) and \(H\) also a cyclic group of order \(n\), generated by \(h\in H\).
Define \(f:G\rightarrow H\) as follows: for each \(x\in G\), there exists an integer \(i\) such that \(x=g^i\), and we define \(f(x)=h^i\in H\).
This is well-defined since, for any integers \(i,j\), if \(g^i=g^j\) then \(n\) divides \(i-j\) so \(h^i=h^j\) as well (proposition 75).
It is injective since, for all integers \(i,j\), if \(h^i=h^j\) then \(n\) divides \(i-j\) so \(g^i=g^j\) too.
And for each \(y\in H\) there exists an integer \(i\) such that \(y=h^i\), so \(f(g^i)=y\) and therefore \(f\) is surjective too, making it bijective.
For any \(x,y\in G\), \(x=g^i\) and \(y=g^j\) for some integers \(i,j\),
and \(f(xy)=f(g^{i+j})=h^{i+j}=h^ih^j=f(x)f(y)\) hence \(f\) is an isomorphism from \(G\) to \(H\). ∎

Thus, if we are only concerned with group properties, we may speak of the cyclic group of order \(n\), for any positive integer \(n\).

For any groups \(G,H\), we may form the Cartesian product \(G\times H\), which is the set of all ordered pairs \((g,h)\) where \(g\in G\) and \(h\in H\).
We may turn this set into a group by defining a binary operation on it: \((g_1,h_1)(g_2,h_2)=(g_1g_2,h_1h_2)\), i.e. we apply the existing binary operation of \(G\) to combine the first coordinates, and the binary operation of \(H\) for the second coordinates.
The resulting group is called the direct product of \(G\) with \(H\).

Now we can return to proposition 96.
Let \(m\geq 3\) be an integer.
Then the unit group \((\mathbb{Z}/2^m\mathbb{Z})^*\) of the integers modulo \(2^m\) has a subgroup \(G=\{-\bar{1},\bar{1}\}\), which is cyclic of order 2, generated by \(-\bar{1}\),
and also a subgroup \(H=\{\bar{5}^i:i\in\mathbb{Z}\}\) which is cyclic of order \(2^{m-2}\), generated by \(\bar{5}\).
Proposition 96 tells us that the unit group \((\mathbb{Z}/2^m\mathbb{Z})^*\) is isomorphic with the direct product \(G\times H\) of these 2 cyclic subgroups.

Let \(n=p^sq^t\) where \(p,q\) are distinct prime numbers and \(s,t\) positive integers.
By the Chinese Remainder Theorem (theorem 29), the integers modulo \(n\) behave exactly like ordered pairs of integers \((a,b)\) where the first coordinate is taken modulo \(p^s\) and the second coordinate modulo \(q^t\).
In particular, \((a,b)\) is a unit if (and only if) \(a\) is a unit in the integers modulo \(p^s\) and \(b\) is a unit modulo \(q^t\).
It follows that the unit group \((\mathbb{Z}/n\mathbb{Z})^*\) is isomorphic with the direct product \((\mathbb{Z}/p^s\mathbb{Z})^*\times (\mathbb{Z}/q^t\mathbb{Z})^*\).
And we know how these behave by propositions 95 and 96, so we can deduce how the unit group of the integers modulo \(n\) is built out of cyclic groups.
More generally, if \(n\) is a product of more than 2 distinct prime numbers, we can apply the Chinese Remainder Theorem more than once, and in this way we can analyze the unit group of the integers modulo \(n\) for any positive integer \(n\).


Exercises
75. List the element(s) of \((\mathbb{Z}/2\mathbb{Z})^*\) and of \((\mathbb{Z}/4\mathbb{Z})^*\) (the only cases not covered by propositions 95 and 96).
76. Find all the primitive roots modulo 11.
77. Show that any two infinite cyclic groups are isomorphic.
78. Let \(p\) be a prime number such that \(p\equiv 1\pmod{4}\). Show that, for any integer \(a\), \(a\) is a primitive root modulo \(p\) if and only if \(-a\) is a primitive root modulo \(p\).