<s>[INST] What are the generators of $\mathbb{Z}_9^*$? I am to understand that $\mathbb{Z}_9^*$ is cyclic because $9=3^2$, where $3^2$ is of the form $p^{\alpha}$, with $p$ an odd prime... but I can't find any generators for the set...
$|\mathbb{Z}_9^*|=6$, and $\mathbb{Z}_9^*=\{\overline{1},\overline{2},\overline{4},\overline{5},\overline{7},\overline{8}\}$
Using a table:
\begin{array}{c|cccccc}
\cdot & 1 & 2 & 4 & 5 & 7 & 8 \\\hline
1 & 1 & 1 & 1 & 1 & 1 & 1 \\
2 & 2 & 4 & 7 & 5 & 2 & 4 \\
4 & 4 & 7 & 4 & 7 & 4 & 7 \\
5 & 5 & 7 & 4 & 2 & 1 & 5 \\
7 & 7 & 4 & 7 & 4 & 7 & 4 \\
8 & 8 & 1 & 8 & 1 & 8 & 1 \\
\end{array}
I'm not sure if I'm misunderstanding the definition of a generator, but since I'm assuming that $\mathbb{Z}_9^*$ is cyclic, it should have $\varphi(\varphi(9))=2$ generators... but I can't find a single one.
 [/INST] When you are looking for generators, a trick to reduce the work is to note that, once you know that $a$ is not a generator, then neither is any power $a^i$. So in your case you'd start by testing $2$ rather than $2^2=4$ or $2^3=8$.
A good way to check $a$ is a generator module ${\mathbb Z}_{p^k}^\times$ is to check whether $a^{\phi(p^k) / q} \not\equiv 1(\bmod. p^k)$ for each prime $q$ dividing $\phi(p^k)$. In thi scase, you can check $2$ is a generator.
More generally, $2$ is a generator of ${\mathbb Z}_{3^k}^{\times}$ for each $k=1,2,3\ldots$. The proof goes as follows:
Lemma: $2^{2\times 3^{k-1}} = 3^k \times q + 1$ for some $q\in {\mathbb Z}$ with $3 \not | q$.
Proof: For $k=1$ this is trivial, indeed $2^2 = 3\times 1 + 1$ and clearly $3\not | 1$.
Assume the result to hold for some $k$, now for $k+1$ we note that:
\begin{align} 2^{2^\times 3^k} = \left(2^{2\times 3^{k-1}} \right)^3 = (3^k \times q + 1)^3 &= 3^{3k} q^3 + 3 \times 3^{2k} q^2 + 3 \times 3^k q + 1 \end{align}
which is of the form $3^{k+1} q^\prime + 1$ where $q^\prime = 3^{2k-1} q^3 + 3^{k}q^2 + q$, now since $3 \not | q$ and $k\geq 1$, we get that $3\not | q^\prime$, finishing the induction. $\square$
Now, with this lemma, note that if the order of $2$ modulo $3^k$ were not $\phi(3^k) = 2 \times 3^{k-1}$, then it'd either divide $2\times 3^{k-2}$ or $3^{k-1}$ (by taking out one prime factor from each, this is the "least we can take out"). The latter is impossible since $2^{3^{k-1}} \equiv -1 (\bmod. 3)$ and so $2^{3^{k-1}} \equiv 1 (\bmod. 3^k)$ is impossible since it'd imply  $2^{3^{k-1}} \equiv 1 (\bmod. 3)$.
So, suppose the order of $2$ were $2\times 3^{k-2}$, we showed a moment ago that $2^{2\times 3^{k-2}} = 3^{k-1} \times q + 1$ where $3\not | q$, so $2^{2\times 3^{k-2}} \equiv 1(\bmod. 3^{k})$ is impossible since it would imply $3^{k-1} \times q \equiv 0(\bmod. 3^k)$ yet $3\not | q$.
</s>