# Integrality of a certain quantity $\sum_{i =1}^n a_{\lfloor \frac{n}{i}\rfloor }=n^{10},$

Problem :A sequence $$a_1,a_2,\dots$$ satisfy $$\sum_{i =1}^n a_{\lfloor \frac{n}{i}\rfloor }=n^{10},$$ for every $$n\in\mathbb{N}$$. Let $$c$$ be a positive integer. Prove that, for every positive integer $$n$$, $$\frac{c^{a_n}-c^{a_{n-1}}}{n}$$ is an integer.

I try :

Note that the required proposition is true if both $$a_n\geqslant n$$ and $$\phi (n)\mid a_n-a_{n-1}$$ is true for all positive integer $$n>1$$. From the condition given, we get that $$a_1=1$$ and \begin{align*} (n+1)^{10}-n^{10}-1& =\sum_{j=1}^{n}{\left( a_{\lfloor \frac{n+1}{j}\rfloor }-a_{\lfloor \frac{n}{j}\rfloor }\right) }\\ & =\sum_{\substack{j\mid n+1 \\1\leqslant j1}}{ (a_d-a_{d-1})} . \end{align*} Following work I can't

You are in the right direction. Differencing yields $$\begin{eqnarray} n^{10} - (n-1)^{10} &=& a_1 +\sum_{1\leq i \leq n-1} (a_{\lfloor \frac{n}{i}\rfloor }-a_{\lfloor \frac{n-1}{i}\rfloor })\\ &=&a_1 + \sum_{i|n, i1} (a_{i }-a_{i-1 }) = \sum_{i|n} (a_{i }-a_{i-1 }) \end{eqnarray}$$ if we let $$a_0 = 0$$. Define $$b_n = a_n - a_{n-1}$$ and $$p(n) = n^{10} - (n-1)^{10}$$. By Mobius inversion formula, (see https://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula) we have $$b_n = \sum_{j|n} p(j)\mu(\frac{n}{j}).$$ What we show first is that $$\phi(n)$$ divides each $$b_n$$ for all $$n\geq 1.$$ To this end, we show the following claim: for each $$r\geq 0$$, $$\sum_{j|n} j^r\mu(\frac{n}{j})$$ has $$\phi(n)$$ as its factor. Proof goes like this. Let $$c_n = \sum_{j|n} j^r\mu(\frac{n}{j}).$$ Observe that $$c_1 = 1$$, hence $$\phi(1) | c_1$$. We first show $$\phi(n)|c_n$$ for $$n = p^k$$ where $$p$$ is a prime. This follows easily since $$c_{p^k} = p^{rk} - p^{r(k-1)},$$ and $$\phi(p^k) = p^k - p^{k-1}.$$ (Note that $$x-y | x^r - y^r$$.) Next we show that $$c_n$$ is multiplicative, that is, for $$p,q$$ such that $$(p,q)=1$$, it holds that $$c_{pq} = c_pc_q$$. This also follows easily from $$\begin{eqnarray} c_{pq} &=&\sum_{j|pq} j^r\mu(\frac{pq}{j}) \\ &=& \sum_{n|p, m|q} (nm)^r\mu(\frac{pq}{nm})\\ &=&\sum_{n|p, m|q} n^r\mu(\frac{p}{n})\cdot m^r\mu(\frac{q}{m})\\ &=& \sum_{n|p} n^r\mu(\frac{p}{n})\cdot \sum_{m|q}m^r\mu(\frac{q}{m})\\ &=& c_p\cdot c_q. \end{eqnarray}$$ Since $$\phi(n)$$ is also multiplicative, these two facts prove the claim.
So far we've shown that for every monomial $$j^r$$, it holds that $$\phi(n) |\sum_{j|n} j^r\mu(\frac{n}{j})$$. Thus it holds for any polynomial with integer coefficients, and especially for $$p(j)$$. This shows $$\phi(n) \:|\: b_n = \sum_{j|n} p(j)\mu(\frac{n}{j}),$$ as we wanted.
It remains to show $$a_n \geq n$$. Assume $$c\cdot j^{10} \leq a_j \leq j^{10}$$ for $$j=1,2,\ldots,n-1$$ for some $$0. Then we have $$\begin{eqnarray} a_n &=& n^{10} - \sum_{2\leq i \leq n} a_{\lfloor \frac{n}{i}\rfloor }\\ &\geq & n^{10} - n^{10}\sum_{2\leq i \leq n} \frac{1}{i^{10}} \\ &\geq & n^{10} (1-\sum_{2\leq i <\infty} \frac{1}{i^{10}}), \end{eqnarray}$$ and $$a_n \leq n^{10}$$. If we let $$c = 1-\sum_{i=2}^{\infty}\frac{1}{i^{10}}\in (0.99,1)$$, then by induction hypothesis, it holds for every $$n\in \mathbb{N}$$ once if we prove it for $$n=1$$. But this is obviously true, since $$a_1 = 1$$. Finally, we see that $$a_n \geq c\cdot n^{10} \geq (c\cdot 2^9)\cdot n >500n$$ for all $$n\geq 2$$, establishing $$a_n \geq n$$.
Denote $$b_n=a_n-a_{n-1}$$ and $$f(n)=n^{10}-(n-1)^{10}$$.
For any prime number $$p$$, we have $$b_p=a_{p}-a_{p-1}=p^{10}-(p-1)^{10}-1=f(p)-1$$ Notice that for any $$n=p^m$$ where $$m$$ is a positive integer : $$b_{p^m}=f(p^m)-1-\sum_{k=1}^{m-1}{b_{p^k}}$$ then by mathematical induction, we can get that $$b_{p^m}=f(p^m)-f(p^{m-1})=(p^m)^{10}-(p^m-1)^{10}-(p^{m-1})^{10}+(p^{m-1}-1)^{10}$$ For two different prime number $$p,q$$, we have $$b_{pq}+b_p+b_q=f(pq)-1$$ which implies that $$b_{pq}=f(pq)-f(p)-f(q)+1$$ then by mathematical induction, we can get that $$b_{p_1p_2\cdots p_k}=\sum^{k}_{i=1}(-1)^{k-i}\sum_{1\leq k_1