A different proof by Mobius inversion formula: Let $p$ a prime such that $p^k\| n$ then I prove $p^k\mid a_n$, the problem follows easily. $\displaystyle a_n=\sum_{d\mid n}\mu(d)2^{\frac{n}{d}}=\sum_{i=0}^k\left(\sum_{d\mid n\wedge \upsilon_p(d)=i}\mu(d)2^{\frac nd}\right)=\sum_{i=0}^k\left(\sum_{d\mid\frac{n}{p^k}}\mu(d\cdot p^i)2^{\frac n{p^id}}\right)=$ $\sum_{d\mid \frac{n}{p^k}}\mu(d)2^{\frac nd}+\sum_{d\mid \frac{n}{p^k}}\mu(pd)2^{\frac n{pd}}=\sum_{d\mid \frac{n}{p^k}}\mu(d)\left(2^{p^k}\right)^{\frac n{p^kd}}-\sum_{d\mid \frac{n}{p^k}}\mu(d)\left(2^{p^{k-1}}\right)^{\frac n{p^kd}}\equiv $ $\displaystyle \equiv \sum_{d\mid \frac{n}{p^k}}\mu(d)\left(2^{p^{k-1}}\right)^{\frac n{p^kd}}-\sum_{d\mid \frac{n}{p^k}}\mu(d)\left(2^{p^{k-1}}\right)^{\frac n{p^kd}}\equiv 0\pmod{p^k}$

Notice that $a_{p^k}=2^{p^k}-2^{p^{k-1}}=2^{p^{k-1}}(2^{p^{k-1}(p-1)}-1)$ which is divisible by $p^{k}$ for $k \ge 0$ by Euler. Then show $a_{mk}=a_ma_k$ for $m,k$ rel. prime by expanding the sum of $a_d$ over all divisors $d$ of $mk$. Thus $n|a_n$ for all $n$.

I don't think $a_{mk}=a_ma_k$ is necessarily true? Anyways here is a sol by me and vincenthuang75025. By Mobius inversion, we have that $a_n=\sum_{d\mid n} \mu (d)\cdot 2^{n/d}$. Let $n=\prod p_i^{e_i}$ have $k$ prime divisors, $n'=\dfrac{n}{\prod_{p\mid n} p}$. Finally, define $X=2^{n'}$. Then $\displaystyle a_n=\sum_{S} (-1)^{k-|S|}X^{\prod_{p\in S} p}$ where $S$ is a subset of $\{p_1,...,p_k\}$. Then note that $X^{ap_i}\equiv X^a\pmod{p_i^{e_i}}$ (note this follows since $X=2^b$ where $p_i^{e_i-1}\mid b$). On the other hand, $a_n=\sum_{S} (-1)^{k-|S|}\left(X^{\prod_{p\in S} p}-X^{p_i\cdot \prod_{p\in S} p}\right)$ where $S$ is a subset of $\{p_1,...,p_k\} \slash \{ p_i \}$. Then we see that $p_i^{e_i}$ divides $a_n$. Considering this for all primes that divide $n$, we are done.

lol Note that $a_n$ is the number of elements of $\mathbb{F}_{2^n}$ that are not elements of $\mathbb{F}_{2^m}$ for any $m<n$. Now, group those elements by minimal polynomial and note that all of those polynomials have degree $n$, so we are immediately done.

First we have $a_{p^k} = 2^{p^k} - 2^{p^{k-1}} \equiv 0 \pmod{p^k}.$ Now assume that $p^k|a_{sp^k}$ for all $1 \le s \le m-1$. Now note that $$a_{mp^k} = 2^{mp^k} - \sum_{d|mp^k, d \neq mp^k} a_d = 2^{mp^k} - \sum_{d|mp^{k-1}} a_d - \sum_{d|m, d \neq m} a_{p^k \cdot d}. $$The hypothesis gives $$p^k|\sum_{d|m, d \neq m} a_{p^k \cdot d}$$and because of the condition $$\sum_{d|mp^{k-1}} a_d = 2^{mp^{k-1}}.$$Therefore we have $a_{mp^k} \equiv 2^{mp^k} - 2^{mp^{k-1}} \equiv 0 \pmod{p^k}$. Thus by induction we proved that $p^k|n$ implies $p^k|a_n$ which finishes the problem.

By Möbius inversion, $a_n=\sum_{d\mid n}^{} \mu(\frac{n}{d})2^d$. It is not hard to show that $a$ is multiplicative. From here, it suffices to consider $n=p^e$ for some prime $p$ and non negative $e$. Observe that $$\sum_{d\mid n}^{} \mu(\frac{p^e}{d})2^{d} = 2^{p^e}-2^{p^{e-1}}\equiv2^{p^{e-1}}-2^{p^{e-1}}\equiv 0 \mod p^e$$and the conclusion follows. $\square$

A detailed proof with a detailed motivation can be found on https://journeyinmath.wordpress.com/2017/07/25/i-learned-how-to-do-addition/.

orl wrote: Define sequence $ (a_n)$ by $ \sum_{d|n} a_d = 2^n.$ Show that $ n|a_n.$ How does one prove multiplicity here? Could someone please spell it out. Thanks!

bora_olmez wrote: orl wrote: Define sequence $ (a_n)$ by $ \sum_{d|n} a_d = 2^n.$ Show that $ n|a_n.$ How does one prove multiplicity here? Could someone please spell it out. Thanks! Sorry for double posting but I have another question. Could someone possibly write the first couple (maybe 10) terms of the sequence because I don't actually think that the sequence I have is multiplicative. e.g, $a_2 = 2$, $a_3 = 6$ but $a_6 = 54$ therefore $a_6 = a_2 \cdot a_3$ does not hold, yet $gcd(2,3)=1$ obviously.

@#12,#13: You are completely right, the sequence is not at all multiplicative. Basically (by Möbius inversion) this would be equivalent to $2^n$ being multiplicative which is of course wrong). So the solutions in #4, #10, #11 are not correct!

The Mobius inversion formula gives us \[ a_n = \sum_{d|n}2^{n/d} \mu(d). \]Let $n = p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k}$. Then, since the Mobius function equals $0$ whenever an exponent is greater than $1$, we can let $d = p_1^{b_1}p_2^{b_2}\ldots p_k^{b_k}$ where $\mathbf{b} = (b_1,b_2, \ldots, b_k) \in \{0,1\}^k$ and rewrite the sum as \[ a_n = \sum_{\mathbf{b} \in \{0,1\}^k} 2^{\prod_i p_i^{\alpha _i - b_i}} \mu\left( \prod_i p_i^{b_i} \right). \] We want to show that for all $j$, $p_j^{\alpha _j} \mid a_n$. First, if $p_j = 2$, then notice that the minimum exponent of the $2$ among the terms of the sum is $\prod_i p_i^{\alpha_i - 1}$, and since \[ \prod_i p_i^{\alpha_i - 1} \geq 2^{\nu_2(n) - 1} \geq \nu_2(n), \]we have $2^{\nu_2(n)} \mid a_n$. Next, if $p_j$ is an odd prime, then we claim that the terms of the sum can be paired up to cancel each other mod $p_j^{\alpha_j}$. More specifically, let \[ f(\mathbf{b}) = 2^{\prod_i p_i^{\alpha _i - b_i}} \mu\left( \prod_i p_i^{b_i} \right), \]i.e., it is the term of the sum "generated" by $\mathbf{b}$. Then, we claim that if $\mathbf{b} = (b_1, \ldots, b_k)$ and $\mathbf{b'} = (b'_1, \ldots, b'_k)$ are vectors such that for all $i \neq j$, $b_i = b'_i$ and $b_j = 0$ and $b'_j = 1$, then \[ f(\mathbf{b}) + f(\mathbf{b'}) \equiv 0 \pmod{p_j^{\alpha_j}}. \]To show this, let \[ M = p_1^{\alpha_1 - b_1}\ldots p_{j-1}^{\alpha_{j-1}-b_{j-1}}p_{j+1}^{\alpha_{j+1}-b_{j+1}}\ldots p_k^{\alpha_k - b_k} = \prod_{i \neq j} p_i^{\alpha _i - b_i}. \]Due to the definition of the Mobius function, the terms $f(\mathbf{b})$ and $f(\mathbf{b'})$ have opposite signs, and it suffices to prove \[ 2^{p_j^{\alpha_j}M} \equiv 2^{p_j^{\alpha_j - 1}M} \pmod{p_j^{\alpha_j}}. \]However, this is true by Euler's theorem: just note $2^{p_j^{\alpha_j} - p_j^{\alpha_j - 1}} \equiv 1 \pmod{p_j^{\alpha_j}}$. Thus, the entire sum is $0$ mod $p_j^{\alpha_j}$ and this concludes the proof.