# Lucas' theorem prime power case

## Statement

### Symbolic statement

Let UNIQ1d439d97686e7669-math-00000000-QINU where UNIQ1d439d97686e7669-math-00000001-QINU is a prime and UNIQ1d439d97686e7669-math-00000002-QINU is relatively prime to UNIQ1d439d97686e7669-math-00000003-QINU. Then: UNIQ1d439d97686e7669-math-00000004-QINU

## 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 UNIQ1d439d97686e7669-math-00000005-QINU, on which the group of order UNIQ1d439d97686e7669-math-00000006-QINU is acting, and then infer that there exists an orbit of size UNIQ1d439d97686e7669-math-00000007-QINU, 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 UNIQ1d439d97686e7669-math-00000008-QINU. Formally, here's the proof.

Consider the cyclic group UNIQ1d439d97686e7669-math-00000009-QINU of order UNIQ1d439d97686e7669-math-0000000A-QINU. We need to show that the number of subsets of size UNIQ1d439d97686e7669-math-0000000B-QINU in UNIQ1d439d97686e7669-math-0000000C-QINU is UNIQ1d439d97686e7669-math-0000000D-QINU modulo UNIQ1d439d97686e7669-math-0000000E-QINU. To prove this, we claim that under the action of left multiplication by UNIQ1d439d97686e7669-math-0000000F-QINU, there is exactly one orbit whose size is relatively prime to UNIQ1d439d97686e7669-math-00000010-QINU, and the size of this orbit is UNIQ1d439d97686e7669-math-00000011-QINU.

Consider an orbit whose size is relatively prime to UNIQ1d439d97686e7669-math-00000012-QINU. Then, the size of this orbit must be a divisor of UNIQ1d439d97686e7669-math-00000013-QINU. Further, since the union of members of any orbit is the whole of UNIQ1d439d97686e7669-math-00000014-QINU, the number of members in the orbit must be at least UNIQ1d439d97686e7669-math-00000015-QINU, 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 UNIQ1d439d97686e7669-math-00000016-QINU in UNIQ1d439d97686e7669-math-00000017-QINU 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 UNIQ1d439d97686e7669-math-00000018-QINU, and moreover, the subgroups are in bijective correspondence with such orbits.

We now use the fact that UNIQ1d439d97686e7669-math-00000019-QINU has a unique subgroup of order UNIQ1d439d97686e7669-math-0000001A-QINU, and we are done.