A divisibility identity for Euler’s totient function

In this note I will give a Galois-theoretic proof that for a prime {p} and positive integer {n},

\displaystyle n \mid \frac{\varphi(p^n-1)}{\varphi(p-1)}.

I’d love to see a more elementary proof if you can come up with one.
First we need the following:

Lemma 1 Let {Z_n} be the cyclic group with {n} elements. Let {m} be a positive divisor of {n}, and consider {Z_m} as a subgroup of {Z_n}. Then the number of automorphisms of {Z_n} which fix {Z_m} pointwise is equal to {\varphi(n)/\varphi(m)} (which, in particular, is an integer).

Proof of the Lemma: Note that any automorphism of {Z_n} fixes {Z_m}, though not necessarily pointwise: indeed {Z_n} has a unique subgroup of order {m}, and thus any automorphism of {Z_n} must take this subgroup to itself. Thus we have a group homomorphism {\text{Aut}(Z_n) \rightarrow \text{Aut}(Z_m)} which is easily seen to be surjective; its kernel is precisely the subgroup consisting of those automorphisms of {Z_n} which fix {Z_m} pointwise. The statement follows by comparing orders. {\square}

Now to prove the initial claim, consider the field extension {\mathbf{F}_{p^n}/\mathbf{F}_p}. Basic Galois theory tells that this is a Galois extension of degree {n}. Consider the canonical homomorphism

\psi: \displaystyle \text{Gal}(\mathbf{F}_{p^n}/\mathbf{F}_p) \rightarrow \text{Aut}(\mathbf{F}_{p^n}^\times)

which restricts an {\mathbf{F}_p}-automorphism {\sigma} to the group of units of {\mathbf{F}_{p^n}}. Clearly it is an injective homomorphism since {\sigma} is completely determined by where it sends the units. Moreover for any {\sigma \in \text{Gal}(\mathbf{F}_{p^n}/\mathbf{F}_p)}, \psi(\sigma) lies in the subgroup of {\mathbf{F}_{p^n}^\times} of those automorphisms fixing pointwise the cyclic subgroup {\mathbf{F}_{p}^\times} of order {p-1}, because the Galois group consists of \mathbf{F}_p-homomorphisms. By the lemma the subgroup of these automorphisms has order {\frac{\varphi(p^n-1)}{\varphi(p-1)}}, whereas {\text{Gal}(\mathbf{F}_{p^n}/\mathbf{F}_p)} has order {n}. This does it.

Burnside’s lemma and Bell numbers

In this post I am going to show that {B_n}, the {n}th Bell number, is larger than {n^n/n!}.

Our main tool will be Burnside’s lemma, which states that if a finite group {G} acts on a finite set {S}, the average number of fixed points of the elements of {G} is equal to the number of orbits of the action of {G} on {S}:

\displaystyle |G\backslash S|=\frac{1}{|G|}\sum_{g \in G}|\text{Fix }g|,

where {\text{Fix }g} is the set of fixed points of {g}.

We let {S_n}, the symmetric group on {n} letters, act on {\{1,2,\dots,n\}^n} component-wise. The elements of {[n]=\{1,2,\dots,n\}^n} are {n}-tuples consisting of integers between {1} and {n}. Now you may easily convince yourself that it is possible to send a tuple {(a_1, \dots, a_n)} to a tuple {(b_1, \dots, b_n)} if and only if whenever {a_i=a_j}, we also have {b_i=b_j}, and vice versa. In other words we view each {n}-tuple {(a_1, \dots, a_n)} as a function {\sigma: [n] \rightarrow [n]}; its fibres partition {[n]}, and composition with a permutation preserves the fibres of {\sigma}. It is immediate that {\sigma} and {\sigma'} are in the same orbit of {S_n} if and only if they have the same collection of fibres. For instance, (1,1,2) can be sent to (3,3,1) by the cycle (1\: 3\: 2) but there is no way to send (1,1,2) to (1,2,3), because any permutation will send (1,1,2) to a 3-tuple of the form (\bullet,\bullet,\circ).

Thus {S_n} has {B_n} orbits on {\{1,2,\dots,n\}^n}. On the other hand since our permutations act component-wise, we have

\displaystyle \text{Fix }_{[n]^n}g \cong (\text{Fix }_{[n]}g)^n,

i.e. the fixed points of {g} acting on {[n]^n} are the tuples {(a_1, \dots, a_n)} consisting of fixed points of {g} acting on {[n]}. Therefore, by Burnside’s lemma, we have

\displaystyle \frac{1}{n!}\sum_{g\in S_n} (\text{Fix }g)^n = B_n.

In fact the same argument shows that for any m\geq n, we have

\displaystyle \frac{1}{m!}\sum_{g\in S_m} (\text{Fix }g)^n = B_n.

In particular, the identity of {S_n} fixes all of {[n]}, so we have

\displaystyle \frac{n^n}{n!} \leq B_n.

In fact, by using the fact that a permutation of {[n]} consists of a subset of {[n]} (the subset of fixed points), and a derangement of the remaining elements, we easily obtain the formula

\displaystyle B_n = \frac{1}{n!}\sum_{i=0}^n {n \choose i} !(n-i) i^n

where {!n} is the number of derangements of a set of {n} elements.