What's a fast, elementary way to show $(\mathbb{Z}/16 \mathbb{Z})^{\times} \cong C_4 \times C_2$? I'm asking this question because in general I'd like to know if there's a nice way to tell what abelian group $(\mathbb{Z}/n \mathbb{Z})^{\times}$ is isomorphic to quickly.
Currently, my best method is this: $|(\mathbb{Z}/16 \mathbb{Z})^{\times}|=\varphi(16)=8$, hence $(\mathbb{Z}/16 \mathbb{Z})^{\times}$ is an abelian group of order $8$.
It has no element of order $8$ by Gauss' theorem classifying when $(\mathbb{Z}/n \mathbb{Z})^{\times}$ is cyclic. Rule out $C_8$.
It has an element of order $4$: $3^2=9 \neq 1, 9^2=1$. Rule out $C_2 \times C_2 \times C_2$.
Hence, it's $C_4 \times C_2$.
Using Gauss' theorem seems like quite high technology, so what's an elementary way to do the part "no no element of order $8$"? I could check all of them, but that's quite long.
Or is there a faster, completely different way?
Best Answer
Theorem. Let $n\geq 3$. Then $5$ has order $2^{n-2}$ modulo $2^n$ and $2^{n}$ is the largest power of $2$ that divides $5^{2^{n-2}}-1$.
Proof. We proceed by induction. For $n=3$, $5\not\equiv 1\pmod{8}$, but $5^2=25\equiv 1\pmod{8}$. Note moreover that $2^3\Vert 5^2-1$.
Assume $5$ has order $2^{n-2}$ modulo $2^n$ and that $2^{n}\Vert (5^{2^{n-2}}-1)$. Then $5^{2^{n-2}}= 1+k2^{n}$ for some odd integer $k$, but $5^{2^{n-2}}\not\equiv 1\pmod{2^{n+1}}$.
Squaring we get $$5^{2^{n-1}} = (1+k2^n)^2 = 1 + k2^{n+1}+2^{2n}\equiv 1\pmod{2^{n+1}},$$ so the order of $5$ modulo $2^{n+1}$ divides $2^{n-1}$, and is greater than $2^{n-2}$; thus, the order is precisely $2^{n-1}$. In addition, since $k$ is odd the largest power of $2$ that divides $5^{2^{n-1}}-1 = 2^{n+1}(k+2^{n-1})$ is $2^{n+1}$, completing the induction. $\Box$
Now note that all the powers of $5$ modulo $2^n$ are congruent to $1$ modulo $4$; The elements $-5$, $-(5^2),\ldots,-(5^{2^{n-2}})$ are all congruent to $3$ modulo $4$ and pairwise incongruent. In particular, there are two elements of order $2$ in $(\mathbb{Z}/2^n\mathbb{Z})^{\times}$, namely $5^{2^{n-3}}$ and $-5^{2^{n-3}}$. So $(\mathbb{Z}/2^n\mathbb{Z})^{\times}$ cannot be cyclic.
Since $(\mathbb{Z}/2^n)^{\times}$ has order $2^{n-1}$, is abelian, is not cyclic for $n\geq 3$, and has an element of order $2^{n-2}$, it follows that it is isomorphic to $C_{2^{n-2}}\times C_2$.