The unit group \((\mathbb Z/n\mathbb Z)^\times\) controls invertible residues. Euler's function gives its order; primitive roots ask when this finite abelian group is cyclic.
Euler's function
Theorem. \[ \varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right). \]
Proof. For \(n=p^\alpha\), exactly \(p^{\alpha-1}\) residue classes are divisible by \(p\), so \(\varphi(p^\alpha)=p^\alpha-p^{\alpha-1}\). The Chinese remainder theorem shows that \(\varphi\) is multiplicative. Multiply the prime-power formulas.
The order \(\operatorname{ord}_n(a)\) of a unit \(a\) is the least positive \(k\) with \(a^k\equiv1\pmod n\). Lagrange's theorem gives \[ \operatorname{ord}_n(a)\mid\varphi(n). \]
Cyclic groups modulo primes
Theorem. The multiplicative group \(\mathbb F_p^\times\) is cyclic of order \(p-1\).
Proof. Let \(m\) be the exponent of the finite abelian group \(G=\mathbb F_p^\times\). Every element is a root of \(x^m-1\), so \(|G|\le m\); Lagrange gives \(m\le|G|\), hence \(m=|G|\). In a finite abelian group the exponent is attained by an element: combine elements whose orders contain the maximal prime-power factors. Therefore some element has order \(p-1\).
Definition. A primitive root modulo \(n\) is a unit of order \(\varphi(n)\), equivalently a generator of \((\mathbb Z/n\mathbb Z)^\times\).
Testing primitive roots
Proposition. If \(p-1=\prod_iq_i^{\alpha_i}\), then \(g\) is a primitive root modulo \(p\) if and only if \[ g^{(p-1)/q_i}\not\equiv1\pmod p \] for every distinct prime \(q_i\mid p-1\).
Proof. The order of \(g\) divides \(p-1\). It is a proper divisor exactly when it divides \((p-1)/q_i\) for at least one prime divisor \(q_i\).
Example. For \(p=17\), \(p-1=16\). Since \[ 3^8\equiv-1\pmod{17}, \] \(3\) has order \(16\) and is a primitive root. Its powers list every nonzero residue exactly once.
Which moduli have primitive roots?
Theorem. Primitive roots exist exactly for \[ n=1,\ 2,\ 4,\ p^k,\ 2p^k, \] where \(p\) is an odd prime.
For other moduli, the Chinese remainder decomposition produces too many independent cyclic factors. The Carmichael function \[ \lambda(n)=\exp\bigl((\mathbb Z/n\mathbb Z)^\times\bigr) \] gives the maximal possible order of a unit even when no primitive root exists; always \(a^{\lambda(n)}\equiv1\pmod n\) for every unit \(a\).