Lucas' theorem prime power case

From Groupprops
Jump to: navigation, search

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.