Existence of primitive roots modulo a prime

Remarks

A proof: a polynomial of degree $d$ has at most $d$ roots in the field $\mathbb{Z}/p\mathbb{Z}$. So for each $d \mid p - 1$, at most $\varphi(d)$ elements have order $d$. The sum of the totient over the divisors then forces exactly $\varphi(d)$ elements of each order $d$. In particular, there are exactly $\varphi(p - 1)$ primitive roots modulo $p$ in $\{1, \dots, p - 1\}$. More generally, each finite subgroup of the multiplicative group of a field is cyclic.