[proofplan]
Let $d$ be the order of $g$ in $G_n := (\mathbb{Z}/p^n\mathbb{Z})^\times$. By Lagrange's theorem, $d$ divides $|G_n| = p^{n-1}(p-1)$, so $d = p^a e$ with $0 \le a \le n-1$ and $e \mid p-1$. We show that $a < n-1$ and $e < p-1$ each lead to a contradiction: the first using the [Power Lifting Lemma](/theorems/1711) to track the exact $p$-adic size of $g^{p-1} - 1$, and the second by reducing modulo $p$ and invoking that $g$ is a primitive root mod $p$. Hence $d = p^{n-1}(p-1) = |G_n|$, i.e., $g$ generates $G_n$.
[/proofplan]
[step:Set up the order of $g$ modulo $p^n$ and parametrise its divisors]
Fix $n \ge 1$ and write $G_n := (\mathbb{Z}/p^n\mathbb{Z})^\times$, a finite abelian group of order
\begin{align*}
|G_n| = \varphi(p^n) = p^{n-1}(p-1).
\end{align*}
Since $(g, p) = 1$, the residue class of $g$ lies in $G_n$; let $d := \operatorname{ord}_{G_n}(g)$. By Lagrange's theorem, $d \mid |G_n| = p^{n-1}(p-1)$. Because $\gcd(p, p-1) = 1$, every divisor of $p^{n-1}(p-1)$ factors uniquely as
\begin{align*}
d = p^a e, \qquad 0 \le a \le n-1, \quad e \mid p-1.
\end{align*}
Our goal is to show $a = n-1$ and $e = p-1$, i.e., $d = p^{n-1}(p-1)$.
[guided]
We fix $n \ge 1$ and work inside the group $G_n := (\mathbb{Z}/p^n\mathbb{Z})^\times$. The order of this group is the Euler totient of $p^n$:
\begin{align*}
|G_n| = \varphi(p^n) = p^{n-1}(p-1).
\end{align*}
Since $(g, p) = 1$, the residue class of $g$ mod $p^n$ is a unit, so it makes sense to speak of its order $d := \operatorname{ord}_{G_n}(g)$. By Lagrange's theorem in group theory, the order of any element divides the order of the group, so
\begin{align*}
d \mid p^{n-1}(p-1).
\end{align*}
Why factor $d$ as $p^a e$? The two prime factors $p$ and $p-1$ of $|G_n|$ are coprime (since $p$ is prime and $p - 1 < p$), so unique factorisation of integers forces every divisor of $p^{n-1}(p-1)$ to split uniquely into its $p$-part and its $(p-1)$-part:
\begin{align*}
d = p^a e, \qquad 0 \le a \le n-1, \quad e \mid p-1.
\end{align*}
This decomposition isolates the two independent obstructions to $g$ being a generator: $a$ could be too small (the $p$-power part of the order is deficient), or $e$ could be too small (the $(p-1)$-part is deficient). We will rule out each separately.
[/guided]
[/step]
[step:Rule out a deficient $p$-part using the Power Lifting Lemma]
Suppose for contradiction that $a \le n-2$, so $d \mid p^{n-2}(p-1)$ and hence
\begin{align*}
g^{p^{n-2}(p-1)} \equiv 1 \pmod{p^n}.
\end{align*}
By Fermat's Little Theorem, $g^{p-1} \equiv 1 \pmod{p}$, so we may write
\begin{align*}
g^{p-1} = 1 + p y, \qquad y \in \mathbb{Z}.
\end{align*}
The hypothesis $g^{p-1} \not\equiv 1 \pmod{p^2}$ is precisely the statement that $p \nmid y$.
We apply the [Power Lifting Lemma](/theorems/1711)(ii) with $k = n-2$ (valid when $n \ge 2$; in the case $n = 1$ the inequality $a \le n - 2 = -1$ is vacuous, so the contradiction hypothesis itself cannot occur and $a = 0 = n - 1$ automatically). Since $p$ is odd and $y \in \mathbb{Z}$, the hypotheses of the lemma are met, and the conclusion reads
\begin{align*}
(1 + py)^{p^{n-2}} \equiv 1 + p^{n-1} y \pmod{p^n}.
\end{align*}
Therefore
\begin{align*}
g^{p^{n-2}(p-1)} = (g^{p-1})^{p^{n-2}} = (1 + py)^{p^{n-2}} \equiv 1 + p^{n-1} y \pmod{p^n}.
\end{align*}
Combined with $g^{p^{n-2}(p-1)} \equiv 1 \pmod{p^n}$, we get $p^{n-1} y \equiv 0 \pmod{p^n}$, i.e., $p \mid y$. This contradicts $p \nmid y$. Hence $a = n - 1$.
[guided]
The goal of this step is to force the $p$-power component $a$ of the order $d = p^a e$ to take its maximal value $a = n-1$. Suppose for contradiction that $a \le n-2$. Since $d = p^a e \mid p^{n-2}(p-1)$ and $d$ is the order of $g$ in $G_n$, we have
\begin{align*}
g^{p^{n-2}(p-1)} \equiv 1 \pmod{p^n}.
\end{align*}
How do we convert this into arithmetic we can contradict? The hypothesis $g^{p-1} \not\equiv 1 \pmod{p^2}$ is a statement about the exact $p$-adic valuation of $g^{p-1} - 1$. By Fermat's Little Theorem, $p \mid g^{p-1} - 1$, so we may write
\begin{align*}
g^{p-1} = 1 + p y, \qquad y \in \mathbb{Z}.
\end{align*}
The extra hypothesis is exactly $p \nmid y$: indeed, $g^{p-1} \equiv 1 \pmod{p^2}$ would mean $p^2 \mid p y$, i.e., $p \mid y$, which we assume does not hold.
Now we want to raise $1 + py$ to the power $p^{n-2}$ and track the result mod $p^n$. This is exactly the content of the [Power Lifting Lemma](/theorems/1711)(ii). Let us verify its hypotheses carefully. The lemma requires $p$ an odd prime (given in our hypotheses), $y \in \mathbb{Z}$ (we just defined $y$ this way), and $k \ge 1$ (we take $k = n - 2$). The index $n - 2 \ge 1$ forces $n \ge 3$; what about $n \in \{1, 2\}$? For $n = 1$, $a \le n-2 = -1$ is impossible, so the contradiction hypothesis is vacuous. For $n = 2$, $a \le 0$ means $a = 0$, and we need $g^{p-1} \equiv 1 \pmod{p^2}$, which directly contradicts the hypothesis $g^{p-1} \not\equiv 1 \pmod{p^2}$; no lifting lemma needed. So we may assume $n \ge 3$ and apply the lemma with $k = n - 2 \ge 1$. Its conclusion is
\begin{align*}
(1 + py)^{p^{n-2}} \equiv 1 + p^{n-1} y \pmod{p^n}.
\end{align*}
Now we substitute back:
\begin{align*}
g^{p^{n-2}(p-1)} = (g^{p-1})^{p^{n-2}} = (1 + py)^{p^{n-2}} \equiv 1 + p^{n-1} y \pmod{p^n}.
\end{align*}
Pairing this with $g^{p^{n-2}(p-1)} \equiv 1 \pmod{p^n}$ yields
\begin{align*}
p^{n-1} y \equiv 0 \pmod{p^n} \iff p \mid y,
\end{align*}
contradicting $p \nmid y$. We conclude $a = n - 1$.
The reason this step works: $p$-adically, raising $1 + py$ to the $p$-th power promotes the precision by exactly one when $p \nmid y$. Iterating $n - 2$ times gives precision $p^{n-1}$, one short of the $p^n$ needed to kill the expression. Without the hypothesis $p \nmid y$, the promotion could overshoot and the bound would collapse.
[/guided]
[/step]
[step:Rule out a deficient $(p-1)$-part by reducing modulo $p$]
Suppose for contradiction that $e < p-1$, while $a = n-1$ by the previous step. Then $d = p^{n-1} e$ with $1 \le e < p-1$ and $e \mid p-1$, and
\begin{align*}
g^{p^{n-1} e} \equiv 1 \pmod{p^n}.
\end{align*}
Reducing modulo $p$ (that is, projecting via the canonical surjection $\mathbb{Z}/p^n\mathbb{Z} \twoheadrightarrow \mathbb{Z}/p\mathbb{Z}$) gives
\begin{align*}
g^{p^{n-1} e} \equiv 1 \pmod{p}.
\end{align*}
By Fermat's Little Theorem applied to the unit $g \pmod p$, we have $g^{p-1} \equiv 1 \pmod{p}$, hence $g^{p^{n-1}} \equiv g \cdot g^{p^{n-1} - 1} \equiv g^{1 + (p^{n-1} - 1)} \pmod{p}$; more directly, raising $g^{p-1} \equiv 1 \pmod{p}$ to integer powers we compute $g^{p^{n-1}} \equiv g^{p^{n-1} \bmod (p-1)} \pmod{p}$. Since $p^{n-1} \equiv 1 \pmod{p-1}$ (as $p \equiv 1 \pmod{p-1}$), we obtain
\begin{align*}
g^{p^{n-1} e} \equiv g^{e} \pmod{p}.
\end{align*}
Therefore $g^{e} \equiv 1 \pmod{p}$. But $g$ is a primitive root mod $p$ by hypothesis, so its order in $(\mathbb{Z}/p\mathbb{Z})^\times$ is exactly $p - 1$, whence $(p-1) \mid e$. Combined with $1 \le e \le p - 1$, this forces $e = p-1$, contradicting $e < p - 1$.
[guided]
We have $a = n-1$ from the previous step; the remaining task is to force $e = p - 1$. Suppose for contradiction $e < p - 1$ with $e \mid p - 1$. The order hypothesis gives
\begin{align*}
g^{p^{n-1} e} \equiv 1 \pmod{p^n}.
\end{align*}
How do we exploit this? The exponent $p^{n-1} e$ involves the high power $p^{n-1}$, which dwarfs $p - 1$. To extract information about the order mod $p$, we project to the smaller modulus: if $x \equiv 1 \pmod{p^n}$ then certainly $x \equiv 1 \pmod{p}$. So
\begin{align*}
g^{p^{n-1} e} \equiv 1 \pmod{p}.
\end{align*}
Now we reduce the exponent modulo $p-1$ using Fermat's Little Theorem. Since $(g, p) = 1$, Fermat gives $g^{p-1} \equiv 1 \pmod{p}$, so $g^k \pmod p$ depends only on $k \bmod (p-1)$. We need the residue of $p^{n-1} e$ modulo $p - 1$. Observe that
\begin{align*}
p \equiv 1 \pmod{p-1} \implies p^{n-1} \equiv 1 \pmod{p-1},
\end{align*}
hence $p^{n-1} e \equiv e \pmod{p-1}$. Therefore
\begin{align*}
g^{p^{n-1} e} \equiv g^{e} \pmod{p}.
\end{align*}
Combining with $g^{p^{n-1} e} \equiv 1 \pmod p$:
\begin{align*}
g^{e} \equiv 1 \pmod{p}.
\end{align*}
Now we invoke the hypothesis that $g$ is a primitive root mod $p$: its order in $(\mathbb{Z}/p\mathbb{Z})^\times$ equals $p - 1$. A standard order fact says that $g^e \equiv 1 \pmod p$ iff $\operatorname{ord}_p(g) \mid e$, i.e., $(p-1) \mid e$. Together with $e \mid p - 1$ and $1 \le e \le p-1$, this forces $e = p - 1$, contradicting $e < p - 1$.
Why does this work? The $p$-adic and $(p-1)$-adic parts of the order decouple cleanly because $p$ and $p-1$ are coprime. The lifting lemma controls the $p$-part (that is what Step 2 did); the primitive-root hypothesis controls the $(p-1)$-part (mod $p$ information suffices, since reducing $p^n$ to $p$ does not affect the $(p-1)$-part of the order).
[/guided]
[/step]
[step:Conclude that $g$ generates $(\mathbb{Z}/p^n\mathbb{Z})^\times$]
By the previous two steps, $a = n-1$ and $e = p-1$, so
\begin{align*}
d = p^a e = p^{n-1}(p-1) = |G_n|.
\end{align*}
The cyclic subgroup $\langle g \rangle \subseteq G_n$ has order $d = |G_n|$, so $\langle g \rangle = G_n$, i.e., $g$ is a generator of $(\mathbb{Z}/p^n\mathbb{Z})^\times$. Since $n \ge 1$ was arbitrary, this holds for all $n$, completing the proof.
[/step]
