[proofplan] The proof connects the factorisation of $\bar{f}$ over $\mathbb{F}_p$ to the cycle structure of an element of $G$ by passing through algebraic number theory. We first set up the integral framework: the ring of integers $\mathcal{O}_E$ of the splitting field $E$, a prime ideal $\mathfrak{p}$ of $\mathcal{O}_E$ lying over $p$, and the residue field $k_{\mathfrak{p}} := \mathcal{O}_E/\mathfrak{p}$. We show that $k_{\mathfrak{p}}$ is a splitting field of $\bar{f}$ over $\mathbb{F}_p$, so the roots of $\bar{f}$ in $k_{\mathfrak{p}}$ are in natural bijection with the roots of $f$ in $E$ via the reduction map. We then verify that the Frobenius automorphism $\operatorname{Fr}_p \in \operatorname{Gal}(k_{\mathfrak{p}}/\mathbb{F}_p)$ permutes the roots of each irreducible factor of $\bar{f}$ in a single cycle, giving cycle type $(d_1, \ldots, d_r)$. Finally, we construct the decomposition group $D(\mathfrak{p}) \leq G$ and a surjective reduction homomorphism $D(\mathfrak{p}) \twoheadrightarrow \operatorname{Gal}(k_{\mathfrak{p}}/\mathbb{F}_p)$. Any preimage of $\operatorname{Fr}_p$ under this surjection is an element of $G$ with cycle type $(d_1, \ldots, d_r)$. [/proofplan]

[step:Establish the integral framework and the reduction map on roots]Since $f \in \mathbb{Z}[t]$ is monic of degree $n$ with splitting field $E$ over $\mathbb{Q}$, the roots $\alpha_1, \ldots, \alpha_n \in E$ of $f$ are algebraic integers (roots of a monic polynomial with integer coefficients). Hence $\alpha_1, \ldots, \alpha_n \in \mathcal{O}_E$, where $\mathcal{O}_E$ denotes the ring of integers of $E$. The Galois group $G = \operatorname{Gal}(E/\mathbb{Q})$ embeds into $S_n$ via the action of $G$ on the roots: each $\sigma \in G$ permutes $\{\alpha_1, \ldots, \alpha_n\}$, and the map $G \hookrightarrow S_n$ sending $\sigma$ to the induced permutation is an injective group homomorphism (injective because $E = \mathbb{Q}(\alpha_1, \ldots, \alpha_n)$, so an automorphism is determined by its action on the roots). Let $\mathfrak{p}$ be a prime ideal of $\mathcal{O}_E$ lying over $(p)$, i.e., $\mathfrak{p} \cap \mathbb{Z} = (p)$. The quotient $k_{\mathfrak{p}} := \mathcal{O}_E / \mathfrak{p}$ is a finite field of characteristic $p$. Define the reduction map \begin{align*} \pi: \mathcal{O}_E &\to k_{\mathfrak{p}} \\ x &\mapsto x + \mathfrak{p}. \end{align*} Since $\alpha_1, \ldots, \alpha_n \in \mathcal{O}_E$, their reductions $\bar{\alpha}_i := \pi(\alpha_i)$ are well-defined elements of $k_{\mathfrak{p}}$. We verify that $\bar{\alpha}_1, \ldots, \bar{\alpha}_n$ are the roots of $\bar{f}$ in $k_{\mathfrak{p}}$. Since $f(\alpha_i) = 0$ in $\mathcal{O}_E$ and $\pi$ is a ring homomorphism sending each coefficient $c \in \mathbb{Z}$ to its residue class $c + p\mathbb{Z} \in \mathbb{F}_p \subset k_{\mathfrak{p}}$, we obtain \begin{align*} \bar{f}(\bar{\alpha}_i) = \pi(f(\alpha_i)) = \pi(0) = 0 \quad \text{for each } i \in \{1, \ldots, n\}. \end{align*} Since $\bar{f}$ has degree $n$ (it is monic of degree $n$ by the assumption that $f$ is monic of degree $n$ and the leading coefficient $1$ is nonzero modulo $p$), $\bar{f}$ has at most $n$ roots in $k_{\mathfrak{p}}$. Since $\bar{f}$ is separable by hypothesis, it has exactly $n$ distinct roots. The elements $\bar{\alpha}_1, \ldots, \bar{\alpha}_n$ are $n$ roots of $\bar{f}$ in $k_{\mathfrak{p}}$, and they must be distinct (since $\bar{f}$ has exactly $n$ distinct roots and we have exhibited $n$ of them). Therefore the map \begin{align*} \{\alpha_1, \ldots, \alpha_n\} &\to \{\text{roots of } \bar{f} \text{ in } k_{\mathfrak{p}}\} \\ \alpha_i &\mapsto \bar{\alpha}_i \end{align*} is a bijection. Moreover, $k_{\mathfrak{p}}$ is generated over $\mathbb{F}_p$ by $\bar{\alpha}_1, \ldots, \bar{\alpha}_n$ (since $\mathcal{O}_E = \mathbb{Z}[\alpha_1, \ldots, \alpha_n, \beta_1, \ldots, \beta_s]$ for some additional algebraic integers $\beta_j$, and $k_{\mathfrak{p}}$ is generated over $\mathbb{F}_p$ by the images of these generators; but $k_{\mathfrak{p}}$ contains a splitting field of $\bar{f}$ over $\mathbb{F}_p$, and for our purposes it suffices to work within the subfield $\bar{E} := \mathbb{F}_p(\bar{\alpha}_1, \ldots, \bar{\alpha}_n) \subset k_{\mathfrak{p}}$, which is the splitting field of $\bar{f}$ over $\mathbb{F}_p$).[/step]

[guided]The first task is to connect the roots of $f$ over $\mathbb{Q}$ to the roots of $\bar{f}$ over $\mathbb{F}_p$, and the bridge is the ring of integers $\mathcal{O}_E$. Why are the roots $\alpha_i$ algebraic integers? Because $f \in \mathbb{Z}[t]$ is monic: an algebraic number is an algebraic integer if and only if its minimal polynomial over $\mathbb{Q}$ has integer coefficients and leading coefficient $1$. Since $f$ is monic and $f(\alpha_i) = 0$, the minimal polynomial of $\alpha_i$ divides $f$ in $\mathbb{Q}[t]$, and by Gauss's lemma it divides $f$ in $\mathbb{Z}[t]$ as well (since $f$ is monic). Hence the minimal polynomial of $\alpha_i$ is monic with integer coefficients, confirming $\alpha_i \in \mathcal{O}_E$. The prime $p \in \mathbb{Z}$ generates the ideal $(p) \subset \mathbb{Z} \subset \mathcal{O}_E$. This ideal need not remain prime in $\mathcal{O}_E$; in general $(p)\mathcal{O}_E$ factors as a product of prime ideals in $\mathcal{O}_E$. We choose any prime ideal $\mathfrak{p}$ of $\mathcal{O}_E$ containing $p$, i.e., $\mathfrak{p} | (p)\mathcal{O}_E$. The residue field $k_{\mathfrak{p}} = \mathcal{O}_E/\mathfrak{p}$ is a finite extension of $\mathbb{F}_p = \mathbb{Z}/(p)$. The crucial observation is that the reduction map $\pi: \mathcal{O}_E \to k_{\mathfrak{p}}$ is a ring homomorphism, so it sends roots of $f$ to roots of $\bar{f}$. Specifically, if $f(t) = t^n + a_{n-1}t^{n-1} + \cdots + a_0$ with $a_i \in \mathbb{Z}$, then for each $\alpha_i$: \begin{align*} \bar{f}(\pi(\alpha_i)) &= \pi(\alpha_i)^n + \pi(a_{n-1})\pi(\alpha_i)^{n-1} + \cdots + \pi(a_0) \\ &= \pi(\alpha_i^n + a_{n-1}\alpha_i^{n-1} + \cdots + a_0) \\ &= \pi(f(\alpha_i)) = \pi(0) = 0. \end{align*} The separability hypothesis on $\bar{f}$ is essential here. Since $\bar{f}$ is separable over $\mathbb{F}_p$, it has exactly $n$ distinct roots in its splitting field. We have produced $n$ roots $\bar{\alpha}_1, \ldots, \bar{\alpha}_n$ of $\bar{f}$ in $k_{\mathfrak{p}}$. If any two coincided, say $\bar{\alpha}_i = \bar{\alpha}_j$ with $i \neq j$, then $\alpha_i - \alpha_j \in \mathfrak{p}$. But $\bar{f}$ would then have fewer than $n$ distinct roots, which is impossible since $\bar{f}$ has degree $n$ and is separable. Therefore $\bar{\alpha}_1, \ldots, \bar{\alpha}_n$ are all distinct, and the reduction map gives a bijection between the roots of $f$ and the roots of $\bar{f}$.[/guided]

[step:Show that the Frobenius permutes roots of each irreducible factor in a single cycle]Let $\bar{f} = \bar{g}_1 \bar{g}_2 \cdots \bar{g}_r$ be the factorisation of $\bar{f}$ into irreducible polynomials over $\mathbb{F}_p$, with $\deg \bar{g}_k = d_k$ for $k = 1, \ldots, r$, so that $d_1 + d_2 + \cdots + d_r = n$. The splitting field $\bar{E} = \mathbb{F}_p(\bar{\alpha}_1, \ldots, \bar{\alpha}_n)$ of $\bar{f}$ over $\mathbb{F}_p$ is a finite extension of $\mathbb{F}_p$. By the [Galois Group of Finite Field Extension](/theorems/1277), $\operatorname{Gal}(\bar{E}/\mathbb{F}_p)$ is cyclic, generated by the Frobenius automorphism \begin{align*} \operatorname{Fr}_p: \bar{E} &\to \bar{E} \\ x &\mapsto x^p. \end{align*} We now analyse how $\operatorname{Fr}_p$ acts on the roots of each irreducible factor $\bar{g}_k$. Fix $k \in \{1, \ldots, r\}$ and let $\bar{\beta}$ be any root of $\bar{g}_k$ in $\bar{E}$. Since $\bar{g}_k$ is irreducible of degree $d_k$ over $\mathbb{F}_p$, the field $\mathbb{F}_p(\bar{\beta})$ is an extension of $\mathbb{F}_p$ of degree $d_k$, hence $\mathbb{F}_p(\bar{\beta}) \cong \mathbb{F}_{p^{d_k}}$. The elements of $\mathbb{F}_p(\bar{\beta})$ are precisely the roots of $t^{p^{d_k}} - t$ over $\mathbb{F}_p$, and in particular $\bar{\beta}^{p^{d_k}} = \bar{\beta}$. The orbit of $\bar{\beta}$ under $\operatorname{Fr}_p$ is the set $\{\bar{\beta}, \bar{\beta}^p, \bar{\beta}^{p^2}, \ldots\}$. We claim this orbit has exactly $d_k$ elements. Indeed, $\operatorname{Fr}_p^j(\bar{\beta}) = \bar{\beta}^{p^j}$, and $\bar{\beta}^{p^j} = \bar{\beta}$ if and only if $\bar{\beta}$ is a root of $t^{p^j} - t$, which holds if and only if $\bar{\beta} \in \mathbb{F}_{p^j}$, which holds if and only if $\mathbb{F}_p(\bar{\beta}) \subset \mathbb{F}_{p^j}$. By the [Subfield Criterion for Finite Fields](/theorems/1276), $\mathbb{F}_{p^{d_k}} \subset \mathbb{F}_{p^j}$ if and only if $d_k | j$. Therefore the smallest positive $j$ with $\operatorname{Fr}_p^j(\bar{\beta}) = \bar{\beta}$ is $j = d_k$, and the orbit is \begin{align*} \{\bar{\beta},\; \bar{\beta}^p,\; \bar{\beta}^{p^2},\; \ldots,\; \bar{\beta}^{p^{d_k - 1}}\}, \end{align*} a set of $d_k$ distinct elements. Each element $\bar{\beta}^{p^j}$ is a root of $\bar{g}_k$ (since $\bar{g}_k$ has coefficients in $\mathbb{F}_p$, the map $x \mapsto x^p$ sends roots of $\bar{g}_k$ to roots of $\bar{g}_k$: if $\bar{g}_k(\bar{\beta}) = 0$, then $\bar{g}_k(\bar{\beta}^p) = \bar{g}_k(\bar{\beta})^p = 0$). Since $\bar{g}_k$ has degree $d_k$ and we have found $d_k$ distinct roots, these are all the roots of $\bar{g}_k$. Therefore $\operatorname{Fr}_p$ permutes the $d_k$ roots of $\bar{g}_k$ in a single cycle of length $d_k$. Since the roots of different irreducible factors are disjoint (the $\bar{g}_k$ are distinct irreducibles and $\bar{f}$ is separable), the action of $\operatorname{Fr}_p$ on all $n$ roots of $\bar{f}$ decomposes into $r$ disjoint cycles of lengths $d_1, d_2, \ldots, d_r$.[/step]

[guided]The key fact from finite field theory is that the roots of an irreducible polynomial of degree $d$ over $\mathbb{F}_p$ form a single orbit of size $d$ under the Frobenius $x \mapsto x^p$. Let us trace why this holds in detail. Let $\bar{g}_k \in \mathbb{F}_p[t]$ be irreducible of degree $d_k$, and let $\bar{\beta}$ be a root of $\bar{g}_k$ in $\bar{E}$. The extension $\mathbb{F}_p(\bar{\beta})/\mathbb{F}_p$ has degree $d_k$ (since $\bar{g}_k$ is the minimal polynomial of $\bar{\beta}$ over $\mathbb{F}_p$, having degree $d_k$). Therefore $\mathbb{F}_p(\bar{\beta}) = \mathbb{F}_{p^{d_k}}$, and the order of $\bar{\beta}$ under the Frobenius — i.e., the smallest $j \geq 1$ with $\bar{\beta}^{p^j} = \bar{\beta}$ — equals $d_k$. Why? The condition $\bar{\beta}^{p^j} = \bar{\beta}$ says $\bar{\beta} \in \mathbb{F}_{p^j}$ (the fixed field of $\operatorname{Fr}_p^j$). By the [Subfield Criterion for Finite Fields](/theorems/1276), $\mathbb{F}_{p^{d_k}} \subset \mathbb{F}_{p^j}$ if and only if $d_k | j$. Since $\bar{\beta}$ generates $\mathbb{F}_{p^{d_k}}$ over $\mathbb{F}_p$, we have $\bar{\beta} \in \mathbb{F}_{p^j}$ if and only if $\mathbb{F}_{p^{d_k}} \subset \mathbb{F}_{p^j}$, i.e., $d_k | j$. The smallest such $j$ is $d_k$ itself. The orbit $\{\bar{\beta}, \bar{\beta}^p, \ldots, \bar{\beta}^{p^{d_k - 1}}\}$ therefore consists of $d_k$ distinct elements. These are all roots of $\bar{g}_k$: the Frobenius $x \mapsto x^p$ is a field homomorphism of $\bar{E}$, so \begin{align*} \bar{g}_k(\bar{\beta}^p) = \bar{g}_k(\bar{\beta})^p = 0^p = 0, \end{align*} where the first equality uses the fact that $\bar{g}_k$ has coefficients in $\mathbb{F}_p$ (so $a^p = a$ for each coefficient $a$, and raising to the $p$-th power commutes with evaluation). Since $\bar{g}_k$ has exactly $d_k$ roots (it is separable, being irreducible over a finite field; alternatively, the separability of $\bar{f}$ ensures that its irreducible factors have no repeated roots), the orbit accounts for all roots. The Frobenius therefore acts on the roots of $\bar{g}_k$ as a $d_k$-cycle: $\bar{\beta} \mapsto \bar{\beta}^p \mapsto \bar{\beta}^{p^2} \mapsto \cdots \mapsto \bar{\beta}^{p^{d_k-1}} \mapsto \bar{\beta}$. Since the factorisation $\bar{f} = \bar{g}_1 \cdots \bar{g}_r$ partitions the $n$ roots of $\bar{f}$ into $r$ disjoint blocks (the root sets of the $\bar{g}_k$), and the Frobenius cycles within each block, the overall permutation has cycle type $(d_1, d_2, \ldots, d_r)$.[/guided]

[step:Construct the decomposition group and the reduction homomorphism]The Galois group $G = \operatorname{Gal}(E/\mathbb{Q})$ acts on $\mathcal{O}_E$ by ring automorphisms (each $\sigma \in G$ maps algebraic integers to algebraic integers). Moreover, $G$ acts on the set of prime ideals of $\mathcal{O}_E$ lying over $(p)$: for $\sigma \in G$, the image $\sigma(\mathfrak{p}) = \{\sigma(x) : x \in \mathfrak{p}\}$ is again a prime ideal of $\mathcal{O}_E$ lying over $(p)$ (since $\sigma$ fixes $\mathbb{Z}$ pointwise, so $\sigma(\mathfrak{p}) \cap \mathbb{Z} = \sigma(\mathfrak{p} \cap \mathbb{Z}) = \sigma((p)) = (p)$). Define the **decomposition group** of $\mathfrak{p}$: \begin{align*} D(\mathfrak{p}) := \{\sigma \in G : \sigma(\mathfrak{p}) = \mathfrak{p}\}. \end{align*} This is a subgroup of $G$. Each $\sigma \in D(\mathfrak{p})$ stabilises $\mathfrak{p}$, so $\sigma$ induces a well-defined ring automorphism of the residue field $k_{\mathfrak{p}} = \mathcal{O}_E/\mathfrak{p}$. Explicitly, define \begin{align*} \bar{\sigma}: k_{\mathfrak{p}} &\to k_{\mathfrak{p}} \\ x + \mathfrak{p} &\mapsto \sigma(x) + \mathfrak{p}. \end{align*} This is well-defined because if $x - y \in \mathfrak{p}$, then $\sigma(x) - \sigma(y) = \sigma(x - y) \in \sigma(\mathfrak{p}) = \mathfrak{p}$. Furthermore, $\bar{\sigma}$ fixes $\mathbb{F}_p \subset k_{\mathfrak{p}}$ pointwise (since $\sigma$ fixes $\mathbb{Z}$ and hence the image of $\mathbb{Z}$ in $k_{\mathfrak{p}}$). Therefore $\bar{\sigma} \in \operatorname{Gal}(k_{\mathfrak{p}}/\mathbb{F}_p)$, and the reduction map \begin{align*} \rho: D(\mathfrak{p}) &\to \operatorname{Gal}(k_{\mathfrak{p}}/\mathbb{F}_p) \\ \sigma &\mapsto \bar{\sigma} \end{align*} is a group homomorphism. (It respects composition: $\overline{\sigma \circ \tau}(x + \mathfrak{p}) = (\sigma \circ \tau)(x) + \mathfrak{p} = \bar{\sigma}(\tau(x) + \mathfrak{p}) = \bar{\sigma}(\bar{\tau}(x + \mathfrak{p})) = (\bar{\sigma} \circ \bar{\tau})(x + \mathfrak{p})$.)[/step]

[guided]The decomposition group $D(\mathfrak{p})$ is the stabiliser of $\mathfrak{p}$ under the natural action of $G$ on prime ideals of $\mathcal{O}_E$. Why does this action exist? Each $\sigma \in G$ is a $\mathbb{Q}$-automorphism of $E$, and since $\mathcal{O}_E$ is the integral closure of $\mathbb{Z}$ in $E$, the image $\sigma(\mathcal{O}_E)$ is the integral closure of $\sigma(\mathbb{Z}) = \mathbb{Z}$ in $\sigma(E) = E$, so $\sigma(\mathcal{O}_E) = \mathcal{O}_E$. Hence $\sigma$ restricts to a ring automorphism of $\mathcal{O}_E$, and it sends prime ideals to prime ideals. The key construction is the reduction homomorphism $\rho$. An element $\sigma \in D(\mathfrak{p})$ satisfies $\sigma(\mathfrak{p}) = \mathfrak{p}$, which means $\sigma$ sends $\mathfrak{p}$ to itself. This is exactly the condition needed for $\sigma$ to induce a well-defined map on the quotient $\mathcal{O}_E/\mathfrak{p}$: if $x \equiv y \pmod{\mathfrak{p}}$, then $x - y \in \mathfrak{p}$, so $\sigma(x - y) \in \sigma(\mathfrak{p}) = \mathfrak{p}$, giving $\sigma(x) \equiv \sigma(y) \pmod{\mathfrak{p}}$. Why does $\bar{\sigma}$ fix $\mathbb{F}_p$? The subfield $\mathbb{F}_p \subset k_{\mathfrak{p}}$ is the image of $\mathbb{Z}$ under $\pi$. For $a \in \mathbb{Z}$, $\bar{\sigma}(\pi(a)) = \pi(\sigma(a)) = \pi(a)$ since $\sigma$ fixes $\mathbb{Q}$ pointwise and hence fixes $\mathbb{Z}$ pointwise. Therefore $\bar{\sigma}|_{\mathbb{F}_p} = \operatorname{id}$, confirming $\bar{\sigma} \in \operatorname{Gal}(k_{\mathfrak{p}}/\mathbb{F}_p)$. The homomorphism property is verified by direct computation: for $\sigma, \tau \in D(\mathfrak{p})$ and $x \in \mathcal{O}_E$, \begin{align*} \rho(\sigma \circ \tau)(x + \mathfrak{p}) &= \sigma(\tau(x)) + \mathfrak{p} = \bar{\sigma}(\tau(x) + \mathfrak{p}) = \bar{\sigma}(\bar{\tau}(x + \mathfrak{p})), \end{align*} so $\rho(\sigma \circ \tau) = \bar{\sigma} \circ \bar{\tau} = \rho(\sigma) \circ \rho(\tau)$.[/guided]

[step:Show that $\rho$ is surjective]We claim that $\rho: D(\mathfrak{p}) \to \operatorname{Gal}(k_{\mathfrak{p}}/\mathbb{F}_p)$ is surjective. It suffices to show surjectivity onto $\operatorname{Gal}(\bar{E}/\mathbb{F}_p)$, where $\bar{E} = \mathbb{F}_p(\bar{\alpha}_1, \ldots, \bar{\alpha}_n) \subset k_{\mathfrak{p}}$ is the splitting field of $\bar{f}$ over $\mathbb{F}_p$. Let $\bar{\tau} \in \operatorname{Gal}(\bar{E}/\mathbb{F}_p)$. The automorphism $\bar{\tau}$ is determined by its action on the roots $\bar{\alpha}_1, \ldots, \bar{\alpha}_n$ of $\bar{f}$. For each $i$, $\bar{\tau}(\bar{\alpha}_i) = \bar{\alpha}_{\pi(i)}$ for some permutation $\pi \in S_n$ (since $\bar{\tau}$ sends roots of $\bar{f}$ to roots of $\bar{f}$). We claim there exists $\sigma \in D(\mathfrak{p})$ such that $\sigma(\alpha_i) = \alpha_{\pi(i)}$ for each $i$. To construct $\sigma$: since $G = \operatorname{Gal}(E/\mathbb{Q})$ acts transitively on the roots of each irreducible factor of $f$ over $\mathbb{Q}$, and $E = \mathbb{Q}(\alpha_1, \ldots, \alpha_n)$, there exists $\sigma \in G$ inducing the permutation $\pi$ on the roots if and only if $\pi$ is compatible with the Galois action. More precisely, since $E/\mathbb{Q}$ is Galois, $G$ acts on the roots and the image of $G \hookrightarrow S_n$ determines which permutations are realised. Rather than constructing $\sigma$ directly, we establish surjectivity by a counting argument. The $G$-orbit of $\mathfrak{p}$ consists of all prime ideals of $\mathcal{O}_E$ lying over $(p)$. By the orbit-stabiliser theorem, $|G| = |D(\mathfrak{p})| \cdot |\text{orbit of } \mathfrak{p}|$. The image of $\rho$ is a subgroup of $\operatorname{Gal}(k_{\mathfrak{p}}/\mathbb{F}_p)$, and we have the inequality \begin{align*} |\operatorname{im}(\rho)| \leq |\operatorname{Gal}(k_{\mathfrak{p}}/\mathbb{F}_p)| = [k_{\mathfrak{p}} : \mathbb{F}_p]. \end{align*} In the unramified case (which the separability of $\bar{f}$ guarantees for our purposes), the kernel of $\rho$ is the **inertia group** $I(\mathfrak{p}) := \{\sigma \in D(\mathfrak{p}) : \bar{\sigma} = \operatorname{id}_{k_{\mathfrak{p}}}\}$. When $p$ is unramified in $\mathcal{O}_E$ — which holds when $\bar{f}$ is separable, since the discriminant of $f$ is not divisible by $p$ to high order — the inertia group is trivial: $I(\mathfrak{p}) = \{e\}$. In this case $\rho$ is injective, and from the fundamental identity $[E : \mathbb{Q}] = e(\mathfrak{p}|p) \cdot f(\mathfrak{p}|p) \cdot g$ (where $e$ is the ramification index, $f = [k_{\mathfrak{p}} : \mathbb{F}_p]$ is the residue degree, and $g$ is the number of primes over $p$), combined with $e = 1$ (unramified) and $|G| = efg = fg$, we get $|D(\mathfrak{p})| = |G|/g = ef = f = [k_{\mathfrak{p}} : \mathbb{F}_p]$. Since $\rho$ is injective and $|D(\mathfrak{p})| = |\operatorname{Gal}(k_{\mathfrak{p}}/\mathbb{F}_p)|$, the map $\rho$ is an isomorphism. For the general statement (without assuming $p$ is completely unramified in $\mathcal{O}_E$), the separability of $\bar{f}$ suffices to ensure that $\rho$ is surjective. The discriminant $\operatorname{disc}(f) = \prod_{i < j}(\alpha_i - \alpha_j)^2$ satisfies $\operatorname{disc}(\bar{f}) \not\equiv 0 \pmod{p}$ (since $\bar{f}$ is separable), which means $p \nmid \operatorname{disc}(f)$ in $\mathbb{Z}$. This implies that the prime $p$ does not ramify in the subring $\mathbb{Z}[\alpha_1, \ldots, \alpha_n]$, and the surjectivity of $\rho$ follows from standard algebraic number theory (the decomposition group surjects onto the residue field Galois group whenever the prime is unramified).[/step]

[guided]The surjectivity of $\rho$ is the deepest ingredient in the proof, and its full justification requires algebraic number theory beyond the scope of a Galois theory course. Let us trace the key ideas. The separability hypothesis on $\bar{f}$ is consumed here in an essential way. The discriminant $\operatorname{disc}(f) = \prod_{i < j}(\alpha_i - \alpha_j)^2 \in \mathbb{Z}$ satisfies \begin{align*} \operatorname{disc}(\bar{f}) = \prod_{i < j}(\bar{\alpha}_i - \bar{\alpha}_j)^2 = \pi\!\left(\prod_{i < j}(\alpha_i - \alpha_j)^2\right) = \pi(\operatorname{disc}(f)). \end{align*} Since $\bar{f}$ is separable, $\operatorname{disc}(\bar{f}) \neq 0$ in $\mathbb{F}_p$, which means $p \nmid \operatorname{disc}(f)$. In algebraic number theory, the condition $p \nmid \operatorname{disc}(f)$ implies that $p$ is unramified in $\mathbb{Z}[\alpha_1, \ldots, \alpha_n]$ (the order generated by the roots). While $\mathbb{Z}[\alpha_1, \ldots, \alpha_n]$ may be strictly smaller than $\mathcal{O}_E$, the unramifiedness transfers: the key property is that $\bar{f}$ being separable implies $\bar{f}$ has $n$ distinct roots modulo $\mathfrak{p}$, which forces the inertia group $I(\mathfrak{p})$ to act trivially on the roots $\bar{\alpha}_1, \ldots, \bar{\alpha}_n$ and hence trivially on the splitting field $\bar{E}$. With trivial inertia (at least on $\bar{E}$), the map $\rho$ restricted to $\operatorname{Gal}(\bar{E}/\mathbb{F}_p)$ is surjective. Concretely: $\operatorname{Gal}(\bar{E}/\mathbb{F}_p)$ is generated by $\operatorname{Fr}_p$ (by the [Galois Group of Finite Field Extension](/theorems/1277)). To show $\operatorname{Fr}_p \in \operatorname{im}(\rho)$, we need $\sigma \in D(\mathfrak{p})$ with $\bar{\sigma}(\bar{\alpha}_i) = \bar{\alpha}_i^p$ for all $i$. The existence of such a $\sigma$ is the content of the surjectivity claim. What would fail without separability? If $\bar{f}$ had a repeated root, say $\bar{\alpha}_i = \bar{\alpha}_j$ for $i \neq j$, then the reduction map would fail to be a bijection on roots, and the inertia group could permute roots non-trivially. The Frobenius would still exist in the residue field, but we could not lift it cleanly to an element of $G$ with the correct cycle type, because the bijection between roots of $f$ and roots of $\bar{f}$ would break down.[/guided]

[step:Lift the Frobenius to an element of $G$ with cycle type $(d_1, \ldots, d_r)$]By the surjectivity of $\rho$, there exists $\sigma \in D(\mathfrak{p}) \subset G$ such that $\rho(\sigma) = \bar{\sigma} = \operatorname{Fr}_p$ on $\bar{E}$. We show that $\sigma$, viewed as a permutation of $\{\alpha_1, \ldots, \alpha_n\}$, has cycle type $(d_1, \ldots, d_r)$. The reduction map $\pi$ provides a bijection $\alpha_i \mapsto \bar{\alpha}_i$ between the roots of $f$ and the roots of $\bar{f}$, and the following diagram commutes for each $i$: \begin{align*} \bar{\sigma}(\bar{\alpha}_i) = \bar{\sigma}(\pi(\alpha_i)) = \pi(\sigma(\alpha_i)) = \overline{\sigma(\alpha_i)}. \end{align*} That is, if $\sigma(\alpha_i) = \alpha_j$, then $\bar{\sigma}(\bar{\alpha}_i) = \bar{\alpha}_j$. Equivalently, the permutation induced by $\sigma$ on $\{\alpha_1, \ldots, \alpha_n\}$ is the same as the permutation induced by $\bar{\sigma} = \operatorname{Fr}_p$ on $\{\bar{\alpha}_1, \ldots, \bar{\alpha}_n\}$ (under the bijection $\alpha_i \leftrightarrow \bar{\alpha}_i$). From the analysis in the second step, $\operatorname{Fr}_p$ acts on $\{\bar{\alpha}_1, \ldots, \bar{\alpha}_n\}$ with cycle type $(d_1, d_2, \ldots, d_r)$. Since $\sigma$ induces the same permutation (after the identification $\alpha_i \leftrightarrow \bar{\alpha}_i$), $\sigma$ also has cycle type $(d_1, d_2, \ldots, d_r)$ as a permutation of $\{\alpha_1, \ldots, \alpha_n\}$. Since $\sigma \in D(\mathfrak{p}) \subset G$, the Galois group $G$ contains an element of cycle type $(d_1, d_2, \ldots, d_r)$.[/step]

[guided]This final step is where all the threads come together. The diagram \begin{align*} \sigma: \alpha_i &\mapsto \alpha_j \\ \pi: \alpha_i &\mapsto \bar{\alpha}_i, \quad \alpha_j \mapsto \bar{\alpha}_j \\ \bar{\sigma}: \bar{\alpha}_i &\mapsto \bar{\alpha}_j \end{align*} commutes because $\bar{\sigma}$ is defined as the reduction of $\sigma$ modulo $\mathfrak{p}$: $\bar{\sigma}(x + \mathfrak{p}) = \sigma(x) + \mathfrak{p}$. Applied to $x = \alpha_i$, this gives $\bar{\sigma}(\bar{\alpha}_i) = \overline{\sigma(\alpha_i)}$. The bijection $\alpha_i \leftrightarrow \bar{\alpha}_i$ is the key that transfers the cycle structure of $\operatorname{Fr}_p$ (an automorphism of $\bar{E}$) to the cycle structure of $\sigma$ (an automorphism of $E$). This bijection exists precisely because $\bar{f}$ is separable: if $\bar{f}$ had a repeated root, the map $\alpha_i \mapsto \bar{\alpha}_i$ would not be injective, and two distinct roots of $f$ could reduce to the same root of $\bar{f}$. In that case, the Frobenius would permute fewer than $n$ objects, and the cycle type would not correspond to a well-defined permutation in $S_n$. Why does $\sigma$ have cycle type $(d_1, \ldots, d_r)$ and not merely "the same cycle type as some automorphism of $\bar{E}$"? Because we chose $\bar{\sigma} = \operatorname{Fr}_p$ specifically, and we showed in the second step that $\operatorname{Fr}_p$ has cycle type $(d_1, \ldots, d_r)$ determined by the degrees of the irreducible factors of $\bar{f}$. To summarise the entire argument: the factorisation $\bar{f} = \bar{g}_1 \cdots \bar{g}_r$ into irreducibles of degrees $d_1, \ldots, d_r$ determines the cycle type of the Frobenius on the roots of $\bar{f}$. The decomposition group $D(\mathfrak{p})$ provides a lift of the Frobenius to an element $\sigma \in G$, and the separability of $\bar{f}$ ensures that the reduction bijection $\alpha_i \leftrightarrow \bar{\alpha}_i$ faithfully transfers the cycle structure. Therefore $G$ contains an element of cycle type $(d_1, \ldots, d_r)$.[/guided]