[proofplan] By the [Lifting a Primitive Root](/theorems/1712) theorem, it suffices to exhibit an integer $g$ which is a primitive root mod $p$ and satisfies $g^{p-1} \not\equiv 1 \pmod{p^2}$. We start from any primitive root $g$ mod $p$, which exists because $(\mathbb{Z}/p\mathbb{Z})^\times$ is cyclic. If $g$ already satisfies the lifting condition, we are done; otherwise we perturb to $g_1 := g(1+p)$, which is still a primitive root mod $p$, and use the [Power Lifting Lemma](/theorems/1711) to compute that $g_1^{p-1} \not\equiv 1 \pmod{p^2}$. [/proofplan] [step:Choose a primitive root modulo $p$ as a candidate generator] Since $p$ is prime, by the theorem that [$(\mathbb{Z}/p\mathbb{Z})^\times$ is Cyclic](/theorems/1710), there exists an integer $g \in \mathbb{Z}$ with $(g, p) = 1$ whose residue class generates $(\mathbb{Z}/p\mathbb{Z})^\times$. In particular, $\operatorname{ord}_p(g) = p - 1$. By Fermat's Little Theorem, $g^{p-1} \equiv 1 \pmod{p}$, so there exists $y \in \mathbb{Z}$ with \begin{align*} g^{p-1} = 1 + p y. \end{align*} We split into two cases according to whether $p \nmid y$ (equivalently, $g^{p-1} \not\equiv 1 \pmod{p^2}$) or $p \mid y$ (equivalently, $g^{p-1} \equiv 1 \pmod{p^2}$). [/step] [step:Apply the lifting lemma directly when $g^{p-1} \not\equiv 1 \pmod{p^2}$] Suppose $g^{p-1} \not\equiv 1 \pmod{p^2}$. Then $g$ satisfies all three hypotheses of the [Lifting a Primitive Root](/theorems/1712) theorem: $p$ is an odd prime, $(g, p) = 1$, $g$ is a primitive root mod $p$, and $g^{p-1} \not\equiv 1 \pmod{p^2}$. Hence $g$ generates $(\mathbb{Z}/p^n\mathbb{Z})^\times$ for all $n \ge 1$, and the group is cyclic of order $\varphi(p^n) = p^{n-1}(p-1)$. [/step] [step:Perturb to $g_1 := g(1+p)$ when $g^{p-1} \equiv 1 \pmod{p^2}$] Suppose instead $g^{p-1} \equiv 1 \pmod{p^2}$, so $g^{p-1} = 1 + p^2 k$ for some $k \in \mathbb{Z}$. Define \begin{align*} g_1: \mathbb{Z} &\to \mathbb{Z} \\ &\mapsto g(1 + p). \end{align*} We check that $g_1$ is coprime to $p$ and a primitive root mod $p$: since $g_1 \equiv g \cdot 1 \equiv g \pmod{p}$, the residue of $g_1$ in $(\mathbb{Z}/p\mathbb{Z})^\times$ equals that of $g$, so $(g_1, p) = (g, p) = 1$ and $\operatorname{ord}_p(g_1) = \operatorname{ord}_p(g) = p - 1$. It remains to verify that $g_1^{p-1} \not\equiv 1 \pmod{p^2}$. We compute \begin{align*} g_1^{p-1} = g^{p-1} (1 + p)^{p-1}. \end{align*} We handle the two factors separately. [guided] The idea: we have a primitive root $g$ mod $p$ but it fails the lifting hypothesis $g^{p-1} \not\equiv 1 \pmod{p^2}$. We want to perturb $g$ multiplicatively by an element congruent to $1$ mod $p$, so that the perturbation preserves the residue class mod $p$ (keeping the primitive-root property) while shifting $g^{p-1}$ mod $p^2$. The simplest such perturbation is $1 + p$ itself. Define $g_1 := g(1 + p)$, viewed as an integer. Since $1 + p \equiv 1 \pmod{p}$, reduction mod $p$ gives $g_1 \equiv g \pmod{p}$. In particular, the residue class of $g_1$ in $(\mathbb{Z}/p\mathbb{Z})^\times$ coincides with that of $g$, so $g_1$ is coprime to $p$ (inheriting from $g$) and its order mod $p$ equals that of $g$, namely $p - 1$. So $g_1$ is still a primitive root mod $p$. The remaining task is to show $g_1^{p-1} \not\equiv 1 \pmod{p^2}$. By multiplicativity of powers: \begin{align*} g_1^{p-1} = g^{p-1} (1 + p)^{p-1}. \end{align*} We will compute each factor modulo $p^2$ (or rather, modulo $p^3$ to be safe and then reduce). The factor $g^{p-1}$ is already known to be $\equiv 1 \pmod{p^2}$ by the case hypothesis. The factor $(1 + p)^{p-1}$ is new and requires the [Power Lifting Lemma](/theorems/1711) to compute cleanly. [/guided] [/step] [step:Compute $(1+p)^{p-1} \pmod{p^2}$ using the Power Lifting Lemma] We evaluate $(1+p)^{p-1}$ modulo $p^2$. By the [Power Lifting Lemma](/theorems/1711)(ii) with $k = 1$ and $y = 1$ (so $1 + py = 1 + p$, verifying the lemma's hypotheses: $p$ is an odd prime, $y = 1 \in \mathbb{Z}$, $k = 1 \ge 1$): \begin{align*} (1 + p)^p \equiv 1 + p^2 \pmod{p^3}. \end{align*} Hence there exists $m \in \mathbb{Z}$ with $(1+p)^p = 1 + p^2 + p^3 m = 1 + p^2(1 + p m)$. Dividing by $1 + p$ (which is invertible mod $p^3$, since it is coprime to $p$): \begin{align*} (1+p)^{p-1} = \frac{(1+p)^p}{1+p} \equiv \frac{1 + p^2(1 + pm)}{1 + p} \pmod{p^3}. \end{align*} To simplify, note that modulo $p^2$ we only need $(1+p)^{p-1} \pmod{p^2}$, so we reduce. Modulo $p^2$, $(1+p)^p \equiv 1 \pmod{p^2}$ (from the lemma, since $1 + p^2 \equiv 1 \pmod{p^2}$). Therefore \begin{align*} (1+p) \cdot (1+p)^{p-1} = (1+p)^p \equiv 1 \pmod{p^2}, \end{align*} so $(1+p)^{p-1}$ is the multiplicative inverse of $1 + p$ modulo $p^2$. That inverse is $1 - p$, since \begin{align*} (1 + p)(1 - p) = 1 - p^2 \equiv 1 \pmod{p^2}. \end{align*} Hence \begin{align*} (1 + p)^{p-1} \equiv 1 - p \pmod{p^2}. \end{align*} [guided] We want $(1+p)^{p-1} \pmod{p^2}$. One path: start from the [Power Lifting Lemma](/theorems/1711)(ii), which with $k = 1$ and $y = 1$ says \begin{align*} (1 + p)^p \equiv 1 + p^2 \pmod{p^3}. \end{align*} Let us verify the lemma's hypotheses: $p$ odd prime (given), $y = 1 \in \mathbb{Z}$ (integer), $k = 1 \ge 1$. All hold. Reducing mod $p^2$ (the weaker modulus suffices for our needs): \begin{align*} (1 + p)^p \equiv 1 + p^2 \equiv 1 \pmod{p^2}. \end{align*} Now the key algebraic move: to get $(1+p)^{p-1}$, divide by $1 + p$. Since $\gcd(1 + p, p) = \gcd(1, p) = 1$, $1 + p$ is a unit in $\mathbb{Z}/p^2\mathbb{Z}$, so dividing is legal. From $(1+p) \cdot (1+p)^{p-1} \equiv 1 \pmod{p^2}$, we conclude that $(1+p)^{p-1}$ is the inverse of $1 + p$ mod $p^2$. What is the inverse of $1 + p$ mod $p^2$? A geometric-series-style computation works: since \begin{align*} (1 + p)(1 - p) = 1 - p^2 \equiv 1 \pmod{p^2}, \end{align*} we get $(1+p)^{-1} \equiv 1 - p \pmod{p^2}$. Hence \begin{align*} (1 + p)^{p-1} \equiv 1 - p \pmod{p^2}. \end{align*} A more direct way to see this: expand $(1+p)^{p-1}$ by the binomial theorem, \begin{align*} (1+p)^{p-1} = \sum_{j=0}^{p-1} \binom{p-1}{j} p^j = 1 + (p-1) p + \binom{p-1}{2} p^2 + \cdots \equiv 1 + (p-1)p \equiv 1 - p \pmod{p^2}. \end{align*} Both approaches agree; the lemma-based one fits cleanly with the machinery developed in earlier theorems. [/guided] [/step] [step:Combine the two factors to show $g_1^{p-1} \not\equiv 1 \pmod{p^2}$] Combining the case hypothesis $g^{p-1} \equiv 1 \pmod{p^2}$ with the previous step: \begin{align*} g_1^{p-1} = g^{p-1} (1 + p)^{p-1} \equiv 1 \cdot (1 - p) \equiv 1 - p \pmod{p^2}. \end{align*} Since $p \ge 3$ (as $p$ is an odd prime), $1 - p \not\equiv 1 \pmod{p^2}$: indeed $1 - p \equiv 1 \pmod{p^2}$ would require $p^2 \mid p$, which is false. Therefore \begin{align*} g_1^{p-1} \not\equiv 1 \pmod{p^2}. \end{align*} Thus $g_1$ satisfies every hypothesis of the [Lifting a Primitive Root](/theorems/1712) theorem: $p$ is an odd prime, $(g_1, p) = 1$, $g_1$ is a primitive root mod $p$, and $g_1^{p-1} \not\equiv 1 \pmod{p^2}$. Consequently, $g_1$ generates $(\mathbb{Z}/p^n\mathbb{Z})^\times$ for all $n \ge 1$. [/step] [step:Conclude cyclicity and compute the order] In both cases (either $g$ or $g_1$ works), we have produced an integer whose residue generates $(\mathbb{Z}/p^n\mathbb{Z})^\times$ for every $n \ge 1$. Therefore $(\mathbb{Z}/p^n\mathbb{Z})^\times$ is cyclic. Its order is \begin{align*} |(\mathbb{Z}/p^n\mathbb{Z})^\times| = \varphi(p^n) = p^{n-1}(p - 1), \end{align*} completing the proof. [/step]