10
$\begingroup$

Burnside's Lemma Deduce That:

$$\sum_{i=1}^{n} a^{\gcd(i,n)} $$

is divisible by $n$

it's a beautiful result. but i want to prove it without any abstract algebraic tools such as Burnside's Lemma...

is there any simple Number-Theoretic proof for it?

$\endgroup$
2
  • 1
    $\begingroup$ Your statement is incomplete: you forgot to specify that $a$ is an integer. Since the residue of the sum mod $n$ only depends on $a \bmod n$, it suffices to take $0 \leq a \leq n-1$ (e.g., no need to focus on $a < 0$, so you could look for a combinatorial interpretation of the sum). $\endgroup$
    – KConrad
    Jul 23, 2016 at 10:58
  • $\begingroup$ Your Burnside Lemma proof may be rephrased elementary (Burnside lemma is nothing but double counting after all, right?). This sum equals the number pairs $(\pi,i)$, where $\pi$ is $n$-periodic infinite word over an alphabet with $a$ letters, and $1\leqslant i\leqslant n$ is also a period of $\pi$. But each word with minimal period $d$, being considered together with all its shifts, corresponds exactly to $n$ such pairs. $\endgroup$ Jul 23, 2016 at 15:46

2 Answers 2

10
$\begingroup$

Our sum equals $$S_n(a):=\sum_{d|n} \varphi\left(\frac{n}d\right)a^d.$$ Fix a prime power $p^k$ which divides $n$ (but $p^{k+1}$ does not divide $n$, we write this as $\nu_p(n)=k$), we have to prove that $p^k$ divides $S_n(a)$. If $p$ divides $a$, then $p^k$ divides each summand. Indeed, $\nu_p(\varphi(n/d))\geqslant \nu_p(n/d)-1=\nu_p(n)-\nu_p(d)-1\geqslant \nu_p(n)-d$ since $d<p^d$), thus $\nu_p(\varphi(n/d)a^d)\geqslant \nu_p(n)$ as desired.

Now consider the remaining case: $p$ does not divide $a$. Fix a divisor $s$ of $n$ such that $p$ does not divide $s$ and consider the set of divisors $\{s,ps,p^2s,\dots,p^ks\}$. I claim that $p^k$ divides the sum of $\varphi\left(\frac{n}d\right)a^d$ over $d$ in each such a group. The claim follows. For proving this denote $\varphi(n/p^ks)=A$, then we have $\varphi(n/p^{k-i}s)=p^{i-1}(p-1)A$ for $i=1,\dots,k$. So, it suffices to prove that (if we denote $b=a^s$) $p^k$ divides $$ b^{p^k}+(p-1)(b^{p^{k-1}}+pb^{p^{k-2}}+\dots+p^{k-1}b)=p^kb+\sum_{i=0}^{k-1} p^i\left(b^{p^{k-i}}-b^{p^{k-i-1}}\right), $$ $p^k$ divides each summand by Euler theorem: $b^{p^m}-b^{p^{m-1}}=b^{p^{m-1}}(b^{\varphi(p^m)}-1)$ is divisible by $p^m$

$\endgroup$
1
  • $\begingroup$ Just Brilliant... any Other Proof? $\endgroup$
    – MR_BD
    Jul 23, 2016 at 15:03
8
$\begingroup$

Here is the "general theory" of such congruences.

Consider a sequence $\{a_n \}_{n\ge 1}$ of integers. We'll say it satisfies the necklace congruences if $$\forall n \in \mathbb{N}: \sum_{d \mid n}a_d \mu(\frac{n}{d}) \equiv 0 \bmod n,$$ where $\mu$ is the Mobius function. Here is an equivalent formulation:

  • Formulation 2: $a_{p^{k+1} m} \equiv a_{p^k m} \mod {p^{k+1}}$ for all $p,m,k$ ($p$ prime)

The proof of the equivalence between these two formulation involves a simple coupling argument, see the first two paragraphes of this post for instance.

A less obvious formulation is the following, which I will prove at the end of this answer:

  • Formulation 3: $\forall n \in \mathbb{N}: \sum_{d \mid n}a_d f(\frac{n}{d}) \equiv 0 \bmod n$, where $f$ is any function $\in \mathbb{N}^{\mathbb{N}}$ satisfying $\sum_{d \mid n} f(d) \equiv 0 \bmod n$ and $f(1)= 1$. Examples include $\phi(n)$ and $\mu(n)$.

There's also the following formulation, appearing as Exercise 5.2 in "Enumerative Combinatorics, vol. 2":

  • Formulation 4: $\exp(\sum_{n\ge 1} \frac{a_n}{n}x^n)$ has integer coefficients.

The congruence you want to prove is the same as saying $$\forall n \in \mathbb{N}: \sum_{d \mid n} a_d \phi(\frac{n}{d}) \equiv 0 \bmod n$$ where $$a_n := a^n.$$ From Formulation 3 with $f(n) := \phi(n)$, your congruence is equivalent to showing that $a_n := a^n$ is a sequence which satisfies the necklace congruences. The fact that it is indeed such a sequence is immediate from Formulation 2 (for which you need Euler's Theorem) or Formulation 4 (for which you need to know the Taylor series of $-\log(1-x)$).


Proof of Formulation 3:

(I assume familiarity with Dirichlet convolution, denoted "*" below)

Assume that $\{ a_n \}_{n\ge 1}$ satisfies the necklace congruences. Let $f\in \mathbb{N}^{\mathbb{N}}$ be a function satisfying $f(1)=1$ and $\forall n\in \mathbb{N}: \sum_{d \mid n} f(d) \equiv 0 \bmod n$. We know that $n \mid \sum_{d \mid n} \mu(\frac{n}{d})a_d$. Now just write $f ∗ a_n$ as $(\mu∗ a_n) ∗ (1 ∗ f)$ and use the properties of $f$ and $a_n$ to conclude that $n \mid \sum_{d \mid n} a_d f(\frac{n}{d})$.

For the other direction, assume that $\forall n \in \mathbb{N}: n \mid (f * a_n)(n)$. By direct induction, if $n \mid (f ∗ 1)(n)$ then $n \mid (f ^{−1} ∗\mu)(n)$. Now write $\mu ∗ a_n$ as $(f ∗ a_n) ∗ (f ^{−1} ∗ \mu)$ and use the properties of $f$ and $a_n$ to conclude that $n \mid \sum_{d \mid n} a_d \mu(\frac{n}{d})$.

$\endgroup$
3
  • $\begingroup$ I also call these the necklace congruences, but because they seemed like the most reasonable name. Do you know a source where they're called that? $\endgroup$ Jul 23, 2016 at 19:13
  • 1
    $\begingroup$ @QiaochuYuan To be honest, I learnt that name from your blog posts :) $\endgroup$ Jul 23, 2016 at 21:49
  • $\begingroup$ @QiaochuYuan, the use of "necklace" for this circle of ideas goes back at least to a paper of Metropolis and Rota on necklace polynomials. See the references on the Wikipedia page en.wikipedia.org/wiki/Necklace_polynomial. $\endgroup$
    – KConrad
    Jul 25, 2016 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.