[proofplan] The group $G = (\mathbb{Z}/p\mathbb{Z})^\times$ has order $p - 1$, and we must show $G$ contains an element of order $p - 1$. Write $N_d$ for the number of elements of $G$ of order exactly $d$. Partitioning by order and using Lagrange's theorem gives $\sum_{d \mid p-1} N_d = p - 1$. Comparing with the classical identity $\sum_{d \mid p-1} \varphi(d) = p - 1$ from the [Explicit Formula for $\varphi$](/theorems/1705), we will show $N_d \leq \varphi(d)$ for every divisor $d$, so equality must hold term by term. In particular $N_{p-1} = \varphi(p-1) \geq 1$, yielding a generator. The inequality $N_d \leq \varphi(d)$ is where the polynomial theory is consumed: any cyclic subgroup of order $d$ exhausts all roots of $X^d - 1$ in $\mathbb{F}_p$ by [Lagrange's polynomial theorem](/theorems/1709), and then the [Generators of a Cyclic Group](/theorems/1701) count finishes the job. [/proofplan] [step:Set up order-counting and the divisor-sum identity for $|G| = p - 1$] Let $G := (\mathbb{Z}/p\mathbb{Z})^\times$, a finite abelian group of order $|G| = p - 1$. For each divisor $d \mid p - 1$, define \begin{align*} N_d &:= \#\{g \in G : \mathrm{ord}(g) = d\}. \end{align*} By [Lagrange's theorem for finite groups](/theorems/???), the order of any element of $G$ divides $|G| = p - 1$. The sets $\{g : \mathrm{ord}(g) = d\}$ as $d$ ranges over divisors of $p - 1$ therefore partition $G$, giving \begin{align*} \sum_{d \mid p-1} N_d &= |G| = p - 1. \tag{$\ast$} \end{align*} On the other hand, the [Explicit Formula for $\varphi$](/theorems/1705) (part (iii)) applied to $n = p - 1$ states \begin{align*} \sum_{d \mid p-1} \varphi(d) &= p - 1. \tag{$\ast\ast$} \end{align*} These two sums are equal, so any pointwise inequality $N_d \leq \varphi(d)$ that we establish must actually be an equality for every $d$. [guided] The strategy rests on a pair of sums that both equal $p - 1$. The first, ($\ast$), comes from sorting the elements of $G$ by their order: every $g \in G$ has a well-defined positive integer order, and by Lagrange's theorem this order must divide $|G| = p - 1$. So if we bucket elements by their order $d \in \{d : d \mid p-1\}$, the buckets partition $G$, and summing their sizes gives $|G|$. The second, ($\ast\ast$), is a purely number-theoretic identity about the totient — it holds for every positive integer $n$, and in particular for $n = p - 1$. The two sums are over the **same** index set $\{d : d \mid p - 1\}$ and both equal $p - 1$. If we can show term-by-term that $N_d \leq \varphi(d)$, then the two sums being equal forces every inequality to be an equality: \begin{align*} \sum_{d} (\varphi(d) - N_d) = 0 \quad \text{with each summand} \geq 0 \implies \varphi(d) = N_d \text{ for all } d. \end{align*} In particular for $d = p - 1$ we will get $N_{p-1} = \varphi(p-1) \geq 1$, producing a generator. So the entire proof reduces to establishing $N_d \leq \varphi(d)$. [/guided] [/step] [step:Reduce $N_d \leq \varphi(d)$ to the structure of a single cyclic subgroup of order $d$] Fix $d \mid p - 1$. We prove $N_d \leq \varphi(d)$ by considering two cases. Case A: $N_d = 0$. Then $N_d = 0 \leq \varphi(d)$. Case B: $N_d \geq 1$. Pick $\alpha \in G$ with $\mathrm{ord}(\alpha) = d$, and let $\langle \alpha \rangle := \{1, \alpha, \alpha^2, \ldots, \alpha^{d-1}\}$ denote the cyclic subgroup generated by $\alpha$. It has order $d$ by choice of $\alpha$. We will show: [claim:Every element of $G$ of order $d$ lies in $\langle \alpha \rangle$] Every $\beta \in G$ with $\mathrm{ord}(\beta) = d$ satisfies $\beta \in \langle \alpha \rangle$. [proof] The element $\beta$ has order $d$, so $\beta^d = 1$ in $G$, which is the same as saying $\beta$ is a root of the polynomial \begin{align*} F(X) := X^d - 1 \in \mathbb{Z}[X] \end{align*} modulo $p$. The leading coefficient of $F$ is $1$, which is not divisible by $p$, so the hypothesis of [Lagrange's Theorem for Polynomial Congruences](/theorems/1709) is satisfied, and the theorem yields \begin{align*} \#\{x \in G : x^d \equiv 1 \pmod p\} \leq \deg F = d. \end{align*} But every element of $\langle \alpha \rangle$ already satisfies $x^d = 1$, because $(\alpha^k)^d = (\alpha^d)^k = 1^k = 1$. So $\langle \alpha \rangle$ supplies $d$ distinct roots of $F$ modulo $p$, and the bound above forces \begin{align*} \{x \in G : x^d \equiv 1 \pmod p\} = \langle \alpha \rangle. \end{align*} Since $\beta^d = 1$, we conclude $\beta \in \langle \alpha \rangle$. [/proof] [/claim] By the claim, the set $\{g \in G : \mathrm{ord}(g) = d\}$ is contained in $\langle \alpha \rangle$, so \begin{align*} N_d = \#\{g \in \langle \alpha \rangle : \mathrm{ord}(g) = d\}. \end{align*} The subgroup $\langle \alpha \rangle$ is cyclic of order $d$, and an element of a cyclic group of order $d$ has order equal to $d$ if and only if it is a generator. By [Generators of a Cyclic Group](/theorems/1701), $\langle \alpha \rangle$ contains exactly $\varphi(d)$ generators, so \begin{align*} N_d = \varphi(d) \leq \varphi(d). \end{align*} Combining both cases yields $N_d \leq \varphi(d)$ for every $d \mid p - 1$. [guided] We want to bound $N_d$, the number of elements of $G$ of order exactly $d$. If there are none, the bound is vacuous, so suppose there is at least one — call it $\alpha$. The cyclic subgroup $\langle \alpha \rangle \subseteq G$ has order $d$ by definition of $\mathrm{ord}(\alpha)$. The crucial observation is that **every** element of $\langle \alpha \rangle$ is a root of $X^d - 1$ in $\mathbb{F}_p$: for $0 \leq k \leq d - 1$, $(\alpha^k)^d = \alpha^{kd} = (\alpha^d)^k = 1$. So $\langle \alpha \rangle$ supplies $d$ distinct roots of $X^d - 1$. Now we invoke [Lagrange's Theorem for Polynomial Congruences](/theorems/1709). Its hypotheses are: the polynomial has integer coefficients, and $p$ does not divide the leading coefficient. For $F(X) = X^d - 1$, the leading coefficient is $1$, and of course $p \nmid 1$. So the hypothesis is satisfied, and the theorem bounds the number of solutions of $F(x) \equiv 0 \pmod p$ by $d = \deg F$. We already have $d$ solutions lined up inside $\langle \alpha \rangle$, so there are **no others**: the set of solutions to $X^d \equiv 1 \pmod p$ in $G$ is exactly $\langle \alpha \rangle$. This is the structural fact that the polynomial theory delivers. In particular, any element $\beta \in G$ with $\mathrm{ord}(\beta) = d$ satisfies $\beta^d = 1$, hence $\beta \in \langle \alpha \rangle$. So every element of order $d$ in $G$ is trapped inside the fixed cyclic subgroup $\langle \alpha \rangle$, and we may count from within. Inside the cyclic group $\langle \alpha \rangle$ of order $d$, the number of elements of order $d$ is exactly the number of generators of $\langle \alpha \rangle$. By [Generators of a Cyclic Group](/theorems/1701), this count equals $\varphi(d)$. So $N_d = \varphi(d)$ in this case. Note that we have actually proved an equality, not just an inequality — but only the inequality is needed for the sum-comparison argument of the next step. The fact that equality holds in each case $N_d > 0$ is a stronger structural statement that will fall out of the sum comparison anyway. [/guided] [/step] [step:Compare the two sums to conclude $N_{p-1} = \varphi(p-1) \geq 1$] From the previous step, $N_d \leq \varphi(d)$ for every $d \mid p - 1$. Subtracting ($\ast$) from ($\ast\ast$): \begin{align*} \sum_{d \mid p-1} \bigl( \varphi(d) - N_d \bigr) = (p - 1) - (p - 1) = 0. \end{align*} Each summand $\varphi(d) - N_d$ is non-negative, and their sum is zero, so every summand is zero: \begin{align*} N_d = \varphi(d) \quad \text{for every } d \mid p - 1. \end{align*} In particular, for $d = p - 1$, \begin{align*} N_{p-1} = \varphi(p-1) \geq 1 \end{align*} (the lower bound $\varphi(p-1) \geq 1$ follows because $1 \in \mathbb{Z}$ is always coprime to $p - 1$). Hence there exists $g \in G$ with $\mathrm{ord}(g) = p - 1$, so $\langle g \rangle$ has order $p - 1 = |G|$, giving $\langle g \rangle = G$. We conclude that $G$ is cyclic of order $p - 1$, as claimed. [/step]