Prove that $k$ divides $a_k$ Define the sequence $a_k$ recursively by $\displaystyle\sum_{d|k}a_d=2^k$ with $d>0$. Prove that $a_k$ is a multiple of $k$. 
 A: I believe this is usually solved with a counting argument, but here is a number theoretic solution:
By Mobius inversion, $a_n=\sum_{d|n}\mu(d)2^{\frac{n}{d}}$. Let $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$. To show that $n|a_n$, it suffices to show that $p_m^{e_m}|a_n$ for each $m$.
Note that $$\sum_{d|n}\mu(d)2^{\frac{n}{d}}=2^n-\sum_{i}2^{\frac{n}{p_i}}+\sum_{i,j}2^{\frac{n}{p_ip_j}}-\cdots+(-1)^k2^{\frac{n}{p_1p_2\cdots p_k}}$$Set $x=2^{\frac{n}{p_1p_2\cdots p_k}}$ and $P=p_1p_2\cdots p_k$. Then the above is equal to $$(x^{p_m})^{\frac{P}{p_m}}-\bigg(x^{\frac{P}{p_m}}+\sum_{i\neq l}(x^{p_m})^{\frac{P}{p_i p_m}}\bigg)+\bigg(\sum_{i\neq m}x^{\frac{P}{p_ip_m}}+\sum_{i,j\neq m}(x^{p_m})^{\frac{P}{p_i p_jp_m}}\bigg)-\cdots +(-1)^k x,$$which can be grouped as $$\bigg((x^{p_m})^{\frac{P}{p_m}}-x^{\frac{P}{p_m}}\bigg)-\bigg(\sum_{i\neq m}(x^{p_m})^{\frac{P}{p_i p_m}}-\sum_{i\neq m}x^{\frac{P}{p_i p_m}}\bigg)+\cdots+(-1)^{k-1}\bigg((x^{p_m})-x\bigg)$$However, if $p_m$ is odd then $x^{p_m}= 2^{p_m^{e_m}N}\equiv 2^{p_m^{e_m-1}N}= x\pmod{p_m^{e_m}}$ by Euler's theorem (since $N=\dfrac{n}{P\cdot p_m^{e_m-1}}$ is an integer). If $p_m=2$ then $x\equiv0$ since $2^{e_m-1}\ge e_m$ for all $e_m\ge 1$. 
Therefore, the above is just $0\pmod{p_m^{e_m}}$, and the conclusion follows.
A: Alternatively, show that $a_k$ the degree of the product of all irreducible polynomials $f(x)\in \mathbb{F}_2[x]$ of degree $k$.  Hence, $k$ naturally divides $a_k$.  (That is, $\frac{a_k}{k}$ is the number of irreducible polynomials in $\mathbb{F}_2[x]$ of degree $k$.)
Here is yet another solution.  Using the Möbius Inversion Formula, one has ${a_k}=\sum_{d\mid k}\,\mu\left(\frac{k}{d}\right)\,2^d$.  Consider the cyclic group $C_k=\langle \gamma\rangle$ acting on $\{0,1\}^k$ via $$\gamma\cdot\left(x_1,x_2,\ldots,x_{k-1},x_k\right):=\left(x_k,x_1,\ldots,x_{k-2},x_{k-1}\right)$$ for all $\left(x_1,x_2,\ldots,x_k\right)\in\{0,1\}^k$.  Prove that the number of asymmetric elements in $\{0,1\}^k$, namely, those which are only fixed by the identity of $C_k$, is precisely $\sum_{d\mid k}\,\mu\left(\frac{k}{d}\right)\,2^d$.  It follows immediately that $\frac{a_k}{k}=\frac{1}{k}\,\sum_{d\mid k}\,\mu\left(\frac{k}{d}\right)\,2^d$ is an integer, being the number of $C_k$-orbits of asymmetric elements.
P.S.  Ooops, darij grinberg already mentioned my second solution.
A: We prove it by induction on $n$. The assertion is true for $n=1$. Suppose it is true for all numbers smaller than $n$. Let $p$ be a prime divisor of $n$ and write $n=p^k\cdot n'$ with $gcd(p,n')=1$. Then:
$$
2^n=\sum_{d\mid n}a_d=\sum_{d\mid p^{k-1}n'}a_d+\sum_{d\mid n'}a_{p^kd}=2^{p^{k-1}n'}+\sum_{d\mid n'}a_{p^kd}
$$
The hypothesis implies that $p^k$ divides every $a_{p^kd}$ except for $a_{p^kn'}=a_n$
Furthermore
$$
p^k\mid 2^n-2^{p^{k-1}n'}=2^{p^{k-1}n'}\left(2^{n'\varphi{\left(p^{k}\right)}}-1\right)
$$
by the little theorem of Fermat (and for $p=2$ directly). Thus $p^k\mid a_n$. Since this is true for every prime divisor of $n$, we obtain $n\mid a_n$.
