I've always wanted a proof I can remember, and I think I've found one.

• Let $G$ be a group such that $|G| = p^n m$ where $p$ does not divide $m$.
• We start by considering the set of all subsets of $G$ of size $p^n$. Call this set $\Omega$.
• We will prove the existence of a special subset $S \subseteq G$ such that $S \in \Omega$, and $|Stab(S)| = p^n$. That is, $|S| = p^n$ and $|Stab(S) = p^n$. This is somewhat natural, since the only way to get subgroups out of actions is to consider stabilizers.
• We need to show the existence of an $S \in \Omega$ such that $Stab(S)$ has maximal cardinality.

§ Lemma: $\binom{pa}{pb} \equiv_p \binom{a}{b}$:

• this is the coefficient of $x^{pb}$ in $(x + 1)^{pa}$. But modulo $p$, this is the same as the coefficient of $x^{pb}$ in $(x^p + 1^p)^a$. The latter is $\binom{a}{b}$. Thus, $\binom{ap}{bp} \equiv_p \binom{a}{b}$ (modulo $p$).

§ Continuing: Size of $\Omega$ modulo $p$:

• Let us begin by considering $|\Omega|$. This is $\binom{p^n m}{p^n}$ since we pick all subsets of size $p^n$ from $p^n$ m. See that if we want to calculate $\binom{pa}{pb}$, this is the coefficient of $x^{pb}$ in $(x + 1)^{pa}$. But modulo $p$, this is the same as the coefficient of $x^{pb}$ in $(x^p + 1^p)^a$. The latter is $\binom{a}{b}$. Thus, $\binom{ap}{bp} \equiv_p \binom{a}{b}$ (modulo $p$). Iterating the lemma shows us that $\binom{p^n m}{p^n} = m$. Thus, $p$ does not divide $|\Omega|$, since $m$ was the $p$-free part of $|G|$.
• This implies that there is some orbit $O \subset \Omega$ whose size is not divisible by $p$. --- Break $\Omega$ into orbits. Since the left hand side $|\Omega|$ is not divisible by $p$, there is some term in the orbits size that is not divisible by $p$.
• Let the orbit $O$ be generated by a set $S \in \Omega$. So $O = Orb(S)$. Now orbit stabilizer tells us that $|Orb(S)| \cdot |Stab(S)| = |G|$. Since $|O = Orb(S)|$ is not divisible by $p$, this means that $Stab(S)$ must be of size at least $p^n$. It could also have some divisors of $m$ inside it.
• Next, we will show that $Stab(S)$ can be at most $p^n$.

§ Lemma: size of stabilizer of subset when action is free:

• Let a group $G$ act freely on a set $S$. This means that for all group elements $g$, if for any $s$we have $g(s) = s$, then we must have $g = id$. In logic, this is: $\forall g, \exists s, g(s) = s \implies g = id$.
• See that an implication of this is that for any two elements $s, t \in S$, we can have at most one $g$ such that $g(s) = t$. Suppose that we have two elements, $g, h$ such that $g(s) = t$ and $h(s) = t$. This means that $g^{-1}h(s) = s$. But we know that in such a case, $gh^{-1} = id$ or $g = h$.
• What does this mean? it means that $Stab(s) = \{ e \}$ for all $s$.
• Now let's upgrade this to subsets of $S$. Let $P$ (for part) be a subset of $S$. What is $|Stab(P)|$? We want to show that it is at most $P$. Let's pick a unique basepoint $p_0 \in P$ [thus $p_0 \in S$ since $P \subseteq S$].
• Let's suppose that $g \in Stab(P)$. This means that $g(p_0) \in P$. Say it sends $p_0$ to $p_g \in P$. Now no other element of $Stab(P)$ can send $p_0$ to $p_g$ since the action is free!
• Thus, there are at most $|P|$ choices for $p_0$ to be sent to, one for each element of $Stab(P)$.
• Thus, $|Stab(P)| \leq |P|$.

§ Continuing: Showing that $|Stab(S) = p^n$.

• Since the action of $G$ on $G$ is free, and since we are considering the stabilizer of some subset $S \subseteq G$, we must have that $|Stab(S) \leq |S| = p^n$. Thus, since $|S| \geq p^n$ (from the orbit argument above) and $|S| \leq p^n$ (from the stabilizer argument), we have $|Stab(S) = p^n$. Thus we are done.

• More explicitly perhaps, let us analyze $|Stab(S)|$. We know that $Stab(S) \cdot S = S$. Thus, for any $t \in S$, we know that $Stab(S) \cdot t \subseteq S$. Thus, $|Stab(s) \cdot t| \leq |S|$.

• Also notice that $|Stab(S) \cdot t$ is a coset of $Stab(S)$. Thus, $|Stab(S) \cdot t| = |Stab(S)|$.

Combining the above, we find that $|Stab(S)| \leq |S|$. So the stabilizer of size $|S| = p^k$ it is in some sense "maximal": it has the largest size a stabilizer could have!