${\mathbb{Z}}_n^{*}$ is an example of a group. We won't formally introduce group theory, but we do point out that a group only deals with one operation, so the reason for the $*$ in ${\mathbb{Z}}_n^{*}$ is to stress that we are only considering mulitplication and forgetting about addition.

Notice we rarely add or subtract elements of ${\mathbb{Z}}_n^{*}$. For one thing, the sum of two units might not be a unit. We performed addition in our proof of Fermat's Theorem, but this can be avoided by using our proof of Euler's Theorem instead. We did need addition to prove that ${\mathbb{Z}}_n^{*}$ has a certain structure, but once this is done, we can focus on multiplication.

In this section, we shall see what we can be said from studying multiplication alone.

When ${\mathbb{Z}}_n^{*}$ has a generator, we call ${\mathbb{Z}}_n^{*}$ a cyclic group. If $g$ is a generator we write ${\mathbb{Z}}_n^{*}=⟨g⟩$.

A subgroup of ${\mathbb{Z}}_n^{*}$ is a subset $H$ of ${\mathbb{Z}}_n^{*}$ such that if $a,b\in H$, then $ab\in H$. Thus any subgroup contains $1$, and also the inverse of every element in the subgroup (why?).

Examples: Any $a\in {\mathbb{Z}}_n^{*}$ can be used to generate cyclic subgroup $⟨a⟩=\{a,a^2,...,a^d=1\}$ (for some $d$). For example, $⟨2⟩=\{\mathrm{2,4,1}\}$ is a subgroup of ${\mathbb{Z}}_7^{*}$. Any group is always a subgroup of itself. {1} is always a subgroup of any group. These last two examples are the improper subgroups of a group.

We prove Lagrange's Theorem for ${\mathbb{Z}}_n^{*}$. The proof can easily be modified to work for a general finite group.

Our proof of Euler's Theorem has ideas in common with this proof.

Theorem: Let $H$ be a subgroup of ${\mathbb{Z}}_n^{*}$ of size $m$. Then $m\mid \varphi (n)$.

Proof: If $H={\mathbb{Z}}_n^{*}$ then $m=\varphi (n)$. Otherwise, let $H=\{h_1,...,h_m\}$. let $a$ be some element of ${\mathbb{Z}}_n^{*}$ not in $H$, and consider the set $\{h_{1}a,...,h_{m}a\}$ which we denote by $Ha$. Every element in this set is distinct (since multiplying $h_{i}a=h_{j}a$ by $a^{-1}$ implies $h_i=h_j$), and furthermore no element of $Ha$ lies in $H$ (since $h_i=h_{j}a$ implies $a=h_j^{-1}{h}_i$ thus $a\in H$, a contradiction).

Thus if every element of ${\mathbb{Z}}_n^{*}$ lies in $H$ or $Ha$ then $2m=\varphi (n)$ and we are done. Otherwise take some element $b$ in ${\mathbb{Z}}_n^{*}$ not in $H$ or $Ha$. By a similar argument, we see that $Hb=\{h_{1}b,...,h_{m}b\}$ contains exactly $m$ elements and has no elements in common with either $H$ or $Ha$.

Thus iterating this procedure if necessary, we eventually have ${\mathbb{Z}}_n^{*}$ as the disjoint union of the sets $H,Ha,Hb,...$ where each set contains $m$ elements. Thus $m\mid \varphi (n)$. $\blacksquare$

Corollary: Euler's Theorem (and Fermat's Theorem). Any $a\in {\mathbb{Z}}_n^{*}$ generates a cyclic subgroup $\{a,a^2,...,a^d=1\}$ thus $d\mid \varphi (n)$, and hence $a^{\varphi (n)}=1$.

Theorem: All subgroups of a cyclic group are cyclic. If $G=⟨g⟩$ is a cyclic group of order $n$ then for each divisor $d$ of $n$ there exists exactly one subgroup of order $d$ and it can be generated by $a^{n/d}$.

Proof: Given a divisor $d$, let $e=n/d$. Let $g$ be a generator of $G$. Then $⟨g^e⟩=\{g^e,g^{2e},...,g^{de}=1\}$ is a cyclic subgroup of $G$ of size $n/d$.

Now let $H=\{a_1,...,a_{d-1},a_d=1\}$ be some subgroup of $G$. Then for each $a_i$, we have $a_i=g^k$ for some $k$. By Lagrange's Theorem the order of $a_i$ must divide $d$, hence $g^{kd}=1$.

Since the order of $g$ is $n$, we have $kd=mn=mde$ for some $m$. Thus $k=em$ and $a_i=(g^e{)}^m$, that is each $a_i$ is some power of $g^e$, hence $H$ is one of the subgroups we previously described. $\blacksquare$

Theorem: Let $G$ be cyclic group of order $n$. Then $G$ contains exactly $\varphi (n)$ generators.

Proof: Let $g$ be a generator of $G$, so $G=\{g,...,g^n=1\}$. Then $g^k$ generates $G$ if and only if $g^{km}=g$ for some $m$, which happens when $km=1(modn)$, that is $k$ must be a unit in ${\mathbb{Z}}_n$, thus there are $\varphi (n)$ values of $k$ for which $g^k$ is a generator. $\blacksquare$

Example: When ${\mathbb{Z}}_n^{*}$ is cyclic (i.e. when $n=\mathrm{2,4},p^k,2p^k$ for odd primes $p$), ${\mathbb{Z}}_n^{*}$ contains $\varphi (\varphi (n))$ generators.

We can now prove a theorem often proved using multiplicative functions:

Theorem: For any positive integer $n$

Proof: Consider a cyclic group $G$ of order $n$, hence $G=\{g,...,g^n=1\}$. Each element $a\in G$ is contained in some cyclic subgroup. The theorem follows since there is exactly one subgroup $H$ of order $d$ for each divisor $d$ of $n$ and $H$ has $\varphi (d)$ generators. $\blacksquare$

In an abstract sense, for every positive integer $n$, there is only one cyclic group of order $n$ which we denote by $C_n$. This is because once we have a generator $g$, we know $C_n=\{g,g^2,...,g^n=1\}$ and the behaviour of $C_n$ is completely determined by this.

Example: Both ${\mathbb{Z}}_3^{*}$ and ${\mathbb{Z}}_4^{*}$ are cyclic of order 2, so they both behave exactly like $C_2$ (when considering multiplication only). This is an example of a group isomorphism.

Example: For $n=2^k{p}_1^{k_1}...p_m^{k_m}$ for odd primes $p_i$, by the Chinese Remainder Theorem we have

Recall each ${\mathbb{Z}}_{p_i^{k_i}}^{*}$ is cyclic, and so are ${\mathbb{Z}}_2^{*}$ and ${\mathbb{Z}}_4^{*}$. Also recall for $k>2$ we have that $3\in {\mathbb{Z}}_{2^k}^{*}$ has order $2^{k-2}$ and no element has a higher order. Using some group theory this means the group structure of ${\mathbb{Z}}_n^{*}$ is

when $k=1,2$ and

when $k>2$.