Representations of Primitive roots Start by letting $p$ be an odd prime and let $\Pi_{i=1}^{k}$ $q_{i}^{\alpha_i}$ be the canonical factorization of $p-1$.
The goal is to show that every primitive root $g$ (mod $p$) has a representation in the form
$g\equiv \Pi_{i=1}^{k}$ $a_i$ (mod $p$), with $ord_{p}$ $a_i=q_{i}^{\alpha_i}$.
I was given two hints to this, each being a different method of approach.


*

*Count the residues of the form $\Pi_{i=1}^{k}$ $a_i$ (mod $p$), with $ord_p$$a_i=q_i^{\alpha_i}$.

*Let $Q_i=(p-1)/q_{i}^{\alpha_i}$ and pick $r_i$ satisfying $r_iQ_i \equiv 1$ (mod $q_i^{\alpha_i}$).  Then examine $g^{\Sigma_{i} r_iQ_i}$ (mod $p$).
The first one has to do with the idea of using a one-to-one correspondence and counting, whereas, the second one uses the idea of "divide and conquer" to solve this.  I cannot figure out either of them, especially when considering hint 1.  How do we even know that there exists residues of order $q_i^{\alpha_i}$ in the residue class of $p$?  Any light to help me understand?
 A: How do we know there are units of order $q_i^{\alpha_i}$ in the integers mod $p$? Why, hint #2 tells you how to explicitly construct them: given $Q_i=(p-1)q_i^{-\alpha_i}$ and $r_iQ_i\equiv1\bmod q_i^{\alpha_i}$, try to compute the order of $a_i=g^{r_{\large i} Q_{\large i}}$. Observe that $a_i^{q_{\large i}^{\alpha_{\large i}-1}}=g^{r_{\large i}(p-1)/q_{\large i}}\ne1$ since $q_i\nmid r_i$ but $a_i^{q_{\large i}^{\alpha_{\large i}}}=g^{r_{\large i}(p-1)}=1$.
Now use Sun-Ze (aka Chinese Remainder Theorem) to see that
$$r_iQ_i\equiv1 \bmod q_i^{\alpha_i}\implies \prod a_i=g^{\sum r_{\large i}Q_{\large i}}\equiv g.$$

Here is a structure-theoretic approach relying on basic finite abelian group theory.
The group of units mod $p$ is cyclic of order $p-1$. By SZ,
$$\frac{\bf Z}{(p-1){\bf Z}}\cong \frac{\bf Z}{q_1^{\alpha_1}{\bf Z}}\times\cdots\times\frac{\bf Z}{q_k^{\alpha_k}{\bf Z}}.$$
Group theory exercise: if $n=w_1\cdots w_k$ with $w_i$ pairwise coprime, then $g\in{\bf Z}/n{\bf Z}$ is a generator if and only if each $g_i$ is a generator for ${\bf Z}/w_i{\bf Z}$, where $g\leftrightarrow(g_1,\cdots,g_k)$ in accordance with the isomorphism ${\bf Z}/n{\bf Z}\cong{\bf Z}/w_1{\bf Z}\times\cdots\times{\bf Z}/w_k{\bf Z}$.
Now, $(g_1,\cdots,g_k)=(g_1,0,\cdots,0)(0,g_2,0,\cdots)\cdots(0,\cdots,0,g_k)$ is a decomposition of $g$ into a product of elements of orders $w_i$ as $i$ varies $1$ through $k$. So pull these $(0,\cdots,0,g_i,0,\cdots,0)$ elements back to the cyclic group ${\bf Z}/(p-1){\bf Z}$ and then back to the multiplicative group $({\bf Z}/p{\bf Z})^\times$.
The hints you have point toward an explicit construction of the elements that implicitly mirrors this structure-theoretic approach.
