I assume the required proposition is only for $n>1$ because $a_0$ is undefined.

Any elementary solution?

Ok does anyone has the official solution (Even in Turkish) or a link to it?

I only have the problems, not the solutions. Nor do I think that solutions exist anywhere, other than those posted on AoPS.

ThE-dArK-lOrD wrote: I assume the required proposition is only for $n>1$ because $a_0$ is undefined.

My, my, we need nothing so frightfully complicated to show that $a_n \geq n$. Simple induction will do. By induction we will show that $n < a_n < n^{10}$ for all $n > 1$. The base case $n=2$ is clear from $a_2 = 2^{10} - 1$. Since each term in the sum is positive, it is obvious that $a_n < n^{10}$. It remains to show that it is at least $n$. Using the inductive hypothesis, \[ n^{10} < a_n + \sum_{k=2}^n \left\lfloor{\frac{n}{k}}\right\rfloor^{10} < a_n + n^{10} (\zeta(10) - 1). \]However, $\zeta(10) -1$ is very small. Just rudimentary estimates give \[ \zeta(10) -1 < \int_2^{\infty} t^{-10} dt = 2^{-9} < 1/100. \]Thus $a_n > 0.99 n^{10}$, which is certainly at least $n$ for all $n > 2$.

Nice solution

Here is the complete solution. For $n>1$, write $n$ and $n-1$ at the given equation and substracting them gives $$\sum_{i=1}^{n-1} (a_{\left\lfloor \frac{n}{i} \right \rfloor}-a_{\left\lfloor \frac{n-1}{i} \right\rfloor})+a_1=n^{10}-(n-1)^{10}$$ Let $b_1=a_1=1$ and for $n>1$ we define $b_n$ as $a_n-a_{n-1}$. Thus $$\sum_{i|n} b_{\frac{n}{i}} =n^{10}-(n-1)^{10} \Rightarrow \sum_{i|n} b_i = n^{10}-(n-1)^{10}$$ Let $\mu$ be the well known function as described above. We will remind a well-known theorem now: Theorem Let $x_1, x_2, ...$ be a sequence and for every positive integer $n$ we define the sequence $\{y_n \}$ as $y_n= \sum_{i|n} x_i$ Therefore we have $x_n= \sum_{i|n} \mu(i) \cdot y_{\frac{n}{i}}$ For $n>1$, if the prime divisors of $n$ are $p_1, p_2, ..., p_k$ we have $$x_n=y_n-y_{\frac{n}{p_1}}-...-y_{\frac{n}{p_k}}+y_{\frac{n}{p_1 \cdot p_1}}+...+y_{\frac{n}{p_{k-1} \cdot p_k}}-...$$ We know $\sum_{i|n} b_i=n^{10}-(n-1)^{10} =(10n^9-45n^8+...-45n^2+10n-1)$ and by using theorem we have $$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+...+10 \cdot \sum_{i|n} \mu(i) \cdot \left( \frac{n}{i} \right) - \sum_{i|n} \mu(i)$$Also for $n>1$ if we show the prime divisors of $n$ with $p_1, p_2, ..., p_k$, for every positive integer $r$ $$\sum_{i|n} \mu(i) \cdot \left( \frac{n}{i} \right)^r = n^r \cdot \left(1- \frac{1}{p_1^{r}} \right)... \left(1- \frac{1}{p_k^{r}} \right) = \phi (n) \cdot n^{r-1} \cdot \left(1+ \frac{1}{p_1} +...+ \frac{1}{p_1^{r-1}} \right) ... \left(1+ \frac{1}{p_k} +...+ \frac{1}{p_k^{r-1}} \right)$$We also have $\sum_{i|n} \mu(i)=0$ for $n>1$, hence $$b_n= \phi(n) \cdot \left(10n^8 \prod \left(1+ \frac{1}{p} +...+ \frac{1}{p^8} \right) - 45n^7 \prod \left(1+ \frac{1}{p} +...+ \frac{1}{p^7} \right) +...-45n \prod \left(1+ \frac{1}{p} \right)+10 \right)$$From this formula, we reach two conclusions: i) For every positive integer $n$ we have $\phi(n) |b_n$ ii) For every positive integer $n$ we also see that $b_n >0$ since $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$ $$\frac{b_n}{\phi(n)} > n^7 \cdot (10n-45) \prod \left(1+ \frac{1}{p}+...+\frac{1}{p^7} \right)+...+n \cdot (120n-45) \prod \left(1+\frac{1}{p} \right) +10 > 0 \Rightarrow b_n >0$$ Let's write $n= m \cdot s $ where $s$ and $c$ are coprime and $m$ divides the some large powers of $c$. Because of $a_{n-1} \ge n-1$ and $\phi(n) | b_n$, $m|c^{n-1}|c^{a_{n-1}}$ and $s|c^{\phi(s)}-1|c^{\phi(n)}-1|c^{b_n}-1$. Consequently, $n|c^{a_{n-1}} \cdot (c^{b_n}-1) = c^{a_n}-c^{a_{n-1}}$ P.S I think this was one of the hardest questions of last years, so I wonder who did manage to solve this during exam. Also this was proposed by Melih Üçer, former IMO medalist.

matinyousefi wrote: Any elementary solution? Here is very clear elementary solution that uses properties of multiplicative functions. https://math.stackexchange.com/questions/3030583/integrality-of-a-certain-quantity-sum-i-1n-a-lfloor-fracni-rfloor?rq=1

Interesting

Let $f(x) = x^{10} - (x-10)^{10}$ and $\Delta_{n} = a_n - a_{n-1}$. Using Möbius's Inversion, we have that $\sum_{d \mid n} \mu (d)\cdot f(\frac{n}{d}) = \Delta_{n}$. Notice that the problem's condition is equivalent to proving $ n \mid c^{\Delta_{n}} -1$, which is equivalent to (letting $n = \prod_{i=1}^{k} p_i^{\alpha_{i}})$ $\Delta_{n} \equiv 0 \pmod{p^{\alpha_{i} -1}_i \cdot (p_i-1)}$, which is equivalent to the following $2$ lemmas: Lemma $1$: $\Delta_{n} \equiv 0 \pmod{p^{\alpha_{i} -1}_i}$ Proof: Notice that if $\mu (d) \neq 0$ we have $p^{\alpha_{i} -1}i \mid \frac{n}{d}$. Hence, $(\frac{n}{d})^{10} - (\frac{n}{d} -1)^{10} \equiv 1 \pmod{p^{\alpha{i} -1}i}$. Now notice that in $\sum{d \mid n} \mu (d).f(\frac{n}{d})$ we have $\binom{k}{0} + \binom{k}{2} + \cdot\cdot\cdot $ terms in this sum with a positive signal and $\binom{k}{1} + \binom{k}{3} + \cdot\cdot\cdot$ terms in this sum with a negative signal. Since these quantities are equal, the sum we're looking for is really $\equiv 0 \pmod{p_i^{\alpha_{i} -1}}$ $\blacksquare$. Lemma $2$:$\Delta_{n} \equiv 0 \pmod{{\text{lcm}}(p_1 -1, p_2 -1, ... p_k -1)}$. Proof: Notice that suffices to prove $\Delta_{n} \equiv 0 \pmod{p_i -1}$ and we have $\sum_{d \mid n} \mu (d) \cdot f(\frac{n}{d}) = \sum_{d \mid \frac{n}{p^{\alpha_{i}}}} \mu (d) \cdot f(\frac{n}{d}) + \sum_{\substack{d' = d \cdot p_i \\ d \mid \frac{n}{p^{\alpha_{i}}}}} \mu (d') \cdot f(\frac{n}{d'})$. By definition, $f(\frac{n}{d'}) = f(\frac{n}{d \cdot p_i})$ and we also have $p_i \equiv 1 \pmod{p_i -1}$ which implies $\frac{n}{d'} \equiv \frac{n}{d} \pmod{p_i -1}$ Hence, we have $\Delta_{n} = \sum_{d \mid \frac{n}{p^{\alpha_{i}}}} \mu (d) \cdot f(\frac{n}{d}) + \sum_{\substack{d' = d \cdot p_i \\ d \mid \frac{n}{p^{\alpha_{i}}}}} \mu (d') \cdot f(\frac{n}{d'}) \equiv \sum_{d \mid \frac{n}{p^{\alpha_{i}}}} \mu (d) \cdot f(\frac{n}{d}) + \sum_{\substack{d' = d \cdot p_i \\ d \mid \frac{n}{p^{\alpha_{i}}}}} -\mu (d) \cdot f(\frac{n}{d}) \equiv 0 \pmod{p_i -1}$, which concludes the proof.

Turkey National MO 2018 wrote: 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. Interesting blend of "asymptotic flavor" and divisibility problem, but quite "technical". Let us further define $a_0 = 0$. Therefore, we could extend our definition of sequence to \[ \sum_{i = 1}^{\infty} a_{\lfloor \frac{n}{i} \rfloor} = n^{10}, \]Therefore, \begin{align*} n^{10} - (n - 1)^{10} &= \sum_{i = 1}^{\infty} a_{\lfloor \frac{n}{i} \rfloor} - \sum_{i = 1}^{\infty} a_{\lfloor \frac{n - 1}{i} \rfloor} \\ &= \sum_{i \mid n} (a_i - a_{i - 1}) \end{align*}since $\left \lfloor \frac{n}{i} \right \rfloor = \left \lfloor \frac{n - 1}{i} \right \rfloor$ for all $i \nmid n$. Let us now define $a_i - a_{i - 1} = b_i$ for all $i \in \mathbb{N}$. Claim 01. $\varphi(k) \mid b_k$ for all $k \in \mathbb{N}$. Proof. Notice that we have $n^{10} - (n - 1)^{10} = \sum_{i \mid n} b_i$. By the Mobius Inversion Formula, we have \[ b_n = \sum_{d \mid n} \mu \left( \frac{n}{d} \right) ((d+1)^{10} - d^{10}) \]We will now prove an even stronger statement, that implies the above claim. Lemma. For any polynomial $P \in \mathbb{Z}[x]$, we have \[ \varphi(n) \mid \sum_{d \mid n} \mu \left( \frac{n}{d} \right) P(d) \]Proof. It suffices to prove that for any $k \ge \mathbb{N}_0$, then \[ \varphi(n) \mid \sum_{d \mid n} \mu \left( \frac{n}{d} \right) d^k \]To prove this, write $S(n) = \sum_{d \mid n} \mu \left( \frac{n}{d} \right) d^k$. We claim that $S(n)$ is multiplicative. Indeed, by letting $f(i) = i^k$ and $g(i) = \mu(i)$, which are both multiplicative function, then notice that $S$ is the Dirichlet Convolution of $f$ and $g$, in particular $S = f * g$, and it is well known that the Dirichlet Convolution of two multiplicative function is again multiplicative. Thus, it suffices to prove the result for prime powers. Indeed, this is not hard, when $n = p^{\ell}$, then \[ S(p^{\ell}) = \sum_{d \mid p^{\ell}} \mu \left( \frac{p^{\ell}}{d} \right) (p^{\ell})^k = p^{k \ell} - p^{k(\ell - 1)}\]and $\varphi(n) = p^{\ell} - p^{\ell - 1} \mid (p^{\ell})^k - (p^{\ell - 1})^k = S(p^{\ell})$ for all $\ell$. Thus, our claim is true. Claim 02. $a_n > n$ for all $n \in \mathbb{N}_{\ge 2}$. Proof. We'll proceed by induction to prove that $n < a_n$ for all $n \in \mathbb{N}_{\ge 2}$. Indeed, for $n = 2$, we have $a_2 = 2^{10} - 1 > 2$, which is true. Notice that $a_n \le \sum_{i = 1}^n a_{\lfloor \frac{n}{i} \rfloor} = n^{10}$ for all $n \in \mathbb{N}$. Therefore, for all $n \ge 2$, \begin{align*} n^{10} &= \sum_{i = 1}^n a_{\lfloor \frac{n}{i} \rfloor} = a_n + \sum_{i = 2}^n a_{\lfloor \frac{n}{i} \rfloor} \\ &\le a_n + \sum_{i = 2}^n \left \lfloor \frac{n}{i} \right \rfloor^{10} \le a_n + n^{10} \cdot \left( \sum_{i = 2}^n \frac{1}{i^{10}} \right) \\ &< a_n + n^{10} \cdot \left( \int_{2}^{\infty} \frac{1}{x^{10}} dx \right) = a_n + n^{10} \cdot \frac{1}{2^9} \end{align*}This forces $a_n > \frac{2^9 - 1}{2^9} \cdot n^{10} > n$ for all $n \ge 2$. Claim 03. The previous two claims imply the problem. Proof. Indeed, we need to prove that $n \mid c^{a_n} - c^{a_{n - 1}}$ for all $n \in \mathbb{N}$, where the case $n = 1$ is pretty obvious. Now, suppose that $n \ge 2$ and $c \ge 2$. Consider two possible cases for $c$. If $c$ is relatively prime to $n$, then from the first claim, we have $n \mid c^{\varphi(n)} - 1 \mid c^{|a_n - a_{n - 1}|} - 1 \mid c^{a_n} - c^{a_{n - 1}}$ by Euler's Theorem, and we are done. Otherwise, write $n = \ell_1 x$ and $c = \ell_2 y$, where $\gcd(\ell_1, x) = \gcd(\ell_2, y) = \gcd(x,y) = 1$ and $\text{rad}(\ell_1) = \text{rad}(\ell_2) = \text{rad}(\gcd(c,n))$. Therefore, by Euler's Theorem and the fact that $\varphi(d) \mid \varphi(n)$ if $d \mid n$, we have \[ x \mid c^{\varphi(x)} - 1 \mid c^{\varphi(n)} - 1 \mid c^{|a_n - a_{n - 1}|} - 1 \]and from Claim 02, we have \[ \nu_p(\ell_1) \le \ell_1 \le n \cdot \nu_p(\ell_2) \ \forall p \mid \text{rad}(\gcd(c,n)) \implies \ell_1 \mid \ell_2^{n} \mid \ell_2^{\min(a_{n - 1},a_n)} \mid c^{\min(a_{n - 1},a_n)} \mid c^{a_n} - c^{a_{n - 1}} \]Combining both results, we conclude that $n \mid c^{a_n} - c^{a_{n - 1}}$. Motivational Remark. Proving $n \mid c^{a_n} - c^{a_{n - 1}} = c^{\min(a_{n - 1}, a_n)}(c^{|a_n - a_{n - 1}|} - 1)$ for any positive integer $c$ forces you to think of two things immediately. By taking $c$ to be something relatively prime to $n$, we need $n \mid c^{|a_n - a_{n - 1}|} - 1$, so it would be good if we have $\varphi(n) \mid a_n - a_{n - 1}$. Similarly, taking $c$ to be a prime divisor of $n$, we would argue that $\min(a_{n - 1},a_n) \ge \nu_p(n)$ for all $n$ and any prime $p \mid n$. However, from this, we know that we need to prove two things: that $a_n - a_{n - 1}$ is divisible by $\varphi(n)$ for all $n \in \mathbb{N}$, and $a_{n - 1}$ grows faster than $\nu_p(n)$, in some sense. Seeing condition involving $\left \lfloor \frac{n}{i} \right \rfloor$ immediately forces me to consider $n^{10} - (n - 1)^{10}$ since $\left \lfloor \frac{n}{i} \right \rfloor = \left \lfloor \frac{n - 1}{i} \right \rfloor$ for a lot of values of $i$, and indeed it boils the statement nicely to something that is doable by Mobius Inversion Formula, and we just need to prove that this is always divisible by $\varphi(n)$.

hydo2332 wrote: Let $f(x) = x^{10} - (x-10)^{10}$ and $\Delta_{n} = a_n - a_{n-1}$. Using Möbius's Inversion, we have that $\sum_{d \mid n} \mu (d)\cdot f(\frac{n}{d}) = \Delta_{n}$. Notice that the problem's condition is equivalent to proving $ n \mid c^{\Delta_{n}} -1$ What if $c = n$? Or rather the smallest prime divisor of $n$

RevolveWithMe101 wrote: hydo2332 wrote: Let $f(x) = x^{10} - (x-10)^{10}$ and $\Delta_{n} = a_n - a_{n-1}$. Using Möbius's Inversion, we have that $\sum_{d \mid n} \mu (d)\cdot f(\frac{n}{d}) = \Delta_{n}$. Notice that the problem's condition is equivalent to proving $ n \mid c^{\Delta_{n}} -1$ What if $c = n$? Or rather the smallest prime divisor of $n$ If $c=n$ then we're done because $n$ clearly dividesa $n^{a_n} - n^{a_{n-1}}$.

hydo2332 wrote: RevolveWithMe101 wrote: hydo2332 wrote: Let $f(x) = x^{10} - (x-10)^{10}$ and $\Delta_{n} = a_n - a_{n-1}$. Using Möbius's Inversion, we have that $\sum_{d \mid n} \mu (d)\cdot f(\frac{n}{d}) = \Delta_{n}$. Notice that the problem's condition is equivalent to proving $ n \mid c^{\Delta_{n}} -1$ What if $c = n$? Or rather the smallest prime divisor of $n$ If $c=n$ then we're done because $n$ clearly dividesa $n^{a_n} - n^{a_{n-1}}$. @above what if $n = p^{2021}$ and $c = p$

Dude, the lemma is still true and prove all cases for all $n$ and $c$.

Your lemma is basically $\varphi(n) \mid \Delta_n$, but this doesn't prove the desired divisibility when $\gcd(n,c) \not= 1$. Euler's Theorem only works when $\gcd(n,c) = 1$. An example is just basically $n = p^{2021}$ and $c = p$.

Replacing the exponent $10$ with an arbitrary positive integer $k$, here is a combinatorial proof. There are $n^k$ different $k$-tuples $(x_1, ..., x_k)$ such that $1 \leq x_i \leq n$ for each $i$. We can also count them by finding the number of tuples with $gcd(x_1, ..., x_k) = d$, where $1 \leq d \leq n$, and summing over $d$. Let $a_n$ be the number of these tuples for which $gcd(x_1, ..., x_k) = 1$. Consider a tuple with $gcd(x_1, ..., x_k) = d$. Dividing all its components by $d$, we obtain a $k$-tuple enumerated by $a_{\lfloor \frac{n}{d}\rfloor}$. Notice that this is a bijection! Therefore, $$\sum_{d=1}^n a_{\lfloor \frac{n}{d}\rfloor}=n^{k}$$for all positive integers $n$. Since this serves as another definition of $a_n$, we conclude that our $a_n$ is the same as the one in the problem. Lemma. $\varphi(n)$ divides $a_n - a_{n-1}$. Proof. $a_n - a_{n-1}$ is the number of the $k$-tuples with the same properties that contain at least one $n$. Let $A$ be the set of these tuples, and consider them modulo $n$. Let $r$ be an integer coprime with $n$. Since all tuples in $A$ contain $n$, multiplying all components of a tuple by $r$ is a closed operation on $A$. It's also easy to verify that multiplying such a tuple with different numbers modulo $n$ gives different results. Hence, this operation divides $A$ into several equivalence classes of length $\varphi(n).$ Our combinatorial definition makes it clear that $a_n > a_{n-1}$ as well. We now have all the necessary information to copy and paste the last few lines of the number-theoretic solutions given above.

Here is a noob thought which is very common.