# 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.