If $a$ is the arithmetic function with $\sum_{d\mid n}a(d)=2^n$, then $n\mid a(n)$

Question

Problem:
Let $a:\mathbb N \rightarrow \mathbb C $ a function with the property: $$\displaystyle{\sum_{d\mid n}a(d)=2^n, \forall n \in \mathbb N}.$$ Prove that $n\mid a(n), \forall n \in \mathbb N.$

My thought:

I used Möbius inversion formula to find that: $$\displaystyle{a(n)=\sum_{d\mid n}μ(n/d)2^d},\forall n \in \mathbb N.$$ From this formula we get information for the binary representation of $a(n)$. Then I thought to consider the binary representation of $n$, see if there is any connection between the binary representations of $a(n)$ and $n$ and if this connection can imply the desired relation of divisibility. I don't know if this idea can give me anything and how to proceed with it.

Any hints and ideas are highly appreciated.

Thanks in advance.

Answer 1

I find if slightly more conofrable to use $a(n)=\sum\limits_{d|n}\mu(d)2^{n/d}$

Let $n$ be an integer and let $p^k$ be the maximum power of $p$ dividing $n$.

We have to prove $p^k$ divides $a(n)$.

To do this we use the inversion formula. Notice that $d$ can be viewed as subset of the prime divisors of $n$.

Notice that if $p\nmid d$ then $2^{n/d}\equiv 2^{n/dp}\bmod p^k$ because $n/d$ and $n/dp$ are both multiples of $p^{k-1}$ and they are congruent $\bmod p-1$ ( because $p$ is congruent to $1\bmod p-1$). It follows that $n/d$ and $n/dp$ are congruent $\bmod \varphi(p^k)$.

However, notice that $\mu(d)$ and $\mu(dp)$ have opposite signs, so we have shown that the whole sum cancels out $\bmod p^k$.

Answer 2

Combinatorial proof.
Let $b(n)$ be the number of non-periodic binary sequences of length $n$. It is easily verified that $b(n)$ satisfies the same relation as $a(n)$: each of the $2^n$ binary sequences of length $n$ has a minimal period $d$ dividing $n$, and there are precisely $b(d)$ sequences with period $d$.

Thus from $a*1=b*1$ we have $$a(n)=b(n)$$ and because each non-periodic sequence of length $n$ comes with $n$ distinct cyclic permutations, $$n\mid b(n).$$

Remarks. 1. The same proof works with $2$ replaced by any positive integer; nowhere did we use any particular property of $2$.
2. This provides a proof of Fermat's little theorem, because $a(p)=2^p-2$ (with $2$ replaced by anything you want).