Let $p$ be a prime. We prove that $(\mathbb{Z}/p\mathbb{Z})^*$ is cyclic, equivalently, that primitive roots modulo $p$ exist.

Lemma 1: For any divisor $d$ of $p-1$, there are at most $d$ solutions to $x^d \equiv 1 \pmod{p}$.

Proof: A polynomial of degree $d$ has at most $d$ roots modulo $p$ (since $\mathbb{Z}/p\mathbb{Z}$ is a field). The polynomial $x^d - 1$ has degree $d$, so at most $d$ roots modulo $p$.

Lemma 2: Let $\psi(d)$ denote the number of elements of order $d$ in $(\mathbb{Z}/p\mathbb{Z})^*$. Then: $\sum_{d \mid (p-1)} \psi(d) = p - 1$

Proof: Every element has some order $d$ dividing $p-1$ (by Lagrange's theorem). The sum counts all $p-1$ non-zero elements exactly once.

Lemma 3: If there exists an element of order $d$, then there are exactly $\phi(d)$ elements of order $d$.

Proof: If $g$ has order $d$, then $g^k$ has order $d$ if and only if $\gcd(k, d) = 1$. There are $\phi(d)$ such values of $k$ in $\{1, \ldots, d\}$.

Main proof: We have $\psi(d) \in \{0, \phi(d)\}$ for each $d \mid (p-1)$.

By Lemma 2: $\sum_{d \mid (p-1)} \psi(d) = p - 1$

But we also know (from properties of Euler's totient function): $\sum_{d \mid (p-1)} \phi(d) = p - 1$

Since $\psi(d) \leq \phi(d)$ for all $d$ and both sums equal $p-1$, we must have $\psi(d) = \phi(d)$ for all divisors $d$ of $p-1$.

In particular, $\psi(p-1) = \phi(p-1) > 0$, so there exist elements of order $p-1$. These are primitive roots modulo $p$.

Let $p$ be an odd prime and $g$ a primitive root modulo $p$. We prove that either $g$ or $g + p$ is a primitive root modulo $p^k$ for all $k \geq 1$.

Step 1: Show that $\text{ord}_{p^k}(g) = p^{k-1}(p-1)$ if $g^{p-1} \not\equiv 1 \pmod{p^2}$.

Let $d = \text{ord}_{p^k}(g)$. Since $g^{p-1} \equiv 1 \pmod{p}$, we have $p-1 \mid d$ by properties of orders.

Also, $d \mid \phi(p^k) = p^{k-1}(p-1)$, so $d = p^j(p-1)$ for some $0 \leq j \leq k-1$.

From $g^d \equiv 1 \pmod{p^k}$, we get $g^d \equiv 1 \pmod{p}$, so $(p-1) \mid d$.

Key claim: If $g^{p^{j}(p-1)} \equiv 1 \pmod{p^{j+2}}$, then $g^{p^{j+1}(p-1)} \equiv 1 \pmod{p^{j+3}}$.

This follows from the binomial theorem: if $g^m = 1 + tp^{j+2}$ with $p \nmid t$, then: $g^{pm} = (1 + tp^{j+2})^p \equiv 1 + tp^{j+3} \pmod{p^{j+4}}$

By induction, if $g^{p-1} \not\equiv 1 \pmod{p^2}$, then $g^{p^{j}(p-1)} \not\equiv 1 \pmod{p^{j+2}}$ for all $j \geq 0$.

Therefore, $\text{ord}_{p^k}(g) = p^{k-1}(p-1) = \phi(p^k)$.

Step 2: If $g^{p-1} \equiv 1 \pmod{p^2}$, show that $(g+p)^{p-1} \not\equiv 1 \pmod{p^2}$.

By the binomial theorem: $(g+p)^{p-1} = g^{p-1} + (p-1)g^{p-2}p + \binom{p-1}{2}g^{p-3}p^2 + \cdots$

Modulo $p^2$: $(g+p)^{p-1} \equiv g^{p-1} + (p-1)g^{p-2}p \pmod{p^2}$

If $g^{p-1} \equiv 1 \pmod{p^2}$, then: $(g+p)^{p-1} \equiv 1 - g^{p-2}p \pmod{p^2}$

Since $g$ is a primitive root modulo $p$, we have $g \not\equiv 0 \pmod{p}$, so $g^{p-2} \not\equiv 0 \pmod{p}$.

Therefore, $(g+p)^{p-1} \not\equiv 1 \pmod{p^2}$, and $g+p$ is a primitive root modulo $p^k$ by Step 1.