# Lucas' theorem prime power case

## Statement

### Symbolic statement

Let $n = p^rm$ where $p$ is a prime and $m$ is relatively prime to $p$. Then: $\binom{n}{p^r} \equiv m \mod p$

## Proof

### Proof using group theory

Recall that a proof of Sylow's theorem invokes Lucas' theorem at the following critical juncture: we consider the size of the set of subsets of size $p^r$, on which the group of order $n$ is acting, and then infer that there exists an orbit of size $m$, whose isotropy subgroup is hence a Sylow subgroup.

In the proof of Lucas' theorem, we employ the same tactic in reverse, but instead of taking any arbitrary group, we start off with the cyclic group of order $n$. Formally, here's the proof.

Consider the cyclic group $C_n$ of order $n$. We need to show that the number of subsets of size $p^r$ in $C_n$ is $m$ modulo $p$. To prove this, we claim that under the action of left multiplication by $C_n$, there is exactly one orbit whose size is relatively prime to $p$, and the size of this orbit is $m$.

Consider an orbit whose size is relatively prime to $p$. Then, the size of this orbit must be a divisor of $m$. Further, since the union of members of any orbit is the whole of $C_n$, the number of members in the orbit must be at least $n/p^r = m$, equality occurring off they are pairwise disjoint.

Combing the two facts, the and hence all the members of the orbit are disjoint. We thus have a situation where there is a subset of size $p^r$ in $C_n$ such that all its left translates are pairwise disjoint. Basic group theory tells us that this subset must be a left coset of a subgroup of size $p^r$, and moreover, the subgroups are in bijective correspondence with such orbits.

We now use the fact that $C_n$ has a unique subgroup of order $m$, and we are done.