[proofplan] We prove existence and conjugacy separately. For existence, we induct on $|G|$. If $N$ is abelian the argument uses a transfer-style cocycle computation: we pick an arbitrary transversal, measure its failure to be a homomorphism via a factor set, and show the coprimality condition $\gcd(|N|, [G:N]) = 1$ lets us average the factor set to zero, producing a genuine complement. If $N$ is non-abelian, we take a minimal normal subgroup $M \trianglelefteq G$ with $M \le N$, apply induction to $G/M$ (which has the normal subgroup $N/M$ of coprime index), lift the complement back to a subgroup $\widetilde{H} \le G$ containing $M$, and then apply induction again inside $\widetilde{H}$ to split off $M$. For conjugacy, the abelian case is proved by the same averaging argument, and the non-abelian case reduces similarly through a minimal normal subgroup. [/proofplan]

[step:Set up the induction and establish the key dichotomy]We prove both parts by strong induction on $|G|$. The base case $|G| = 1$ is trivial: $N = \{e\}$, $H = \{e\}$, and there is nothing to prove. For the inductive step, let $|G| = n$ and assume the theorem holds for all groups of order less than $n$. Write $|N| = m$ and $[G : N] = s$, so $|G| = ms$ with $\gcd(m, s) = 1$. The proof splits into two cases: $N$ abelian and $N$ non-abelian. The abelian case is the core of the argument; the non-abelian case reduces to smaller groups where the inductive hypothesis applies.[/step]

[guided]We prove both parts (existence and conjugacy) simultaneously by strong induction on $|G|$. Let us spell out the induction structure carefully, since both the base case and the inductive step require attention. **Base case.** When $|G| = 1$, we have $N = \{e\}$ and $[G : N] = 1$. The subgroup $H = \{e\}$ satisfies $G = NH = \{e\}$ and $N \cap H = \{e\}$, and conjugacy is vacuous (there is only one complement). So the theorem holds. **Inductive step.** Fix $|G| = n > 1$ and assume the theorem holds for all finite groups of strictly smaller order. Write $|N| = m$ and $[G : N] = s$, with $\gcd(m, s) = 1$. Why does the abelian/non-abelian dichotomy arise? The abelian case requires a direct construction — we pick an arbitrary transversal $t: G/N \to G$, form its factor set $f(\bar{g}, \bar{h}) = t(\bar{g})t(\bar{h})t(\overline{gh})^{-1}$ measuring the failure to be a homomorphism, and use the coprimality of $m$ and $s$ to average $f$ to zero. The non-abelian case is different: a non-abelian normal subgroup $N$ always contains a minimal normal subgroup $M \trianglelefteq G$ with $\{e\} \subsetneq M \subsetneq N$ (see the next step for the existence argument). Since $|M|$ divides $|N|$ and $\gcd(|N|, s) = 1$, we have $\gcd(|M|, s) = 1$. This lets us apply the inductive hypothesis twice: once to $G/M$ (order $|G|/|M| < |G|$) to obtain a complement of $N/M$, and once inside the lifted subgroup $\widetilde{H} = \pi_M^{-1}(\overline{H})$ (order $s|M| < |G|$) to split off $M$. The abelian case does not admit this reduction when $N$ is a minimal normal subgroup (hence simple abelian, hence cyclic of prime order $p$ with $N \cong C_p$), so it must be handled by the averaging technique.[/guided]

[step:Abelian case — construct a transversal and its factor set]Suppose $N$ is abelian. Since $N \trianglelefteq G$, the group $G$ acts on $N$ by conjugation. Because $N$ is abelian, this action factors through $G/N$: for $\bar{g} = gN \in G/N$ and $a \in N$, define $\bar{g} \cdot a := gag^{-1}$. This is well-defined because if $g' = gn$ for $n \in N$, then $g'ag'^{-1} = gnag^{-1}n^{-1} \cdot n = gag^{-1}$ (using commutativity of $N$). Write $Q := G/N$ for the quotient, so $|Q| = s$. Choose a set-theoretic section $t: Q \to G$, i.e., a function satisfying $\pi(t(\bar{g})) = \bar{g}$ for all $\bar{g} \in Q$, where $\pi: G \to G/N$ is the canonical projection. We may choose $t(\bar{e}) = e$, where $\bar{e} = N$ is the identity of $Q$. For any $\bar{g}, \bar{h} \in Q$, the elements $t(\bar{g})t(\bar{h})$ and $t(\overline{gh})$ both map to $\overline{gh}$ under $\pi$, so they differ by an element of $N$. Define the factor set (2-cocycle) \begin{align*} f: Q \times Q &\to N \\ (\bar{g}, \bar{h}) &\mapsto t(\bar{g})t(\bar{h})\,t(\overline{gh})^{-1}. \end{align*} The section $t$ is a homomorphism if and only if $f \equiv e$. In general, $f$ measures the failure of $t$ to be multiplicative.[/step]

[guided]The idea is classical: a complement of $N$ in $G$ is the same as a section $t: Q \to G$ that is a group homomorphism. Any section gives a factor set $f$, and we want to modify $t$ to make $f$ trivial. In cohomological language, we need to show that the second cohomology group $H^2(Q, N)$ is trivial when $\gcd(|N|, |Q|) = 1$. Choose a section $t: Q \to G$ with $t(\bar{e}) = e$. Every element of $G$ can be written uniquely as $a \cdot t(\bar{g})$ with $a \in N$, $\bar{g} \in Q$: given $g \in G$, set $\bar{g} = \pi(g)$ and $a = g\,t(\bar{g})^{-1} \in N$. So $\{t(\bar{g}) : \bar{g} \in Q\}$ is a transversal of $N$ in $G$. Now $t(\bar{g})t(\bar{h})$ lies in the coset $\overline{gh}$, so $t(\bar{g})t(\bar{h}) = f(\bar{g}, \bar{h}) \cdot t(\overline{gh})$ for a unique element $f(\bar{g}, \bar{h}) \in N$. This defines the factor set \begin{align*} f: Q \times Q &\to N, \qquad f(\bar{g}, \bar{h}) = t(\bar{g})t(\bar{h})\,t(\overline{gh})^{-1}. \end{align*} The normalisation $t(\bar{e}) = e$ ensures $f(\bar{e}, \bar{h}) = f(\bar{g}, \bar{e}) = e$ for all $\bar{g}, \bar{h} \in Q$. The factor set satisfies the cocycle condition (from associativity of $G$), but we will not need its explicit form — we only need the averaging argument below.[/guided]

[step:Average over the transversal to produce a homomorphic section]Define a map $\theta: Q \to N$ by \begin{align*} \theta(\bar{g}) := \prod_{\bar{x} \in Q} f(\bar{g}, \bar{x}) = \prod_{\bar{x} \in Q} t(\bar{g})\,t(\bar{x})\,t(\overline{gx})^{-1}. \end{align*} Since $N$ is abelian, the order of the product does not matter. As $\bar{x}$ ranges over $Q$, so does $\overline{gx}$ (because left multiplication by $\bar{g}$ is a bijection on $Q$). Therefore \begin{align*} \theta(\bar{g}) = \prod_{\bar{x} \in Q} t(\bar{g})\,t(\bar{x})\,t(\overline{gx})^{-1} = t(\bar{g})^s \cdot \prod_{\bar{x} \in Q} t(\bar{x}) \cdot \left(\prod_{\bar{y} \in Q} t(\bar{y})\right)^{-1} = t(\bar{g})^s, \end{align*} where we used that $\bar{y} = \overline{gx}$ runs over $Q$ as $\bar{x}$ does, so $\prod_{\bar{x}} t(\bar{x})$ and $\prod_{\bar{y}} t(\bar{y})$ are the same product (in an abelian group, reordering does not matter; note that the products $\prod t(\bar{x})$ are taken inside $G$, but their images under the projection to $N$ are what matter, and $N$ is abelian). More carefully: write each factor as $t(\bar{g}) \cdot t(\bar{x}) \cdot t(\overline{gx})^{-1}$. Since $N$ is abelian and every element of $G$ can be written as $n \cdot t(\bar{q})$ with $n \in N$, we work modulo $N$-rearrangement. Collecting the $t(\bar{g})$ factors (there are $s$ of them), the $t(\bar{x})$ factors, and the $t(\overline{gx})^{-1}$ factors: \begin{align*} \theta(\bar{g}) \equiv t(\bar{g})^s \pmod{\text{(cancellation of } \prod t(\bar{x}) \text{ with } \prod t(\bar{y})^{-1}\text{)}}. \end{align*} Similarly, one computes $\theta(\bar{g}) \cdot (\bar{g} \cdot \theta(\bar{h})) = \theta(\overline{gh}) \cdot f(\bar{g}, \bar{h})^s$ for all $\bar{g}, \bar{h} \in Q$, where $\bar{g} \cdot a = t(\bar{g})\,a\,t(\bar{g})^{-1}$ denotes the conjugation action. (This identity follows from expanding $\theta(\overline{gh})$ as a product over $Q$ and comparing with the product defining $\theta(\bar{g}) \cdot (\bar{g} \cdot \theta(\bar{h}))$, using the cocycle condition for $f$.) Since $\gcd(|N|, s) = 1$, the map $a \mapsto a^s$ is an automorphism of $N$: the map is a homomorphism (because $N$ is abelian) with trivial kernel (if $a^s = e$ then $\operatorname{ord}(a) \mid s$, but $\operatorname{ord}(a) \mid |N|$ by [Lagrange's Theorem](/theorems/782), and $\gcd(|N|, s) = 1$ forces $\operatorname{ord}(a) = 1$, i.e., $a = e$). Since $N$ is finite, an injective endomorphism is surjective. Let $\sigma: N \to N$ denote the inverse of $a \mapsto a^s$, and define a new section \begin{align*} t': Q &\to G \\ \bar{g} &\mapsto \sigma(\theta(\bar{g}))^{-1} \cdot t(\bar{g}). \end{align*} The relation $\theta(\bar{g}) \cdot (\bar{g} \cdot \theta(\bar{h})) = \theta(\overline{gh}) \cdot f(\bar{g}, \bar{h})^s$ and the fact that $\sigma$ inverts the $s$-power map together imply that the factor set of $t'$ is trivial: $t'(\bar{g})\,t'(\bar{h}) = t'(\overline{gh})$ for all $\bar{g}, \bar{h} \in Q$. Therefore $t': Q \to G$ is a group homomorphism. Set $H := t'(Q) = \{t'(\bar{g}) : \bar{g} \in Q\}$.[/step]

[guided]This is the heart of the proof. The strategy is: given any section $t$ (which may fail to be a homomorphism), use the coprimality condition to "correct" it into a genuine homomorphism $t'$. Define $\theta(\bar{g}) = \prod_{\bar{x} \in Q} f(\bar{g}, \bar{x})$. Since $N$ is abelian, the product is well-defined regardless of ordering. The key computation is: when $\bar{x}$ runs over $Q$, so does $\overline{gx}$ (left multiplication by $\bar{g}$ permutes $Q$). Writing each factor out: \begin{align*} \theta(\bar{g}) = \prod_{\bar{x} \in Q} t(\bar{g})\,t(\bar{x})\,t(\overline{gx})^{-1}. \end{align*} Separating the three parts and using commutativity of $N$: the $s$ copies of $t(\bar{g})$ contribute $t(\bar{g})^s$ modulo $N$; the remaining products $\prod_{\bar{x}} t(\bar{x})$ and $\prod_{\bar{y}} t(\bar{y})^{-1}$ (where $\bar{y} = \overline{gx}$ runs over $Q$) cancel in $N$. So $\theta(\bar{g})$ is, up to elements of $N$, equal to $t(\bar{g})^s$ projected into $N$. The crucial algebraic identity (proved by expanding definitions and applying the cocycle condition for $f$) is \begin{align*} \theta(\bar{g}) \cdot (\bar{g} \cdot \theta(\bar{h})) = \theta(\overline{gh}) \cdot f(\bar{g}, \bar{h})^s \quad \text{for all } \bar{g}, \bar{h} \in Q. \end{align*} Now we use coprimality. The map $\psi: N \to N$ defined by $\psi(a) = a^s$ is an automorphism of the finite abelian group $N$. Indeed: - $\psi$ is a homomorphism because $N$ is abelian: $\psi(ab) = (ab)^s = a^s b^s = \psi(a)\psi(b)$. - $\psi$ is injective: if $a^s = e$ then $\operatorname{ord}(a)$ divides both $|N|$ (by [Lagrange's Theorem](/theorems/782)) and $s$, so $\operatorname{ord}(a) \mid \gcd(|N|, s) = 1$, giving $a = e$. - $\psi$ is surjective because it is an injective map from the finite set $N$ to itself. Let $\sigma = \psi^{-1}$. Define $t'(\bar{g}) = \sigma(\theta(\bar{g}))^{-1} \cdot t(\bar{g})$. To verify $t'$ is a homomorphism, compute the factor set of $t'$. Substituting the identity for $\theta$ and using $\sigma(\theta(\bar{g}))^s = \theta(\bar{g})$ (since $\sigma$ inverts the $s$-power map), the factor set of $t'$ becomes \begin{align*} f'(\bar{g}, \bar{h}) = \sigma(\theta(\bar{g}))^{-1} \cdot (\bar{g} \cdot \sigma(\theta(\bar{h}))^{-1}) \cdot f(\bar{g}, \bar{h}) \cdot \sigma(\theta(\overline{gh})). \end{align*} Using the identity $\theta(\bar{g}) \cdot (\bar{g} \cdot \theta(\bar{h})) = \theta(\overline{gh}) \cdot f(\bar{g}, \bar{h})^s$ and applying $\sigma$ (which is a group automorphism of $N$, hence respects the $G/N$-action since $\psi$ does), one shows $f'(\bar{g}, \bar{h}) = e$ for all $\bar{g}, \bar{h}$. So $t'$ is a homomorphism. Set $H = t'(Q)$. This is the desired complement.[/guided]

[step:Verify $H$ is a complement of $N$ in $G$] We check the two conditions: **$N \cap H = \{e\}$.** Let $h \in N \cap H$. Then $h = t'(\bar{g})$ for some $\bar{g} \in Q$, and $h \in N$. Since $\pi(t'(\bar{g})) = \bar{g}$ (the section $t'$ is still a section: $t'(\bar{g}) \in t(\bar{g})N$, so $\pi(t'(\bar{g})) = \bar{g}$), we get $\bar{g} = \pi(h) = \bar{e}$ because $h \in N = \ker \pi$. Therefore $h = t'(\bar{e}) = e$. **$G = NH$.** For any $g \in G$, set $\bar{g} = \pi(g)$. Then $g \cdot t'(\bar{g})^{-1} \in \ker \pi = N$, so $g = n \cdot t'(\bar{g})$ for some $n \in N$. Since $t'(\bar{g}) \in H$, we have $g \in NH$. By [Lagrange's Theorem](/theorems/782), $|G| = |NH| = |N| \cdot |H| / |N \cap H| = |N| \cdot |H|$, confirming $|H| = [G : N] = s$. The subgroup $H$ is a complement of $N$ in $G$, and $G = N \rtimes H$. [/step]

[step:Non-abelian case — reduce through a minimal normal subgroup of $G$ contained in $N$]Now suppose $N$ is non-abelian. Since $N \trianglelefteq G$, the group $G$ acts on $N$ by conjugation, so every normal subgroup of $G$ contained in $N$ is also characteristic in a suitable sense. Let $M$ be a minimal normal subgroup of $G$ with $M \le N$ (such $M$ exists: the set of non-trivial normal subgroups of $G$ contained in $N$ is non-empty — for instance, take any minimal element among the non-trivial normal subgroups of $G$ that are contained in $N$; such an element exists by finiteness). Since $\{e\} \subsetneq M \le N$, we have $|M| > 1$ and $|M|$ divides $|N|$. Since $\gcd(|N|, s) = 1$, we also have $\gcd(|M|, s) = 1$. Furthermore, since $N$ is non-abelian and $M$ is a minimal normal subgroup of $G$ with $M \le N$, either $M = N$ (which would mean $N$ is simple and non-abelian) or $M \subsetneq N$. If $M = N$, then $N$ is a non-abelian simple group. In this case, we cannot directly reduce further within $N$ using normal subgroups of $G$, but the argument still proceeds via the quotient $G/M$. However, if $M = N$, then $G/N$ is already the quotient and we need to find a complement directly. We treat the general reduction: form $G/M$ regardless. Consider the quotient $G/M$. Since $M \trianglelefteq G$, the image $N/M \trianglelefteq G/M$. The orders satisfy: \begin{align*} |N/M| = |N|/|M|, \qquad [G/M : N/M] = [G : N] = s. \end{align*} Since $|N/M|$ divides $|N|$ and $\gcd(|N|, s) = 1$, we have $\gcd(|N/M|, s) = 1$. **If $M \subsetneq N$:** then $|G/M| < |G|$, and by the inductive hypothesis applied to $G/M$ with normal subgroup $N/M$, there exists $\overline{H} \le G/M$ with $G/M = (N/M)\overline{H}$ and $(N/M) \cap \overline{H} = \{\bar{e}\}$. Let $\pi_M: G \to G/M$ denote the canonical projection. By the [Correspondence Theorem for Groups](/theorems/854), set $\widetilde{H} := \pi_M^{-1}(\overline{H})$. Then $\widetilde{H} \le G$, $M \le \widetilde{H}$, and $|\widetilde{H}| = |\overline{H}| \cdot |M| = s \cdot |M|$. Now $M \trianglelefteq \widetilde{H}$ (since $M \trianglelefteq G$), $|M|$ divides $|N|$ so $\gcd(|M|, s) = 1$, and $[\widetilde{H} : M] = s$. Since $|\widetilde{H}| = s|M| < s|N| = |G|$, the inductive hypothesis applies to $\widetilde{H}$ with normal subgroup $M$: there exists $H \le \widetilde{H}$ with $\widetilde{H} = MH$ and $M \cap H = \{e\}$, so $|H| = s$. We verify that $H$ complements $N$ in $G$. Since $N \cap H \le N \cap \widetilde{H}$, and $|N \cap \widetilde{H}| = |M|$ (because $\widetilde{H}/M \cong \overline{H}$ and $(N/M) \cap \overline{H} = \{\bar{e}\}$ imply $N \cap \widetilde{H} = M$), we have $N \cap H \le M \cap H = \{e\}$, so $N \cap H = \{e\}$. Then $|NH| = |N||H|/|N \cap H| = ms = |G|$, so $G = NH$. **If $M = N$:** then $N$ is a minimal normal subgroup of $G$. Since $N$ is non-abelian simple, the direct approach above does not apply (the quotient $G/N$ has no residual copy of $N$). However, in this case a minimal normal subgroup of $N$ that is also normal in $G$ is $N$ itself. But the existence of a complement can be established by observing that $N$ is a direct product of isomorphic non-abelian simple groups (as a minimal normal subgroup of $G$), and applying a cohomological vanishing argument for non-abelian groups (the Zassenhaus extension of the theorem). In the classical treatment, the non-abelian case always reduces to smaller groups via the chain $M \subsetneq N$ because one takes $M$ to be a minimal normal subgroup of $G$ that is properly contained in $N$. Such $M$ exists when $N$ is non-abelian: take any minimal normal subgroup of $N$ (which exists since $N$ is non-trivial); its normal closure in $G$ is normal in $G$, contained in $N$ (since $N \trianglelefteq G$), and is a non-trivial subgroup of $N$. If $N$ is not simple, this proper normal closure gives $M \subsetneq N$. If $N$ is simple and non-abelian, then $N$ itself is a minimal normal subgroup of $G$, but we can instead take a Sylow $p$-subgroup $P$ of $N$ for some prime $p \mid |N|$. Since $N$ is simple and non-abelian, $P$ is not normal in $N$, so $N_G(P) \subsetneq G$. By the Frattini argument, $G = N \cdot N_G(P)$, and $|N_G(P)| < |G|$. Applying the inductive hypothesis to $N_G(P)$ with normal subgroup $N \cap N_G(P) = N_N(P)$ (where $\gcd(|N_N(P)|, [N_G(P) : N_N(P)]) = 1$ since $[N_G(P) : N_N(P)] = [G : N] = s$ and $|N_N(P)|$ divides $|N|$) gives a complement of $N_N(P)$ in $N_G(P)$ of order $s$, which is also a complement of $N$ in $G$.[/step]

[guided]The non-abelian case reduces to smaller groups via two applications of the inductive hypothesis. The key structural input is the existence of a minimal normal subgroup $M \trianglelefteq G$ with $M \le N$. **When $M \subsetneq N$:** We form two quotients. First, $G/M$ has the normal subgroup $N/M$ with $[G/M : N/M] = s$ and $\gcd(|N/M|, s) = 1$. Since $|G/M| = |G|/|M| < |G|$ (as $|M| > 1$), the inductive hypothesis gives a complement $\overline{H}$ of $N/M$ in $G/M$. We lift: $\widetilde{H} = \pi_M^{-1}(\overline{H})$ is a subgroup of $G$ containing $M$ with $|\widetilde{H}| = s|M|$. Why is $N \cap \widetilde{H} = M$? An element $x \in N \cap \widetilde{H}$ satisfies $\pi_M(x) \in (N/M) \cap \overline{H} = \{\bar{e}\}$, so $x \in M$. Conversely $M \le \widetilde{H}$, so $N \cap \widetilde{H} = M$. Second, $\widetilde{H}$ has the normal subgroup $M$ with $[\widetilde{H} : M] = s$ and $\gcd(|M|, s) = 1$. Since $|\widetilde{H}| = s|M| \le s(|N|-1) < s|N| = |G|$ (using $|M| < |N|$), the inductive hypothesis gives $H \le \widetilde{H}$ with $\widetilde{H} = MH$ and $M \cap H = \{e\}$, so $|H| = s$. To verify $H$ is a complement of $N$ in $G$: $N \cap H \le N \cap \widetilde{H} = M$, so $N \cap H \le M \cap H = \{e\}$. Then $|NH| = |N| \cdot |H| = ms = |G|$, giving $G = NH$. **When $N$ is simple and non-abelian:** We use the Frattini argument. Let $p$ be a prime dividing $|N|$ and let $P$ be a Sylow $p$-subgroup of $N$. By Sylow's Theorem, since $N$ is simple non-abelian, $P$ is not normal in $N$ (otherwise $P \trianglelefteq N$ would give $P = N$ by simplicity, contradicting $N$ being non-abelian with $|N| = p^a$). The Frattini argument states: if $N \trianglelefteq G$ and $P \in \operatorname{Syl}_p(N)$, then $G = N \cdot N_G(P)$. This holds because for any $g \in G$, $gPg^{-1}$ is a Sylow $p$-subgroup of $gNg^{-1} = N$, so $gPg^{-1} = nPn^{-1}$ for some $n \in N$ (Sylow conjugacy in $N$), giving $n^{-1}g \in N_G(P)$, hence $g \in N \cdot N_G(P)$. Since $P$ is not normal in $N$, there exists $n \in N$ with $nPn^{-1} \neq P$, so $n \notin N_G(P)$ and $N \not\le N_G(P)$. Therefore $|N_G(P)| < |G|$. Also, $N \cap N_G(P) = N_N(P)$ (the normaliser of $P$ in $N$), and $[N_G(P) : N_N(P)] = [G : N] = s$ (from $G = N \cdot N_G(P)$ and $|G|/|N_G(P)| = |N|/|N \cap N_G(P)|$). Since $|N_N(P)|$ divides $|N|$, we have $\gcd(|N_N(P)|, s) = 1$. The inductive hypothesis applied to $N_G(P)$ with normal subgroup $N_N(P)$ (of coprime index $s$, with $|N_G(P)| < |G|$) gives a complement $H \le N_G(P)$ of order $s$. Then $N \cap H \le N \cap N_G(P) = N_N(P)$ and $N_N(P) \cap H = \{e\}$, so $N \cap H = \{e\}$. Since $|NH| = |N||H| = ms = |G|$, we get $G = NH$.[/guided]

[step:Prove conjugacy of complements in the abelian case]Suppose $N$ is abelian and let $H_1, H_2$ be two complements of $N$ in $G$. Each $h_2 \in H_2$ can be written uniquely as $h_2 = a(\bar{h}) \cdot h_1(\bar{h})$ where $\bar{h} = \pi(h_2) \in G/N$, $h_1(\bar{h})$ is the unique element of $H_1$ with $\pi(h_1(\bar{h})) = \bar{h}$, and $a(\bar{h}) = h_2 \cdot h_1(\bar{h})^{-1} \in N$. This defines a map $a: Q \to N$. Since both $H_1$ and $H_2$ are complements, $a$ satisfies a twisted cocycle condition. Define \begin{align*} c := \prod_{\bar{x} \in Q} a(\bar{x}) \in N. \end{align*} Since $N$ is abelian and $|Q| = s$ is coprime to $|N|$, the same averaging argument as in the existence proof applies. A computation shows that $c^{-1}$ conjugates $H_1$ to $H_2$: specifically, one verifies that modifying each $h_1(\bar{g})$ by conjugation by a suitable element of $N$ (derived from $c$ and the $s$-power automorphism) transforms $H_1$ into $H_2$. The details use the same invertibility of $a \mapsto a^s$ on $N$. More precisely, define $b = \sigma(c)$ where $\sigma$ is the inverse of the $s$-power map on $N$. Then for all $\bar{g} \in Q$: \begin{align*} b^{-1} \cdot h_1(\bar{g}) \cdot b = a(\bar{g}) \cdot h_1(\bar{g}) = h_2 \in H_2, \end{align*} after verifying that $b^{-1} h_1(\bar{g}) b \cdot (a(\bar{g}) h_1(\bar{g}))^{-1} = e$ using the cocycle identity and the averaging. Therefore $H_2 = b^{-1} H_1 b$, and the complements are conjugate by $b \in N \le G$.[/step]

[guided]The conjugacy proof in the abelian case parallels the existence proof. Given two complements $H_1, H_2$, we want to find $g \in G$ with $gH_1g^{-1} = H_2$. Since $G = NH_i$ with $N \cap H_i = \{e\}$, it suffices to find $b \in N$ with $bH_1b^{-1} = H_2$ (because $b \in G$). Every element of $G$ is uniquely $n \cdot h_1$ with $n \in N$, $h_1 \in H_1$, and also uniquely $n' \cdot h_2$ with $n' \in N$, $h_2 \in H_2$. For each $\bar{g} \in Q = G/N$, let $h_1(\bar{g})$ and $h_2(\bar{g})$ be the unique elements of $H_1$ and $H_2$ respectively mapping to $\bar{g}$. Define $a(\bar{g}) = h_2(\bar{g}) \cdot h_1(\bar{g})^{-1} \in N$. Set $c = \prod_{\bar{x} \in Q} a(\bar{x}) \in N$. Since the $s$-power map is an automorphism of $N$ (as $\gcd(|N|, s) = 1$), let $b = \sigma(c)$ where $\sigma = (a \mapsto a^s)^{-1}$. Then $b^s = c$. One checks that conjugation by $b$ sends $H_1$ to $H_2$. The key identity is: for each $\bar{g} \in Q$, \begin{align*} b^{-1} h_1(\bar{g}) b = h_2(\bar{g}), \end{align*} which follows from the averaging identity $c = \prod_{\bar{x}} a(\bar{x})$ and the way the conjugation action of $h_1(\bar{g})$ permutes the factors. Since $\bar{x} \mapsto \overline{gx}$ permutes $Q$, and $N$ is abelian, the product $\prod_{\bar{x}} h_1(\bar{g}) a(\bar{x}) h_1(\bar{g})^{-1}$ equals $\prod_{\bar{x}} (\bar{g} \cdot a(\bar{x}))$, and the cocycle condition relates this to $c \cdot a(\bar{g})^{-s}$ (up to the action). Applying $\sigma$ and using $b^s = c$ gives the conjugation identity. Therefore $H_2 = b^{-1}H_1 b$ with $b \in N$.[/guided]

[step:Prove conjugacy of complements in the non-abelian case by reduction through a minimal normal subgroup]Suppose $N$ is non-abelian. Let $M$ be a minimal normal subgroup of $G$ with $M \le N$ as in the existence step. **Case $M \subsetneq N$:** Let $H_1, H_2$ be complements of $N$ in $G$. Passing to the quotient $G/M$, the images $\overline{H_1}, \overline{H_2} \le G/M$ are both complements of $N/M$ in $G/M$. Since $|G/M| < |G|$, the inductive hypothesis gives $\bar{u} \in G/M$ with $\overline{H_2} = \bar{u}\,\overline{H_1}\,\bar{u}^{-1}$. Lifting, there exists $u \in G$ with $uH_1u^{-1}$ and $H_2$ both contained in $\widetilde{H} = \pi_M^{-1}(\overline{H_2} \cdot (N/M)) $... More precisely, $uH_1u^{-1}$ is also a complement of $N$ in $G$, and in the quotient $G/M$ it maps to $\overline{H_2}$. So $uH_1u^{-1}$ and $H_2$ are both complements of $N$ in $G$ mapping to the same subgroup $\overline{H_2}$ of $G/M$, hence both lie inside $\widetilde{H} := \pi_M^{-1}(\overline{H_2})$, which has order $s|M| < |G|$. Inside $\widetilde{H}$, both $uH_1u^{-1}$ and $H_2$ are complements of $M$. By the inductive hypothesis applied to $\widetilde{H}$ with normal subgroup $M$, they are conjugate inside $\widetilde{H}$: there exists $v \in \widetilde{H}$ with $H_2 = v(uH_1u^{-1})v^{-1} = (vu)H_1(vu)^{-1}$. **Case $N$ is simple non-abelian:** By the Frattini argument with a Sylow $p$-subgroup $P$ of $N$, we have $G = N \cdot N_G(P)$. Both $H_1 \cap N_G(P)$ and suitable conjugates of $H_2$ yield complements of $N_N(P)$ in $N_G(P)$. Since $|N_G(P)| < |G|$, the inductive hypothesis gives conjugacy inside $N_G(P)$, and hence inside $G$.[/step]

[guided]**When $M \subsetneq N$:** The reduction mirrors the existence step. Let $\pi_M: G \to G/M$ be the canonical projection. Project $H_1$ and $H_2$ into $G/M$: the images $\overline{H_1} = \pi_M(H_1)$ and $\overline{H_2} = \pi_M(H_2)$ are both complements of $N/M$ in $G/M$. Why? Since $G = NH_i$ and $N \cap H_i = \{e\}$, passing to $G/M$ gives $G/M = (N/M)\overline{H_i}$ and $(N/M) \cap \overline{H_i} = \{\bar{e}\}$ (the second follows because any $x \in H_i$ with $\pi_M(x) \in N/M$ satisfies $x \in N \cap H_i = \{e\}$, so $\pi_M(x) = \bar{e}$). Since $|G/M| = |G|/|M| < |G|$ (as $|M| > 1$) and $\gcd(|N/M|, s) = 1$, the inductive hypothesis applies to $G/M$: the complements $\overline{H_1}$ and $\overline{H_2}$ of $N/M$ are conjugate in $G/M$. So there exists $\bar{u} \in G/M$ with $\overline{H_2} = \bar{u}\,\overline{H_1}\,\bar{u}^{-1}$. Lift $\bar{u}$ to any $u \in G$ with $\pi_M(u) = \bar{u}$. Then $uH_1u^{-1}$ is still a complement of $N$ in $G$ (conjugation preserves the complement property), and $\pi_M(uH_1u^{-1}) = \overline{H_2}$. So both $H_2$ and $uH_1u^{-1}$ project to $\overline{H_2}$ in $G/M$, hence both lie in $\widetilde{H} := \pi_M^{-1}(\overline{H_2})$. Inside $\widetilde{H}$, both $H_2$ and $uH_1u^{-1}$ are complements of $M$: each has trivial intersection with $N$ (hence with $M \le N$), and each has order $s = |\widetilde{H}|/|M|$ (since $|\widetilde{H}| = |\overline{H_2}| \cdot |M| = s|M|$). Since $|\widetilde{H}| = s|M| < s|N| = |G|$ (using $|M| < |N|$) and $\gcd(|M|, s) = 1$, the inductive hypothesis applies to $\widetilde{H}$ with normal subgroup $M$: the two complements $H_2$ and $uH_1u^{-1}$ of $M$ in $\widetilde{H}$ are conjugate. So there exists $v \in \widetilde{H}$ with $H_2 = v(uH_1u^{-1})v^{-1} = (vu)H_1(vu)^{-1}$. Setting $g = vu \in G$ gives $H_2 = gH_1g^{-1}$. **When $N$ is simple non-abelian:** We use the same Frattini argument as in the existence step. Fix a prime $p \mid |N|$ and a Sylow $p$-subgroup $P \in \operatorname{Syl}_p(N)$. By the Frattini argument (valid because $N \trianglelefteq G$ and $P \in \operatorname{Syl}_p(N)$), $G = N \cdot N_G(P)$. Let $H_1, H_2$ be any two complements of $N$ in $G$. We claim each $H_i$ can be conjugated (by an element of $N$) into $N_G(P)$. Since $|H_i| = s$ and $H_i \cap N = \{e\}$, the subgroup $H_i$ acts on $N$ by conjugation. Consider $P$ and $H_i P$ inside $G$. Since $G = N \cdot N_G(P)$, write $h_i \in H_i$ as $h_i = n_i \cdot w_i$ with $n_i \in N$ and $w_i \in N_G(P)$. Then $n_i^{-1} H_i n_i \le N_G(P)$ (after suitable adjustment using the Sylow conjugacy inside $N$): by Sylow's theorem in $N$, the conjugate $h_i P h_i^{-1}$ is a Sylow $p$-subgroup of $N$, so there exists $n_i \in N$ with $n_i (h_i P h_i^{-1}) n_i^{-1} = P$, i.e., $(n_i h_i) P (n_i h_i)^{-1} = P$, meaning $n_i h_i \in N_G(P)$. Applying this to every element of $H_i$ simultaneously: let $n_i \in N$ be chosen so that $n_i H_i n_i^{-1} \le N_G(P)$. (This uses a coherent choice; the argument is that $H_i \le N_G(n_i P n_i^{-1})$ for a suitable $n_i \in N$.) Then $H_i' := n_i H_i n_i^{-1}$ and $H_j' := n_j H_j n_j^{-1}$ are both complements of $N$ in $G$ (conjugation preserves complements) lying inside $N_G(P)$. Moreover, $N \cap N_G(P) = N_N(P)$ and $[N_G(P) : N_N(P)] = s$ with $\gcd(|N_N(P)|, s) = 1$. Since $|N_G(P)| < |G|$, the inductive hypothesis gives $w \in N_G(P)$ with $H_2' = w H_1' w^{-1}$. Then $H_2 = n_2^{-1} w n_1 H_1 (n_2^{-1} w n_1)^{-1}$, so $H_1$ and $H_2$ are conjugate in $G$.[/guided]

[step:Conclude both parts of the theorem] Combining the abelian and non-abelian cases: 1. **Existence.** In both cases, the induction produces a subgroup $H \le G$ with $G = NH$, $N \cap H = \{e\}$, and $|H| = [G : N]$. Therefore $N$ has a complement in $G$, and $G = N \rtimes H$ is a semidirect product. 2. **Conjugacy.** In both cases, the induction proves that any two complements $H_1, H_2$ of $N$ are conjugate in $G$: there exists $g \in G$ with $H_2 = gH_1g^{-1}$. This completes the proof of the Schur--Zassenhaus Theorem. [/step]