Show that any cyclic group is abelian.
Show that every subgroup of a cyclic group is cyclic.
Show that \[\phi(n) = n \prod_{p\mid n}\qty{1 - {1\over p}}.\]
Compute \(\aut(\ZZ/n\ZZ)\) for \(n\) composite.
Compute \(\aut(\qty{\ZZ/p\ZZ}^n)\).
Solution
1. A cyclic group \(G=\langle g\rangle\) is abelian.
Any two elements are \(g^a,g^b\), and \(g^ag^b=g^{a+b}=g^bg^a\).
2. Every subgroup \(H\) of \(G=\langle g\rangle\) is cyclic.
If \(H=\{e\}\), then \(H=\langle e\rangle\). Otherwise \(H\) contains some \(g^k\) with \(k\neq0\), hence also \(g^{|k|}\), so let \(m\) be the least positive integer with \(g^m\in H\). For \(g^k\in H\), write \(k=qm+r\) with \(0\le r<m\); then \(g^r=g^k(g^m)^{-q}\in H\), so \(r=0\) by minimality. Hence \(H=\langle g^m\rangle\).
3. \(\phi(n)=|(\ZZ/n\ZZ)^\times|=n\prod_{p\mid n}\left(1-\frac1p\right)\).
For \(n=\prod_i p_i^{a_i}\), the Chinese remainder theorem gives \((\ZZ/n\ZZ)^\times\cong\prod_i(\ZZ/p_i^{a_i}\ZZ)^\times\). The nonunits of \(\ZZ/p^a\ZZ\) are the \(p^{a-1}\) multiples of \(p\), so \(|(\ZZ/p^a\ZZ)^\times|=p^a-p^{a-1}=p^a(1-1/p)\). Multiplying over the prime powers dividing \(n\) gives the formula.
4. \(\Aut(\ZZ/n\ZZ)\cong(\ZZ/n\ZZ)^\times\cong\prod_i(\ZZ/p_i^{a_i}\ZZ)^\times\), where\[(\ZZ/2^a\ZZ)^\times\cong\begin{cases}1,&a=1,\\ C_2,&a=2,\\ C_2\times C_{2^{a-2}},&a\ge3,\end{cases}\]and \((\ZZ/p^a\ZZ)^\times\) is cyclic of order \(p^{a-1}(p-1)\) for \(p\) odd.
An endomorphism of \(\ZZ/n\ZZ\) is multiplication by \(u=\varphi(1)\), and it is bijective exactly when \(u\) is a unit; composition corresponds to multiplication of the units. The product decomposition is step 3, For odd \(p\) there is a primitive root modulo \(p^a\); for \(a\ge3\), the class of \(5\) has order \(2^{a-2}\) modulo \(2^a\) and \((\ZZ/2^a\ZZ)^\times=\langle-1\rangle\times\langle5\rangle\). For composite \(n\) the group need not be cyclic, e.g. \(\Aut(\ZZ/8\ZZ)\cong C_2\times C_2\).
5. \(\Aut((\ZZ/p\ZZ)^n)\cong\operatorname{GL}_n(\FF_p)\), of order \(\prod_{i=0}^{n-1}(p^n-p^i)\).
A group homomorphism of \((\ZZ/p\ZZ)^n=\FF_p^n\) is additive, hence \(\FF_p\)-linear, so the automorphisms are the invertible \(\FF_p\)-linear maps. An invertible matrix is a choice of columns \(v_1,\dots,v_n\) with \(v_{i+1}\notin\operatorname{span}(v_1,\dots,v_i)\), which leaves \(p^n-p^i\) choices for \(v_{i+1}\).