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{cases} (-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{cases}$$
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}} - \dots - y_{\frac{n}{p_k}} + y_{\frac{n}{p_1 p_2}} + \dots + 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 + \dots - 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 + \dots + 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{aligned} \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) \\ &= \phi(n) \cdot n^{r-1} \cdot \left(1 + \frac{1}{p_1} + \dots + \frac{1}{p_1^{r-1}}\right) \cdots \left(1 + \frac{1}{p_k} + \dots + \frac{1}{p_k^{r-1}}\right). \end{aligned}$$
Furthermore, $\sum_{i|n} \mu(i) = 0$ since $n > 1$, therefore we obtain the following:
$$\begin{aligned} \frac{b_n}{\phi(n)} &= 10n^8 \prod \left(1 + \frac{1}{p} + \dots + \frac{1}{p^8}\right) \\ &\quad -45n^7 \prod \left(1 + \frac{1}{p} + \dots + \frac{1}{p^7}\right) + \dots -45n \prod \left(1 + \frac{1}{p}\right) + 10. \end{aligned}$$
We draw the following two conclusions from this formula:
(i) For each positive integer $n$, one has $\phi(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{aligned} \frac{b_n}{\phi(n)} &> n^7 \cdot (10n - 45) \prod \left(1 + \frac{1}{p} + \dots + \frac{1}{p^7}\right) + \dots \\ &\quad + n \cdot (120n - 45) \prod \left(1 + \frac{1}{p}\right) + 10 > 0 \Rightarrow b_n > 0. \end{aligned}$$

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^{\phi(s)-1} \mid c^{\phi(n)-1} \mid c^{b_n-1}$ since $\phi(n) \mid b_n$. Therefore, $n \mid c^{a_{n-1}} \cdot (c^{b_n-1}) = c^{a_n} - c^{a_{n-1}}$.