Remark. A well known fact is that \(\mathbb{Z}_p^{*}\), the multipicative group of the integers modulo \(p\), is cyclic, i.e., has a generator.
For a short proof, recall that the number of elements of order \(d\) in a group is at most the number of solutions to \[x^{d}\equiv 1 \mod p,\] which is at most \(\phi(d)\). So we have: \[p\le \sum_{d\mid (p-1)} \phi(d).\]
On the other hand, for any \(n\) we have \[\sum_{d\mid n} \phi(d) = n\] which can be seen by noting that \(\Pr_{x\gets[n]}[gcd(n,x) = \frac{n}{d}] = \phi(d)\) which can be seen by listing the things which have \(\frac{n}{d} \mid gcd(n,x)\), namely \(\frac{n}{d},\frac{2n}{d},\frac{3n}{d}\ldots, \frac{dn}{d}\) and then crossing out the ones which have additional divisors beyond \(d\). Anyways, this means that the number of elements of order \(d\mid (p-1)\) is really \(\phi(d)\) for each \(d\mid (p-1)\).
Anyways, but that’s not what I want to talk about.
Remark. Another well-known fact is that for \(p\neq q\) odd primes the group \(\mathbb{Z}_{pq}^{*}\) is not cyclic.
proof:
\(g^{\lcm(p-1,q-1)}\equiv 1\) for any \(g\in \mathbb{Z}_{pq}^{*}\) but \(\lcm(p-1,q-1)<(p-1)(q-1)\).
Maybe one day I’ll think about even numbers. But for today lets assume they don’t exist.
Theorem. The group \(Z_{p^{k}}^{*}\) is cyclic.
Proof. We proceed by induction. The base case will be \(k=2\). For \(k=2\) we have that \(|\mathbb{Z}_{p^{2}}^{*}| = p(p-1)\). Let \(\gamma\) be a generator for \(\mathbb{Z}_p^{*}\), we showed above that this exists. Then \(p-1 \mid ord_{p^{2}}(\gamma)\), where \(ord_{p^{2}}\) denotes the order of an element in \(\mathbb{Z}_{p^{2}}^{*}\).
Also observe \(ord_{p^{2}}(1+p) \equiv 0 \mod p.\)
But then \((1+p)\gamma\) has order \(p(p-1)\). Proof of this claim: imagine \(p\mid ord(x),p-1\mid ord(y)\). Then \((xy)^{p}\notequiv 1, (xy)^{p-1}\notequiv 1\). Hence \(ord(xy)= p(p-1)\).
Now we consider \(k>2\) by induction. To be continued after the semester ends…