Normal subgroup of prime index

This is a standard exercise, and the answer is that the statement is true, but the proof is rather different from the elementary way in which the $p=2$ case can be proven.

Let $H$ be a subgroup of index $p$ where $p$ is the smallest prime that divides $|G|$. Then $G$ acts on the set of left cosets of $H$, $\{gH\mid g\in G\}$ by left multiplication, $x\cdot(gH) = xgH$.

This action induces a homomorphism from $G\to S_p$, whose kernel is contained in $H$. Let $K$ be the kernel. Then $G/K$ is isomorphic to a subgroup of $S_p$, and so has order dividing $p!$. But it must also have order dividing $|G|$, and since $p$ is the smallest prime that divides $|G|$, it follows that $|G/K|=p$. Since $|G/K| = [G:K]=[G:H][H:K] = p[H:K]$, it follows that $[H:K]=1$, so $K=H$. Since $K$ is normal, $H$ was in fact normal.

Here is a slightly different way to prove the result:

We will do it by induction on $|G|$. If $G$ has just one subgroup of index $p$ then clearly that subgroup is normal, so let $H_1$ and $H_2$ be distinct subgroups of index $p$. We then have that $|H_1H_2|$ is a multiple of $|H_1|$, but due to the choice of $p$ we must in fact have $H_1H_2 = G$ which means that if we let $K = H_1 \cap H_2$ then $K$ has index $p$ in $H_1$ and $H_2$ so by induction we know that $K$ is normal in $H_1$ and $H_2$ and thus normal in $G$. Now we know that $G/K$ has order $p^2$ so it is abelian. Now since both $H_1$ and $H_2$ contain $K$ they correspond to subgroups of $G/K$ and since this is abelian, they correspond to normal subgroups, which shows that they are normal in $G$ as desired.

Hint: Consider the set of cosets $G/H$ of which there are $p$. Then $G$ acts on these cosets by left multiplication. So you have a homomorphism $\phi: G \rightarrow S_p$. If $p$ is the smallest prime dividing $|G|$ then what can you say about $|\mathrm{im} \phi|$ and what does this imply about $\ker \phi$?