26th Turkish Mathematical Olympiad

For any $n>1$, we can write the given equality for $n$ and $n-1$, then subtract them side by side to obtain the following: $$\sum _{i=1}^{n-1}\left(a_{\lfloor \frac{n}{i}\rfloor }-a_{\lfloor \frac{n-1}{i}\rfloor }\right)+a_1=n^{10}-(n-1{)}^{10}.$$ Defining a new sequence by $b_1=a_1=1$ and $b_n=a_n-a_{n-1}$ for each $n>1$, we can express the equality we obtained in the following form: $$\sum _{i|n}{b}_{\frac{n}{i}}=n^{10}-(n-1{)}^{10}\Rightarrow \sum _{i|n}{b}_i=n^{10}-(n-1{)}^{10}.$$ It is easy to see that this equality holds for $n=1$ as well as $n>1$. Now, recall the definition of the well-known $\mu$-function: $$\mu (n)=\{\begin{array}{ll}(-1{)}^k& n\text{ is square-free and the number of prime divisors of }n\text{ is }k\\ 0& n\text{ is not square-free}\end{array}$$ Also recall the following well-known theorem: Theorem. Let $x_1,x_2,\dots$ be a sequence and let $y_n={\sum }_{i|n}{x}_i$ for each positive integer $n$. Then, $$x_n=\sum _{i|n}\mu (i)\cdot y_{\frac{n}{i}}$$ holds for each positive integer $n$. If $n>1$, denoting the prime divisors of $n$ by $p_1,p_2,\dots ,p_k$, we can express the equality more explicitly as follows: $$x_n=y_n-y_{\frac{n}{p_1}}-\cdots -y_{\frac{n}{p_k}}+y_{\frac{n}{p_1{p}_2}}+\cdots +y_{\frac{n}{p_{k-1}{p}_k}}-\dots$$ Now, we know that $$\sum _{i|n}{b}_i=n^{10}-(n-1{)}^{10}=(10n^9-45n^8+\cdots -45n^2+10n-1).$$ Therefore, by the theorem above, we find that $$b_n=\sum _{i|n}\mu (i)\cdot \left({\left(\frac{n}{i}\right)}^{10}-{\left(\frac{n}{i}-1\right)}^{10}\right)$$ $$=10\cdot \sum _{i|n}\mu (i)\cdot {\left(\frac{n}{i}\right)}^9-45\cdot \sum _{i|n}\mu (i)\cdot {\left(\frac{n}{i}\right)}^8+\cdots +10\cdot \sum _{i|n}\mu (i)\cdot \left(\frac{n}{i}\right)-\sum _{i|n}\mu (i).$$ For $n>1$, denoting the prime divisors of $n$ by $p_1,p_2,\dots ,p_k$, we see that the following holds for each positive integer $r$: $$\begin{array}{rl}\sum _{i|n}\mu (i)\cdot {\left(\frac{n}{i}\right)}^r& =n^r\cdot \left(1-\frac{1}{p_1^r}\right)\cdots \left(1-\frac{1}{p_k^r}\right)\\ & =\varphi (n)\cdot n^{r-1}\cdot \left(1+\frac{1}{p_1}+\cdots +\frac{1}{p_1^{r-1}}\right)\cdots \left(1+\frac{1}{p_k}+\cdots +\frac{1}{p_k^{r-1}}\right).\end{array}$$ Furthermore, ${\sum }_{i|n}\mu (i)=0$ since $n>1$, therefore we obtain the following: $$\begin{array}{rl}\frac{b_n}{\varphi (n)}& =10n^8\prod \left(1+\frac{1}{p}+\cdots +\frac{1}{p^8}\right)\\ & -45n^7\prod \left(1+\frac{1}{p}+\cdots +\frac{1}{p^7}\right)+\cdots -45n\prod \left(1+\frac{1}{p}\right)+10.\end{array}$$ We draw the following two conclusions from this formula: (i) For each positive integer $n$, one has $\varphi (n)\mid b_n$. This is obvious for $n=1$ and follows from the formula for $n>1$. (ii) For each positive integer $n$, one has $b_n>0$, thus $a_n\ge n$. Because, $$b_1=1>0,b_2=2^{10}-2>0,b_3=3^{10}-2^{10}-1>0,b_4=4^{10}-3^{10}-2^{10}+1>0$$ and for $n\ge 5$, $$\begin{array}{rl}\frac{b_n}{\varphi (n)}& >n^7\cdot (10n-45)\prod \left(1+\frac{1}{p}+\cdots +\frac{1}{p^7}\right)+\dots \\ & +n\cdot (120n-45)\prod \left(1+\frac{1}{p}\right)+10>0\Rightarrow b_n>0.\end{array}$$

For $n>1$, separate the prime divisors of $n$ into two subsets as those which divide $c$ and those which do not divide $c$, hence write $n=m\cdot s$. Here, $m$ divides sufficiently large powers of $c$ and $s$ is coprime to $c$. Hence, $m\mid c^{n-1}\mid c^{a_{n-1}}$ since $a_{n-1}\ge n-1$ and $s\mid c^{\varphi (s)-1}\mid c^{\varphi (n)-1}\mid c^{b_n-1}$ since $\varphi (n)\mid b_n$. Therefore, $n\mid c^{a_{n-1}}\cdot (c^{b_n-1})=c^{a_n}-c^{a_{n-1}}$.