Primitive roots exist modulo every prime

Setup. Work in the field $\mathbb F_p$. Every nonzero residue has an order dividing $p-1$ (Fermat), so
$$\sum_{d\mid p-1}\psi(d)=p-1.$$

Claim: $\psi(d)\le\varphi(d)$ for all $d\mid p-1$. If $\psi(d)=0$ there is nothing to prove. Otherwise let $g$ have order $d$. The $d$ numbers $1,g,\dots,g^{d-1}$ are pairwise distinct and all satisfy $x^d=1$. A polynomial of degree $d$ over a field has at most $d$ roots, so these are *all* the roots of $x^d-1$. Any element of order $d$ is a root of $x^d-1$, hence of the form $g^j$ with $0\le j<d$. The order of $g^j$ is $\frac d{\gcd(j,d)}$, which equals $d$ iff $\gcd(j,d)=1$. So $\psi(d)=\varphi(d)$ in this case.

Comparison. We know $\sum_{d\mid p-1}\varphi(d)=p-1$ (the sum of $\varphi$ over the divisors of $p-1$). Combined with $\psi(d)\le\varphi(d)$ and $\sum\psi(d)=p-1$, equality must hold for every $d$:
$$\psi(d)=\varphi(d)\quad\text{for all }d\mid p-1.$$
In particular $\psi(p-1)=\varphi(p-1)\ge1$: a primitive root exists.

Example. $p=7$: $3$ is a primitive root ($3,2,6,4,5,1$), and there are $\varphi(6)=2$ of them ($3$ and $5$).

Lesson. Count elements of each order, bound each count by a polynomial-root argument, and use $\sum_{d\mid m}\varphi(d)=m$ to force equality.