Why multiplicative group $\mathbb{Z}_n^*$ is not cyclic for $n = 2^k$ and $k \ge 3$

Solution 1:

An element $a\in\mathbb{Z}/n\mathbb{Z}$ is a unit if and only if $(a,n)=1$, that is, if and only if $a$ and $n$ are relatively prime. In your case, since the only prime divisor of $n=2^k$ is $2$, this equivalence reduces to $a$ is a unit if and only if $a$ is odd. Hence, the elements of $(\mathbb{Z}/2^k\mathbb{Z})^*$ are $$1,3,5,7,\ldots,2^k-5,2^k-3,2^k-1$$ of which there are $2^{k-1}$, or just half of $2^k$ because we are only taking odd elements. Now $(\mathbb{Z}/2^k\mathbb{Z})^*$ is not cyclic for $k\ge 3$ (read here, which states that $(\mathbb{Z}/2^k\mathbb{Z})^*\cong\mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/2^{k-2}\mathbb{Z}$). It follows that any element $a$ must have order less than $2^{k-1}$, but still dividing $2^{k-1}$, and hence must be no larger than $2^{k-2}$.

Solution 2:

If we simply want to show that the multiplicative group $G = \Bbb{Z}_{2^k}^*$ is not cyclic for $k \ge 3$ (which is all that is needed to conclude the order of any element is strictly less than the order of group $G$), then we can verify it first for the case $k = 3$ as Jared's original comment points out: $\Bbb{Z}_8^*$ is isomorphic to the product of two cyclic groups of order two (and has no element of order 4).

Then for $k \gt 3$ one verifies that the natural ring homomorphism from $\Bbb{Z}_{2^k}$ onto $\Bbb{Z}_8$ (taking the coarser congruence relation) induces a group homomorphism of the respective multiplicative groups (the groups of units of the respective rings). From this we see that $\Bbb{Z}_{2^k}^*$ cannot be cyclic, since the quotient group of a cyclic group is again cyclic.

The specific structure of $\Bbb{Z}_{2^k}^*$ can be worked out from the fact that it has two cyclic factors, $C_2 \times C_{2^{k-2}}$, with a generator for the second factor being 3 in all orders ($k \ge 3$). A write-up in terms of "primitive roots" is given here in Lemma 12, where it is shown by induction that for any odd $a$:

$$ k \ge 3 \implies a^{2^{k-2}} \equiv 1 \mod 2^k $$