I can sence the beauty of the IMO 2018 problems... Exelent Job!!! problem selection committee & team leaders!! I would like to know whose problem is this?

Main claim: If $\frac{a}{x} + \frac{x}{b} - \frac{a}{b}$ is an integer, then $\gcd(a, b) | x.$ Proof: Compute the expression. It becomes $\frac{ab+x^2-ax}{bx}.$ Say a prime $p$ satisfies $p|a, p|b.$ Then $p|x^2$ so $p|x$. Divide it out and continue. Now, I will show that as the sequence goes along, that both the numerator and denominator of the reduced fraction $\frac{a_n}{a_1}$ will decrease as $n$ increases past $n \ge N.$ Now, assume that $\frac{a}{x} + \frac{x}{b} - \frac{a}{b}$ is an integer and $\gcd(a, b) = 1.$ Then $x | ab$ so $x = a'b'$ where $a' | a, b' | b$. Now take $a = a_n, b = a_1, x = a_{n+1}.$ Then $\frac{a_{n+1}}{a_1} = \frac{x}{b} = \frac{a'}{(b/b')}.$ So both the numerator and denominator decreased! Therefore, the sequence $\frac{a_n}{a_1}$ will eventually converge, as desired.

The condition implies that the difference $S(n) = \frac{a_{n+1}}{a_1} - \frac{a_n}{a_1} + \frac{a_n}{a_{n+1}}$ is an integer for all $n > N$. We proceed by $p$-adic valuation only henceforth. Claim: If $p \nmid a_1$, then $\nu_p(a_{n+1}) \le \nu_p(a_n)$ for $n \ge N$. Proof. The first two terms of $S(n)$ have nonnegative $\nu_p$, so we need $\nu_p(\frac{a_n}{a_{n+1}}) \ge 0$. $\blacksquare$ Claim: If $p \mid a_1$, then $\nu_p(a_n)$ is eventually constant. Proof. By hypothesis $\nu_p(a_1) > 0$. We consider two cases. First assume $\nu_p(a_k) \ge \nu_p(a_1)$ for some $k > N$. We claim that for any $n \ge k$ we have: \[ \nu_p(a_1) \le \nu_p(a_{n+1}) \le \nu_p(a_n). \]This is just by induction on $n$; from $\nu(\frac{a_n}{a_1}) \ge 0$, we have \[ \nu_p\left( \frac{a_{n+1}}{a_1} + \frac{a_n}{a_{n+1}} \right) \ge 0 \]which implies the displayed inequality (since otherwise exactly one term of $S(n)$ has nonnegative $\nu_p$). Thus once we reach this case, $\nu_p(a_n)$ is monotic but bounded below by $\nu_p(a_1)$, and so it is eventually constant. Now assume $\nu_p(a_k) < \nu_p(a_1)$ for every $k > N$. Take any $n > N$ then. We have $\nu_p\left(\frac{a_{n+1}}{a_1}\right) < 0$, and also $\nu_p\left(\frac{a_n}{a_1}\right) < 0$, so among the three terms of $S(n)$, two must have equal $p$-adic valuation. We consider all three possibilities: \begin{align*} \nu_p\left(\frac{a_{n+1}}{a_1}\right) = \nu_p\left(\frac{a_n}{a_1}\right) &\implies \boxed{\nu_p(a_{n+1}) = \nu_p(a_{n})} \\ \nu_p\left(\frac{a_{n+1}}{a_1}\right) = \nu_p\left(\frac{a_n}{a_{n+1}}\right) &\implies \boxed{\nu_p(a_{n+1}) = \frac{\nu_p(a_n) + \nu_p(a_1)}{2}} \\ \nu_p\left(\frac{a_{n}}{a_1}\right) = \nu_p\left(\frac{a_n}{a_{n+1}}\right) &\implies \nu_p(a_{n+1}) = \nu_p(a_1),\text{ but this is impossible}. \end{align*}Thus, $\nu_p(a_{n+1}) \ge \nu_p(a_n)$ and $\nu_p(a_n)$ is bounded above by $\nu_p(a_1)$. So in this case we must also stabilize. \qedhere $\blacksquare$ Since the latter claim is applied only to finitely many primes, after some time $\nu_p(a_n)$ is fixed for all $p \mid a_1$. Afterwards, the sequence satisfies $a_{n+1} \mid a_n$ for each $n$, and thus must be eventually constant. Remark: This solution is almost completely $p$-adic, in the sense that I think a similar result if one replaces $a_n \in {\mathbb Z}$ by $a_n \in {\mathbb Z}_p$ for any particular prime $p$. In other words, the primes almost do not talk to each other. There is one caveat: if $x_n$ is an integer sequence such that $\nu_p(x_n)$ is eventually constant for each prime then $x_n$ may not be constant. For example, take $x_n$ to be the $n$th prime! That's why in the first claim (applied to co-finitely many of the primes), we need the stronger non-decreasing condition, rather than just eventually constant.

Written a bit hastily, so let me know if there is any flaw. We have that $$\frac{a_n}{a_{n+1}}+\frac{a_{n+1}-a_n}{a_1} \in \mathbb{Z} \;\;\; \forall n \geq N \;\;\;\;\;\; (1)$$Now let $m>n$ be an integer and $$A=\frac{a_1}{a_2} + \frac{a_2}{a_3} + \ldots + \frac{a_{n-1}}{a_n}, \;\;\;\; B=\frac{a_n}{a_{n+1}}+\ldots +\frac{a_{m-1}}{a_m}$$Then $$B+\frac{a_m}{a_1}-\frac{a_n}{a_1}\in \mathbb{Z} \;\;\;\;(2)$$Taking $(1)$ from $n$ to $m$ combined with $(2)$ gives $$\frac{a_m}{a_1} \in \mathbb{Z} \; \Rightarrow \frac{a_m}{a_{m+1}}\in \mathbb{Z} \;\;\; \forall m > n$$So $a_{n+1}=ka_1,k\in \mathbb{Z}$. But $$\frac{a_n}{a_1}\left(1-\frac{1}{k} \right) \in \mathbb{Z}$$So either $k=1$ which implies $a_{n+1}=a_1 \Rightarrow a_m=a_{m+1} \;\; \forall m\geq n+1$ or $a_1|a_n \Rightarrow a_{n+1}|a_n \;\; \forall n$. In either case we're done. Edit: It is wrong. Thanks below.

knm2608 wrote: Taking $(1)$ from $n$ to $m$ combined with $(2)$ gives $\frac{a_m}{a_1} \in \mathbb{Z}$ How? I think (2) is just a repeated application of (1), so it seems like the most you will get out of this is a tautology. Great problem though!

Since the sequence is an integer sequence, the differences of consecutive terms must also be integers. So we have $$\frac{a_{n+1}^2-a_n a_{n+1} + a_n a_1}{a_1 a_{n+1}} \in \mathbb{Z}$$Subtracting 1, we have $a_1 a_{n+1} | (a_{n+1} - a_1) (a_{n+1} - a_n)$. Now consider any prime $p$ that divides $a_1, a_{n}$. Then we have, by dividing both sides by $p$, that $p| a_{n+1}$. Now divide all of $a_1, a_n, a_{n+1}$ by $p$, and then notice that we can still argue further like this. So $\min ( \nu_p (a_1), \nu_p (a_{n}) ) \le \nu_p(a_{n+1}) $. Since we have $a_1 a_{n+1} | (a_{n+1} - a_1) (a_{n+1} - a_n)$, we see that $a_{n+1} | a_1 a_n$. Note that if $\gcd (a_1, a_{n+1}) = \alpha_{n+1},$ then $a_{n+1} / \alpha_{n+1}$ is an integer, and it divides $a_n$, so the resulting conjugate factor is $k$ (say). Then $\frac{a_{n+1}}{a_1} = \frac{a_n/k}{a_{1}/\alpha_{n+1}}$, so the moduli of numerator and denominator are non-increasing. This leads us to $a_m = a_{m+1}$ from some $m$ onwards, since no positive integer sequence can strictly decrease forever.

Here's a solution I wrote during the competition. Quite similar to the one written by v_Enhance, but the execution is maybe a little bit bloodier. Solution: Proof by contradiction. For the rest of the solution we assume that the sequence $a_n$ isn't constant starting from any point. In the end we will achieve a contradiction, thus proving the statement. The difference $$ \frac{a_{n+1}}{a_1} + \frac{a_n}{a_{n+1}} - \frac{a_n}{a_1} = \frac{a_{n+1}^2 - a_{n+1}a_n + a_na_1}{a_1a_{n+1}} $$ is an integer for all $n \ge N$. Lemma 1. There is a prime $p$ such that $v_p(a_{n+1}) \neq v_p(a_n)$ for infinitely many $n \ge N$. Proof. The integer-ness condition above implies that $a_{n+1} \mid a_na_1$. This means that for all $p \mid a_n$, $p$ prime and $n \ge N$, we have either $p \mid a_N$ or $p \mid a_1$ (assume not, and take the smallest $i > N$ for which $p \mid a_i$). Thus, there are only finitely many $p$ such that $p \mid a_n$ for some $n \ge N$. Now, for the statement of the lemma, assume not: now, if we take any prime $p$ which doesn't divide any of the numbers $a_1, a_N, a_{N+1}, a_{N+2}, \ldots $, then we of course have $v_p(a_{n+1}) = v_p(a_n)$ for all $n \ge N$. For the rest of the primes, which we have finitely many, we must have $v_p(a_{n+1}) = v_p(a_n)$ for all large enough $n$. But this means that the sequence $a_n$ is constant, which is a contradiction. Thus, the statement of the lemma is true. Now, take any prime $p$ satisfying the condition of lemma 1. Define $v_p(a_n) = b_n$ for all $n$. We aren't that interested in the cases where $b_{n+1} = b_n$, but luckily we have infinitely many interesting cases. Lemma 2. If $b_{n+1} > b_n$, we have $b_{n+1} = b_1$. Proof: we divide into two cases, one where $b_{n+1} > b_1$, and one where $b_{n+1} < b_1$. We prove that both of these cases lead into a contradiction, which proves the lemma. If $b_{n+1} > b_1$, then $v_p(a_{n+1}^2 - a_na_{n+1} + a_na_1) = v_p(a_na_1) = b_n + b_1 < b_{n+1} + b_1 = v_p(a_{n+1}a_1)$, contradicting the fact that $a_{n+1}a_1$ divides $a_{n+1}^2 - a_na_{n+1} + a_na_1$. In a similar manner we see that if $b_{n+1} < b_1$, then the $v_p$ of the denominator is $b_n + b_{n+1}$, which is less than $b_{n+1} + b_1$, since $b_1 > b_{n+1} > b_n$. Thus, we must have $b_{n+1} = b_1$. Lemma 3. If $b_{n+1} < b_n$, then we have $b_1 \ge b_{n+1}$. Proof. Again, a proof by contradiction. Now, the $v_p$ of the denominator is $2b_{n+1}$, which is less than $b_1 + b_{n+1}$. Now, we have our setup ready. We only need the following crucial lemma, and then we are basically done: Lemma 4. There exists an $n \ge N$ such that $b_n = b_1$. Proof. Surprise, a proof by contradiction. Now, if $b_{n+1} > b_n$ for some $n$, then $b_{n+1} = b_1$ due to lemma 2. This can't happen, so $b_{n+1} \le b_n$ for all $n$. So $b_n$ is a decreasing sequence, which is a contradiction with the fact that $b_{n+1} \neq b_n$ for infinitely many $n$, and that $b_n \ge 0$ for all $n$. Now, take such $n$ that $b_n = b_1$. If $b_{n+1} = b_n$, just increment $n$ by $1$ as long as we have $b_{n+1} \neq b_n = b_1$. This gives a contradiction: if $b_{n+1} > b_n$, then due to lemma 2 we have $b_1 = b_{n+1} > b_n = b_1$, a contradiction. if $b_{n+1} < b_n$, then due to lemma 3 we have $b_1 \le b_{n+1} < b_n = b_1$, a contradiction. Thus, the original assumption of the statement being false gave a contradiction. The sequence $a_m$ is therefore constant starting from some point. Motivation: The divisibility condition given is very nice for investigating the $p$-adic valuations, as there are no constant terms. Then, you just bash the cases a little bit to use the well-known lemma $v_p(a \pm b) = \min(v_p(a), v_p(b))$ for $v_p(a) \neq v_p(b)$. I was hoping for a direct contradiction in either one of the cases $b_{n+1} > b_n$ or $b_{n+1} < b_n$, but I wasn't able do get this, so I just picked up all the nice information I got from the case-work there. When you really look at lemmas 2 and 3, it's not too difficult to come up with the rest of the solution. Lemma 1 is only needed to describe the prime we pick for our "$v_p$-bash".

The difference $\frac{a_{n+1}}{a_1} - \frac{a_n}{a_1} + \frac{a_n}{a_{n+1}}$ is also an integer for $n \ge N$. Hence \[a_1 a_{n+1} \mid a_{n+1}^2 - a_n a_{n+1} + a_1 a_n \equiv (a_{n+1} - a_1)(a_{n+1} - a_n).\] Lemma. If $a$, $x$, $y$ are positive integers with $ay \mid (y - a)(y - x)$ and $p$ is a prime, then \[\min\big(\nu_p(a), \nu_p(x)\big) \le \nu_p(y) \le \max\big(\nu_p(a), \nu_p(x)\big).\]This can be easily proved by examining the possibilities $\nu_p(y) < \min\big(\nu_p(a), \nu_p(x)\big)$ and $\nu_p(y) > \max\big(\nu_p(a), \nu_p(x)\big)$; both lead to $\nu_p$ contradictions in the divisibility. Corollary 1. $\gcd(a_1, a_n) \mid a_{n+1} \mid \mathrm{lcm}(a_1, a_n)$ for $n \ge N$. Corollary 2. $\gcd(a_1, a_n) \mid \gcd(a_1, a_{n+1})$ and $\mathrm{lcm}(a_1, a_{n+1}) \mid \mathrm{lcm}(a_1, a_n)$ for $n \ge N$. Hence $\{\gcd(a_1, a_n)\}_{n \ge N}$ and $\{\mathrm{lcm}(a_1, a_n)\}_{n \ge N}$ are increasing and decreasing sequences (respectively) bounded by $a_1$. Thus they are eventually constant; say $\gcd(a_1, a_m) = u$ and $\mathrm{lcm}(a_1, a_m) = v$ for $m \ge M$. Then \[a_m = \frac{\gcd(a_1, a_m) \cdot \mathrm{lcm}(a_1, a_m)}{a_1} = \frac{uv}{a_1}\]for all $m \ge M$, as desired.

v_Enhance wrote: The condition implies that the difference \[ \frac{a_{n+1}}{a_1} - \frac{a_n}{a_1} + \frac{a_n}{a_{n+1}} \]is an integer for all $n > N$. We proceed by $p$-adic valuation only henceforth. Claim: If $p \nmid a_1$, then $\nu_p(a_{n+1}) \le \nu_p(a_n)$ for $n \ge N$. Proof. The third term in the difference must have nonnegative $\nu_p$. $\blacksquare$ Claim: If $p \mid a_1$, then $\nu_p(a_n)$ is eventually constant. Proof. By hypothesis $\nu_p(a_1) > 0$. We consider two cases, First assume $\nu_p(a_k) \ge \nu_p(a_1)$ for some $k > N$. We claim that for any $n \ge k$ (by induction) we have: \[ \nu_p(a_1) \le \nu_p(a_{n+1}) \le \nu_p(a_n). \]Note in this case that $\nu(\frac{a_n}{a_1}) \ge 0$, so we must have \[ \nu_p\left( \frac{a_{n+1}}{a_1} + \frac{a_n}{a_{n+1}} \right) \ge 0 \]which implies the displayed inequality (since otherwise exactly one of the summands has nonnegative $\nu_p$). Thus once we reach this case, $\nu_p(a_n)$ is monotic but bounded below by $\nu_p(a_1)$, and so it is eventually constant. Now assume $\nu_p(a_k) < \nu_p(a_1)$ for every $k > N$. Take any $n > N$ then. We have $\nu_p\left(\frac{a_{n+1}}{a_1}\right) < 0$, and also $\nu_p\left(\frac{a_n}{a_1}\right) < 0$, so among the three summands two must have equal $p$-adic valuation. We consider all three possibilities: \begin{align*} \nu_p\left(\frac{a_{n+1}}{a_1}\right) = \nu_p\left(\frac{a_n}{a_1}\right) &\implies \boxed{\nu_p(a_{n+1}) = \nu_p(a_{n})} \\ \nu_p\left(\frac{a_{n+1}}{a_1}\right) = \nu_p\left(\frac{a_n}{a_{n+1}}\right) &\implies \boxed{\nu_p(a_{n+1}) = \frac{\nu_p(a_n) + \nu_p(a_1)}{2}} \\ \nu_p\left(\frac{a_{n}}{a_1}\right) = \nu_p\left(\frac{a_n}{a_{n+1}}\right) &\implies \nu_p(a_{n+1}) = \nu_p(a_1),\text{ but this is impossible}. \end{align*}Thus, eventually $\nu_p(a_{n+1}) \ge \nu_p(a_n)$ in either possible situation, but $\nu_p(a_n)$ is bounded above by $\nu_p(a_1) - 1$, so in this case we must also stabilize. \qedhere $\blacksquare$ Since the latter claim is applied only to finitely many primes, after some time $\nu_p(a_n)$ is fixed for all $p \nmid a_n$. Afterwards, the sequence satisfies $a_{n+1} \mid a_n$ for each $n$, and thus must be eventually constant. Remark: This solution is almost completely $p$-adic, in the sense that I think a similar result if one replaces $a_n \in {\mathbb Z}$ by $a_n \in {\mathbb Z}_p$ for any particular prime $p$. In other words, the primes almost do not talk to each other. There is one caveat: if $x_n$ is an integer sequence such that $\nu_p(x_n)$ is eventually constant for each prime then $x_n$ may not be constant. For example, take $x_n$ to be the $n$th prime! That's why in the first claim (applied to co-finitely many of the primes), we need the stronger non-decreasing condition, rather than just eventually constant. This is basically my solution. This "caveat" at the end is easy to get around if you notice that since $\frac{a_{n+1}^2-a_na_{n+1}+a_na_1}{a_1a_{n+1}}$ is an integer, $a_{n+1} \mid a_na_1$, so eventually $\frac{a_n}{(a_n,a_1)}$ converges to a constant. Then you basically do this analysis only on primes that divide $a_1$, of which there are finitely many. I think this is the more intuitive way to deal with it.

For any prime $p$, $v_p (a_{n+1})$ is between $v_p (a_n)$ and $v_p (a_1)$. That's it. Was expecting more from an IMO P5

Let $x=a_1$. Throughout the problem, $n$ will denote an arbitrary number $\ge N$. Notice \[ \frac{a_{n}}{a_{n+1}} + \frac{a_{n+1}-a_n}{x} = \left( \frac{a_1}{a_2}+\cdots + \frac{a_n}{a_{n+1}} + \frac{a_{n+1}}{x} \right) -\left( \frac{a_1}{a_2}+\cdots + \frac{a_n}{x} \right) \]is an integer. Thus $a_{n+1}=\frac{a_nx}{\ell_n}$ for some positive integer $\ell_n$ such that $x| \ell_n+a_{n+1}-a_n$. Thus, for any prime $p\nmid x$, we have $v_p(a_n)$ is decreasing, and so eventually becomes constant. There's finitely many primes that divide $a_N$, and so there's some $M\ge N$ such that for any $p\nmid x$, the quantity $v_p(a_n)$ is fixed after $n\ge M$, and the $\ell_n$'s are only divisible by primes in $P:=\{ p | x\}$, i.e. primes that divide $x$. From now on, $n$ will denote an arbitrary number $\ge M$. Let $p\in P$ and set $b:= v_p(x)$, $b_n := v_p(a_n)$. Assume for some $n$, $b_{n+1}> b_n$, so that $b > v_p(\ell_n)$. Notice $v_p(a_{n+1}-a_n) = b_n$ but $b\le v_p(\ell_n+a_{n+1}-a_n)$, and so $b_n=v_p(\ell_n) < b$. Thus $b_{n+1}=b$ and so $p^b | \ell_{n+1} + a_{n+2}$. But $v_p(\ell_{n+1}) + v_p(a_{n+2}) = 2b$ and so both must be $b$, thus $b_{n+2}=b$ and thus the sequence $\{b_i\}$ is eventually constant. Otherwise, the sequence is never increasing, but it can never be negative, so it's also eventually constant. Since $P$ is finite, and all these sequences are constant, we get the $P$-part of the $\{a_n\}$ sequence is eventually constant. But the first paragraph proves the non-$P$ part is also eventually constant. Thus, the sequence itself is eventually constant as desired.

The proof is quite straight for a problem $5$. Lemma:There are finite primes dividing one or more elements of the sequence. Proof:Assume for country then there exists a prime $p$ so that $p$ divides $a_{t+1}$ for some large $t$ but not the previous elements of the subset.Since $\frac{a_{t+1}}{a_1} - \frac{a_t}{a_1} + \frac{a_t}{a_{t+1}}$ has to be an integer this is impossible. Let $\mathbb{P}$ denote the set of primes dividing at least one element of the sequence and take $p \in \mathbb{P}$.We divide the problem into two cases. First case:$v_p(a_n) <v_p(a_1)$ holds for all integer $n \ge N$:Since $\frac{a_{n+1}}{a_1} - \frac{a_n}{a_1} + \frac{a_n}{a_{n+1}}$ has to be an integer using nothing more than $p$-adic calculations one can show $v_p(a_N) \le v_p(a_{N+!} \le \dots$ because the sequence of $v_p(a_i)$ has an upper bound it has to be constant after somewhere. Second case :There exist $\ell \ge N$ so that $v_p(a_{\ell }) \ge v_p(a_1)$.By induction and some $p$-adic calculations one can prove $v_p(a_{\ell }) \ge v_p(a_{\ell +1}) \ge \dots $ and all this values are bigger than or equal to $v_p(a_1)$ so by FMID it has to be constant after somewhere. So there exist an $M$ so that powers of all primes in $\mathbb{P}$ is constant in $a_M,a_{M+1},\dots $ since they are the only primes dividing one or more element of the sequence hence all these numbers have to be equal. Is this solution true?If so then why is this a problem $5$(I came up with it within 30 minutes in the mock imo we had in Iran while I spend some hours or days to solve some other problems 5's). Remark:I noticed this is a way to deal with the issue evan remarked in his answer to show the wrong appropach..

More or less the same idea as above. Suppose that $n \ge N$ and $a_1 = c$ then we get that $$ca_{n + 1} | a_{n+1}^2 + a_nc - a_na_{n+1}$$ We must have for every prime $p$ $v_p(c) + v_p(a_{n + 1}) \le v_p(a_{n+1}^2 + a_nc - a_na_{n+1})$. $\textbf{Lemma 1.}$ $v_p(a_{n + 1}) \le \max(v_p(c),v_p(a_n))$ Proof: Suppose the contrary, then $v_p(c) + v_p(a_n) < v_p(a_n) + v_p(a_{n + 1}) < 2v_p(a_{n + 1})$ so $v_p(c) + v_p(a_{n + 1}) \le v_p(c) + v_p(a_n)$ or $v_p(a_{n + 1}) \le v_p(a_n)$, contradiction. $\textbf{Lemma 2.}$ If $v_p(a_{n + 1}) < v_p(a_n)$ then $v_p(a_{n + 1}) \ge v_p(c)$ Proof: Suppose $v_p(a_{n + 1}) < v_p(c) \le v_p(a_n)$ then $2v_p(a_{n + 1}) < v_p(a_{n + 1}) + v_p(a_n) < v_p(c) + v_p(a_n)$ so $v_p(c) + v_p(a_n) \le 2v_p(a_{n + 1})$, contradiction. By lemma $1$ it's also possible to prove that there are finite number of prime $p$ such that $p$ divides at least one $a_n$. Now consider the following cases: $\textbf{Case 1.}$ $v_p(a_N) < v_p(c)$. We must have that $v_p(a_n) \le v_p(c)$ from lemma $1$ and induction. Suppose there exists $n$ with $v_p(a_{n + 1}) < v_p(a_n)$, then $v_p(a_n) > v_p(a_{n + 1}) \ge v_p(c)$, contradiction. Therefore, sequence $b_{n} = v_p(a_{n + N})$ is upper bounded and increasing, so it converges. $\textbf{Case 2.}$ $v_p(a_N) \ge v_p(c)$, then one can prove by induction with lemma $2$ that $v_p(a_n) \ge v_p(c)$. Suppose there exist $n$ with $v_p(a_{n + 1}) > v_p(a_n)$, then $v_p(a_n) \ge \max(v_p(c),v_p(a_n)) > v_p(a_{n + 1}) > v_p(a_n)$, contradiction. Therefore, sequence $c_{n} = v_p(a_{n + N})$ is lower bounded and decreasing, so it converges. There are finite prime numbers $p$ so the conclusion follows.

What is $p$-adic valuation?

jdevine wrote: I solved it the same way as #3. What is $p$-adic valuation? Basically considering the largest power of prime $p$ dividing a rational number. Doesn't make sense here but formally speaking if $r=p^a\cdot\frac bc$ with neither $b$ nor $c$ divisible by $p$ then the $p$-adic valuation of $r$ is $p^{-a}$. In any case allow me to write my solution too, also based on the fact that for each $n\ge N$ we have \[\frac{a_n}{a_{n+1}}+\frac{a_{n+1}-a_n}{a_1}\]is an integer. Also consider (like some previous solution) the idea of $v_p$: if $r=p^a\cdot\frac bc$ with neither $b$ nor $c$ divisible by $p$ then $v_p(r)=a$, with $a$ an integer, possibly negative. Observe that $v_p(\frac{a_n}{a_{n+1}}+\frac{a_{n+1}-a_n}{a_1})\ge 0$ for all prime $p$. Suppose that we have $v_p(a_{n+1}) < \min(v_p(a_1), v_p(a_n))$. Then the following happens: $\bullet$ $v_p(\frac{a_n}{a_{n+1}})=v_p(a_n)-v_p(a_{n+1})>0$ $\bullet$ $v_p(a_{n+1}-a_n)=v_p(a_{n+1})$, since if $v_p(a)\neq v_p(b)$ then $v_p(a+b)=v_p(a-b)=\min(v_p(a), v_p(b))$. $\bullet$ $v_p(\frac{a_{n+1}-a_n}{a_1}) = v_p(a_{n+1}-a_n)-v_p(a_1) = v_p(a_{n+1}) - v_p(a_1) < 0$ $\bullet$ $v_p(\frac{a_n}{a_{n+1}}+\frac{a_{n+1}-a_n}{a_1}) < 0$ This is a contradiction so $v_p(a_{n+1}) <\ge \min(v_p(a_1), v_p(a_n)) = v_p(\gcd(a_1, a_n))$ for all $p$, and hence $\gcd(a_{n+1}, a_1)\ge \gcd(a_n, a_1)$ so this sequence must be nondecreasing. Since $\gcd(a_n, a_1)\le a_1$ anyway, this sequence of $\gcd(a_n, a_1)$ must be constant after one point, i.e. there exists $N_1$ and $C$ such that $\gcd(a_n, a_1)=C$ for all $n\ge N_1$. Now let $\gcd(a_n, a_1)=\gcd(a_{n+1}, a_1)$ for some $n$. Then for each prime $p$, either $v_p(a_n)\ge v_p(a_1)$ and $v_p(a_{n+1})\ge v_p(a_1)$, or $v_p(a_n)=v_p(a_{n+1})<v_p(a_1)$. In the first case, $v_p(a_1)\le \min( v_p(a_n), v_p(a_{n+1}) \le v_p(a_{n+1}-a_n)$ so $v_p(\frac{a_{n+1}-a_n}{a_1})\ge 0$. This would mean that $v_p(\frac{a_n}{a_{n+1}})\ge 0$ too, otherwise the desired expression cannot be an integer. In the second case we have $v_p(\frac{a_n}{a_{n+1}})= 0$. In either case we have $v_p(\frac{a_n}{a_{n+1}})\ge 0$ and since this holds true for all $p$, $\frac{a_n}{a_{n+1}}$ is an integer, hence $a_{n+1}|a_n$. Repeating this for all $n\ge N_1$ we have $a_{n+1}\le a_n$ for all $n\ge N_1$, and since the sequence cannot strictly decrease indefinitely, we must have $a_n=a_{n+1}$ eventually.

jdevine wrote: Let $a_1$, $a_2$, $\ldots$ be an infinite sequence of positive integers. Suppose that there is an integer $N > 1$ such that, for each $n \geq N$, the number $$\frac{a_1}{a_2} + \frac{a_2}{a_3} + \cdots + \frac{a_{n-1}}{a_n} + \frac{a_n}{a_1}$$is an integer. Prove that there is a positive integer $M$ such that $a_m = a_{m+1}$ for all $m \geq M$. Let $P(n)$ denote the given claim for all $n>N$. Now $$P(n+1)-P(n) \implies \frac{a_{n+1}-a_n}{a_1}+\frac{a_n}{a_{n+1}} \in \mathbb{Z} \implies a_{n+1} \mid a_1a_n.$$Now write $a_n=b_ng_n$ for all $n>N$ such that $\gcd(b_n, a_1)=1$ and $b_n \mid a_n$ is the largest such number. Then $b_{n+1} \mid (g_na_1)b_n \implies b_{n+1} \mid b_n$ so for some constant $K>N$ and all $n>K$ we have $b_n \overset{\text{def}}{:=} b$ for some positive integer $b$ with $(b,a_1)=1$. Now $$\frac{a_{n+1}-a_n}{a_1}+\frac{a_n}{a_{n+1}} -1 \in \mathbb{Z} \implies \frac{(bg_{n+1}-g_n)(g_{n+1}-g_n)}{a_1g_{n+1}} \in \mathbb{Z}$$so we consider the following claim. Lemma. Suppose $(g_n)_{n>K}$ is a sequence of positive integers and $a_1=a$ is an integer such that for all primes $p$ if $p \mid g_n$ for some $n>K$ then $p \mid a$. Suppose $$ \frac{(bg_{n+1}-g_n)(g_{n+1}-g_n)}{a_1g_{n+1}} \in \mathbb{Z}$$for all $n>K$. Then $(g_n)_n$ is eventually constant. (Proof) Proceed by induction on $k=\sum_{p \, \text{prime}} v_p(a) \ge 0$. For $k=0$ it is trivial as all terms equal $1$. For any $k \ge 1$ fix a prime $p \mid a$ and any constant $T>K$. Now consider two cases: If $v_p(g_n)>v_p(a_1)$ for all $n>T$. Then plug $g_n=p^{v_p(a)}h_n$ and $a'=a/p^{v_p(a)}$. Apply induction hypothesis now with $K$ replaced by $T$. So assume this case never happens for any $T$. Else pick minimal $n>T$ with $v_p(g_{n+1})<v_p(a)$. Then $$v_p(g_{n+1}-g_n)+v_p(bg_{n+1}-a) \ge v_p(a)+v_p(g_{n+1}) \implies v_p(g_{n+1}-g_n) \ge v_p(a)>v_p(g_{n+1}) \implies v_p(g_n)=v_p(g_{n+1})<v_p(a)$$however since $n$ is minimal we must have $n=T+1$ and $v_p(g_{T+2})=v_p(g_{T+1})$. As $T$ can be any sufficiently large number we conclude $(v_p(g_n))_n$ is eventually constant for each prime $p$. Apply for all primes $p \mid a$ to complete the proof. $\blacksquare$ Conclusion follows.

Let $c=a_1$. The condition is equivalent to $\frac{a_n}{a_{n+1}} +\frac{a_{n+1}}{c} - \frac{a_n}{c} \in\mathbb Z$ for large enough $n$, which is equivalent to $ca_{n+1}\mid ca_n + a_{n+1}(a_{n+1}-a_n),$ so for any prime $p$, $$\nu_p(ca_{n+1}) \leqslant \nu_p(ca_n + a_{n+1}(a_{n+1}-a_n)).$$Suppose that $\nu_p(a_{n+1}) > \nu_p(a_n)$ and $\nu_p(a_{n+1})\neq \nu_p(c)$. This means $\nu_p(a_{n+1}(a_{n+1}-a_n)) = \nu_p(a_{n+1}) + \nu_p(a_n)\neq \nu_p(ca_n)$, so $$\nu_p(ca_n +a_{n+1}(a_{n+1}-a_n)) =\min\{\nu_p(ca_n), \nu_p(a_{n+1})+\nu_p(a_n)\} < \nu_p(ca_{n+1})$$which is impossible. Therefore, for all $n\geqslant N$ and any prime $p$, $$\nu_p(a_{n+1}) \leqslant \nu_p(a_n)\text{ or }\nu_p(a_{n+1}) = \nu_p(c).$$ In the latter case, we have $\nu_p(ca_{n+2}) \leqslant \nu_p(ca_{n+1} + a_{n+2}(a_{n+2}-a_{n+1})).$ If $\nu_p(a_{n+2})\neq \nu_p(c)$ then $$\nu_p(ca_{n+1} + a_{n+2}(a_{n+2}-a_{n+1})) = 2\min\{\nu_p(a_{n+2}), \nu_p(c)\} < \nu_p(ca_{n+2})$$which is a contradiction, hence $\nu_p(a_{n+2})=\nu_p(c)$. Doing this repeatedly, we have $\nu_p(a_{m}) = \nu_p(c)$ for all $m\geqslant n+1$. Therefore, for any prime $p$, as $\nu_p(a_n)$ is either eventually constant at $\nu_p(c)$ or a non-increasing sequence of non-negative integers, which is also eventually constant. Since there are only finitely many primes to consider (namely those dividing $ca_N$), the sequence $\{a_n\}$ is eventually constant. $\blacksquare$

the difference gives : $(1)$ $\frac{a_na_1+a_{n+1}(a_{n+1}-a_n)}{a_1a_{n+1}}\in \mathbb{Z}$ So $a_1|a_{n+1}(a_{n+1}-a_n)$. now let $\gcd(a_1,a_{n+1})=d$ then : $\frac{a_1}{d}|a_{n+1}-a_n\implies \gcd(\frac{a_1}{d},a_n)=1\implies \gcd(a_1,a_n)|d$ Which implies $\gcd(a_1,a_n)\le \gcd(a_1,a_{n+1})$ for any $n\ge N$ but $\gcd(a_1,a_{n+1})\le a_1$ so we must have an integer $K$ such that : $\gcd(a_1,a_n)=d$ for any $n\ge K$ So let $a_1=dc,a_n=db_n$ for $n\ge K$ from $(1)$ wh have : $\frac{b_nc+b_{n+1}(b_{n+1}-b_n)}{b_{n+1}c}\in \mathbb{Z}$ So : $b_{n+1}|cb_n$ but : $\gcd(c,b_{n+1})=1$ so $b_{n+1}|b_n\implies b_{n+1}\le b_n$ but $b_n$ is positive so we must have an integer $M$ such that : $b_n=b_{n+1}$ for $n\ge M$

Hi everyone I have some questions: On IMO site we can see that there are 172 $7$s in this problem. Most of the solutions use $v_p $ to solve this.What did motivate you to take $v_p $ ? In fact seeing ELMO 2017 SL N3 is a big advantage for this problem(that problem has the almost same idea) But since there are 172 7s ,there must be more well know problem that has same idea. Can anyone share his motivation on this problem?

This is a truly remarkable problem. Take large $n$. Then both of $\frac{a_{1}}{a_{2}} + \frac{a_{2}}{a_{3}} + \dots + \frac{a_{n - 2}}{a_{n - 1}}$ and $\frac{a_{1}}{a_{2}} + \frac{a_{2}}{a_{3}} + \dots + \frac{a_{n - 1}}{a_{n}}$ are integers, so $\frac{a_{n - 1}}{a_{n}} + \frac{a_{n}}{a_{1}} - \frac{a_{n - 1}}{a_{1}} = \frac{a_{n - 1}a_{1} + a_{n}(a_{n} - a_{n - 1})}{a_{n}a_{1}}$ is integer, so $a_{n} \mid a_{n - 1}a_{1}$. Thus induction shows $a_{n} \mid a_{n - k}a_{1}^k$ for some $k \le n - N$. Thus the set of prime dividing $a_{n}$ is finite. Let $p$ be a prime dividing one of $a_{n}$'s. Then since $\frac{a_{n - 1}a_{1} + a_{n}(a_{n} - a_{n - 1})}{a_{n}a_{1}}$ is integer, so $\nu_{p}(a_{n}) + \nu_{p}(a_{1}) \le \nu_{p}(a_{n - 1}a_{1} + a_{n}(a_{n} - a_{n - 1}))$. Claim: The sequence $(\nu_{p}(a_{n}))$ eventually becomes constant. Proof: If there doesn't exist $n \ge N$ such that $\nu_{p}(a_{n}) > \nu_{p}(a_{n - 1})$, then since $\nu_{p}(a_{m}) \ge 0$ for all $m$, so the sequence $(\nu_{p}(a_{n}))$ eventually becomes constant. Therefore there exist $n \ge N$ such that $\nu_{p}(a_{n}) > \nu_{p}(a_{n - 1})$. If $\nu_{p}(a_{n - 1}a_{1}) < \nu_{p}(a_{n}(a_{n} - a_{n - 1}))$, then $\nu_{p}(a_{n - 1}a_{1}) = \nu_{p}(a_{n - 1}a_{1} + a_{n}(a_{n} - a_{n - 1})) \ge \nu_{p}(a_{n}a_{1})$, so $\nu_{p}(a_{n - 1}) \ge \nu_{p}(a_{n})$, a contradiction. Thus $\nu_{p}(a_{n}a_{n - 1}) = \nu_{p}(a_{n}(a_{n} - a_{n - 1})) < \nu_{p}(a_{n - 1}a_{1})$, so $\nu_{a_{1}} \ge \nu_{p}(a_{n})$. Take minimum $k \ge n + 1$ such that $\nu_{p}(a_{k}) < \nu_{p}(a_{a_{k - 1}})$. (If there doesn't exist such $k$, then the sequence $(\nu_{p}(a_{n}))$ eventually becomes constant) Then if $2\nu_{p}(a_{k}) = \nu_{p}(a_{k}(a_{k} - a_{k - 1}) \ge \nu_{p}(a_{k - 1}a_{1})$, so $\nu_{p}(a_{1}) \ge \nu_{p}(a_{k - 1}) \le \nu_{p}(a_{k}) \ge \nu_{p}(a_{1})$, a contradiction. So $2\nu_{p}(a_{k})\nu_{p}(a_{k - 1}a_{1} + a_{k}(a_{k} - a_{k - 1})) \ge \nu_{p}(a_{k}a_{1})$, so $\nu_{p}(a_{1}) \ge \nu_{p}(a_{k - 1}) \le \nu_{p}(a_{k}) \ge \nu_{p}(a_{1})$, a contradiction. Thus the sequence $(\nu_{p}(a_{n}))$ eventually becomes constant.$\blacksquare$ By claim, taking large $n$, we have $\nu_{p}(a_{n}) = \nu_{p}(a_{n - 1})$ for all primes dividing the sequence $(a_{n})$ and since the set of prime dividing $a_{n}$ is finite, so the sequence $(a_{n})$ eventually becomes constant. $\blacksquare$

It's enough that $\frac{a_{n+1}}{a_1} - \frac{a_n}{a_1} + \frac{a_n}{a_{n+1}} = \frac{a_{n+1}^2 - a_{n+1} a_n + a_1 a_n}{a_1 a_{n+1}}$ be integrer. Let be $\alpha = \nu_{p}(a_n)$, $\beta = \nu_{p}(a_1)$ and $\theta = \nu_{p}(a_{n+1})$, and take $a_n = p^{\alpha} x$, $a_1 = p^{\beta} y$ and $a_{n+1} = p^{\theta} z$, the idea it's show that $\theta$ eventually becomes constant. From $\frac{a_{n+1}^2 - a_{n+1} a_n + a_1 a_n}{a_1 a_{n+1}}$, we have that $p^{\beta + \theta} \mid p^{2\theta} z^2 - p^{\theta + \alpha} xz + p^{\beta + \alpha} xy$ (1). So we gonna do 3 cases and see what happend with $\theta$. Case 1: $\alpha = \beta$ From (1), we know that $p^{\theta + \alpha} \mid p^{2\theta} z^2 - p^{\theta + \alpha} xz + p^{2\alpha} xy$$\rightarrow$$p^{\theta + \alpha} \mid p^{2\theta} z^2 + p^{2\alpha} xy$, so if $\theta < \alpha$$\rightarrow$$p^{\alpha-\theta} \mid z^2 + p^{2\alpha - 2\theta} xy$$\rightarrow$$p\mid z$, a contradition, and if $\theta > \alpha$$\rightarrow$$p^{\theta - \alpha} \mid p^{2\theta - 2\alpha} z^2 + xy$$\rightarrow$$p\mid xy$, a contradition. So $\alpha = \beta = \theta$. Case 2: $\alpha < \beta$ If $\beta \le \theta$$\rightarrow$$p^{\theta + \beta} \mid - p^{\theta + \alpha} xz + p^{\beta + \alpha} xy$ $= x p^{\beta + \alpha}(y - z p^{\theta - \beta})$$\rightarrow$$p^{\theta-\alpha} \mid y - p^{\theta - \beta}z$$\rightarrow$$\theta = \beta$, cause $y$ it's prime with $p$, or $\beta > \theta$. So supose $\beta >\theta$, if $\beta > \theta > \alpha$$\rightarrow$$p^{\beta-\alpha} \mid p^{\theta-\alpha} z^2 - xy + p^{\beta - \theta}xy$$\rightarrow$$p \mid xy$, a contradition, and if $\beta > \alpha > \theta$$\rightarrow$$p^{\beta - \theta} \mid z^2 - p^{\alpha - \theta} xz + p^{\beta + \alpha - 2\theta} xy$$\rightarrow$$p \mid z$, a contradition, so $\alpha = \theta$. Then if $\alpha < \beta$, we have that $\theta = \beta$ or $\theta = \alpha$. Case 3: $\alpha > \beta$ If $\theta > \alpha$$\rightarrow$$p^{\theta - \alpha} \mid p^{2\theta - \beta -\alpha} z^2 - p^{\theta - \beta} xz + xy$$\rightarrow$$p \mid xy$, a contradition, so $\theta \le \alpha$. To finish the problem, we gonna proff that $\theta$ it's eventually constant, for that, if $\alpha = \beta$, how $\beta$ it's constante, so $\theta$ is constant. If $\alpha > \beta$, how $\theta \le \alpha$, so $\theta$ becomes constant or eventually $\theta$ will be less that $\beta$, and it is our case 3, if $\alpha < \beta$, we have that $\theta = \alpha$ for all $n$ big, and becomes constant, or eventually $\theta = \beta$ and becomes constant. Thus, we finished.

nice problem

Denote the given sum as $S_n$. For $n \ge N$, we are given that \[S_{n+1}-S_n = \frac{a_{n+1}-a_n}{a_1}+\frac{a_n}{a_{n+1}}\] is an integer. Consider the following cases for $v_p(a_n)$ and $v_p(a_{n+1})$, where $p$ is an arbitrary prime: $v_p(a_n) > v_p(a_{n+1}): \quad$ We get $v_p\left(\frac{a_n}{a_{n+1}}\right) > 0$, so we just need \[v_p\left(\frac{a_{n+1}-a_n}{a_1}\right) \ge 0 \implies v_p(a_{n+1}) \ge v_p(a_1).\] $v_p(a_n) < v_p(a_{n+1}): \quad$ Since $v_p\left(\frac{a_n}{a_{n+1}}\right) < 0$, we must have \[ v_p\left(\frac{a_n}{a_{n+1}}\right) = v_p\left(\frac{a_{n+1}-a_n}{a_1}\right) \implies v_p(a_{n+1}) = v_p(a_1).\] $v_p(a_n) = v_p(a_{n+1}): \quad$ No definite outcome. Thus the behavior of our sequence $v_p(a_{N+1}), v_p(a_{N+2}), v_p(a_{N+3}), \ldots$ can be modeled as follows: This sequence begins greater than or equal to $v_p(a_1)$ and is weakly decreasing, but is bounded by $v_p(a_1)$. This sequence begins less than $v_p(a_1)$ and will remain constant until, at some point, it leaps to $v_p(a_1)$, where it forever remains fixed. As $a_1$ has finitely many prime factors, and our sequence is monotonic and eventually remains constant for all $p$, we get the desired conclusion. $\blacksquare$

We have $ a_1a_{N+1}$ $\mid$ $ a_{N+1} ( a_{N+1} - a_N) + $$ a_{1}a_N$ Claim : $v_p(a_{N+1}) \leq v_p(a_N)$ FTSOC, lets assume $v_p(a_{N+1}) > v_p(a_N)$ Therefore $ v_p(a_1) + v_p(a_{N+1}) \leq$ $Min[ v_p(a_{N+1}) +v_p(a_N) , v_p(a_1) + v_p(a_N)] $ Since $v_p(a_1) + v_p(a_N)$ is always less than $v_p(a_1) + v_p(a_{N+1})$. We get our contradiction. Now it is easy to see we will get a constant sequence after some time

Note that $\frac{a_{n+1}-a_n}{a_1}+ \frac{a_n}{a_{n+1}}$ must be an integer for all $n > N$. Claim: $\nu_p(a_i)$ is eventually constant and bounded by $\nu_p(a_1)$. We will do casework. Case 1: $\nu_p(a_n) < \nu_p(a_{n+1})$ We get that $\nu_p\left(\frac{a_{n+1}-a_n}{a_1}\right) = \nu_p\left(\frac{a_n}{a_{n+1}}\right)$ so $\nu_p(a_{n+1}) = \nu_p(a_1)$. Case 2: $\nu_p(a_n) > \nu_p(a_{n+1})$ We get that $\nu_p\left(\frac{a_{n+1}-a_n}{a_1}\right) \ge 0$ so $\nu_p(a_{n+1}) \ge \nu_p(a_1)$. From these two cases we can conclude the claim. Now we are done since the claim implies the sequence is eventually constant.

First of all, it \(n=2\) is not possible since we must have \(a_{2^m} + 2a_{2^{m+1}} = 0\) for each \(m\) which inductively gives \(a_1 = (-2)^ma_{2^m},\) which means that \(2^m|a_1\) for every \(m\) — this is impossible since \(a_1\) must be non-zero. We will show that it applies to each \(n \geq 3.\) It is enough for each \(n\) to find a function \(f_n : \mathbb{N} \to \mathbb{N},\) which from now on I will denote with \(f,\) with the properties (a) \(f(rs) = f(r)f(s)\) for each \(r,s \in \mathbb{N}\) (b) \(f(1) + 2f(2) + \cdots + nf(n) = 0\). Indeed, if \(f\) satisfies (a) and (b), then setting \(a_m = f(m)\) for each \(m\), we have \(\displaystyle{a_k + 2a_{2k} + \cdots + na_{nk} = f(k) + 2f(2k) + \cdots + nf(nk) = f(k)(1 + 2f(2) + \cdots +nf(n)) = 0.}\) We can therefore consider \(n \geq 3.\) We know from Bertrand's theorem that for every \(n \geq 2,\) there exists a prime \(p\) with \(n/2 < p \leq n.\) Let \(p\) be the greatest prime less than or equal to \(q\) and \(n,\) where \(q\) is the largest prime that is less than \(n.\) Then we have \(n/4 < q < p \leq n.\) If \(f(m) = a^{m_p}b^{m_q},\) posit where \(m_p, m_q\) are their powers in the prime factorization, and \(a, b\) are nonzero integers which will be determined later. We see that (a) is satisfied, and it is enough to choose them appropriately \(a, b\) so that (b) is also satisfied. Case 1: \(q > n/2.\) Then we want \(n-2 + pf(p) + qf(q) = 0.\) Because \(p, q\) are coprime, there are \(x, y\) such \(px + qy = 1.\) We define \(a = -(n-2)x, b = -(n-2)y,\) and we are done. Case 2: \(n/3 < q \leq n/2.\) Then we want \(n-3 + pf(p) + qf(q) + 2qf(2q) = 0.\) Case 2a: If \(q=2,\) then it must be \(n=3\) or \(n=4\) (since if \(n \geq 5,\) then \(p \geq 5\) and \(q \geq 3\)). The case \(n=3\) is rejected after \(q > n/2.\) For \(n=4,\) we have \(p=3, q=2,\) and want \(1 + 3f(3) + 2f(2) + 4f(2)^2 = 0,\) and it is enough to choose \(a = f(3) = -1\) and \(b = f(2) = -1.\) Case 2b: If \(q > 2,\) then we want \(n-3 + pf(p) + 3qf(q) = 0,\) and because \(p, 3q\) are coprime, we can find suitable \(a, b\) as in case 1. (For the \(a, b\) non-zeros to be, it is enough to check that \(n-3 \neq 0,\) which is true since if \(n=3,\) we would have \(q=2\) and would not be in case 2.) Case 3: \(n/4 < q \leq n/3.\) Then we want \(n-4 + pf(p) + qf(q) + 2qf(2q) + 3qf(3q) = 0.\) Case 3a: If \(q \leq 3,\) then you must \(n \leq 6.\) (Since if \(n \geq 7,\) then \(p \geq 7\) and \(q \geq 5 > 3.\)) But if \(n \leq 6,\) then \(q \leq n/3 \leq 2.\) So \(q = 2,\) and \(n=6.\) But this is inappropriate since for \(n=6,\) we have \(q=3.\) So here we have nothing to control. Case 3b: If \(q > 3,\) then we want \(n-4 + pf(p) + 6qf(q) = 0,\) and because \(p, 6q\) are coprime, we can find suitable \(a, b\) as in case 1. (For the \(a, b\) non-zeros to be, it is enough to check that \(n \neq 4,\) which is true since if \(n=4,\) we would have \(q=2\) and would not be in case 3.)

From the condition we get that $S(n) = \frac{a_{n+1}}{a_1} - \frac{a_n}{a_1} + \frac{a_n}{a_{n+1}}$ is an integer for all $n > N$. Now if $p \not \mid a_1$, then the first two terms of $S(n)$ have $\nu_p \geq 0$ $\Rightarrow$ $\nu_p(\frac{a_n}{a_{n+1}}) \geq 0$ $\Rightarrow$ $\nu_p(a_n) \geq \nu_p(a_{n+1}) $ for $n \geq N$. Now we will prove that if $p \mid a_1$, then $\nu_p(a_n)$ will be constant at some point. We have that $\nu_p(a_1) > 0$. Let $\nu_p(a_k) \ge \nu_p(a_1)$ for $k > N$. We will show that for all $n \ge k$ we have $\nu_p(a_1) \leq \nu_p(a_{n+1}) \leq \nu_p(a_n)$, which can be done by induction on n. Now from $\nu(\frac{a_n}{a_1}) \geq 0$, we have that $\nu_p(\frac{a_{n+1}}{a_1} + \frac{a_n}{a_{n+1}}) \geq 0$ which gives us the inequality we wanted, if thats not true we will have exactly one term of $S(n)$ with $\nu_p \geq 0$ $\Rightarrow$ $\nu_p(a_n)$ is monotonic and at the same time is lower bounded by $\nu_p(a_1)$ $\Rightarrow$ it will eventually be constant. Now let $\nu_p(a_k) < \nu_p(a_1)$ for every $k > N$. Also get any $n > N$. We have $\nu_p(\frac{a_{n+1}}{a_1}) < 0$, and also $\nu_p(\frac{a_n}{a_1}) < 0$, so from the three terms of $S(n)$, two must have equal $\nu_p$'s. We will check all 3 cases. 1) $\nu_p(\frac{a_{n+1}}{a_1}) = \nu_p(\frac{a_n}{a_1})$ $\Rightarrow$ ${\nu_p(a_{n+1}) = \nu_p(a_{n})}$, which is enough. 2) $\nu_p(\frac{a_{n+1}}{a_1}) = \nu_p(\frac{a_n}{a_{n+1}})$ $\Rightarrow$ ${\nu_p(a_{n+1}) = \frac{\nu_p(a_n) + \nu_p(a_1)}{2}}$, which is also enough. 3) $\nu_p(\frac{a_{n}}{a_1}) = \nu_p(\frac{a_n}{a_{n+1}})$ $\Rightarrow$ $\nu_p(a_{n+1}) = \nu_p(a_1)$, but this is false $\Rightarrow$ $\nu_p(a_{n+1}) \ge \nu_p(a_n)$ and $\nu_p(a_n)$ is upper bounded by $\nu_p(a_1)$, so we will get to a constant eventually. Since we apply this to finitely many primes, at some point $\nu_p(a_n)$ will get fixed for all $p \mid a_1$ $\Rightarrow$ the sequence will satisfy $a_{n+1} \mid a_n$ for all n $\Rightarrow$ it will eventually be constant.

My solution was incorrect. Thanks for report!

Let the whole sum be $S_n$ then for $n \ge N$ we will consider $S_{n+1}-S_n$, so we have that: \[S_{n+1}-S_n \in \mathbb Z \implies \frac{a_{n+1}}{a_1}+\frac{a_n}{a_{n+1}}-\frac{a_n}{a_1}=\frac{a_{n+1}-a_n}{a_1}+\frac{a_n}{a_{n+1}}=\frac{a_{n+1}^2-a_na_{n+1}+a_na_1}{a_1a_{n+1}} \in \mathbb Z \]Therefore $a_1a_{n+1} \mid a_{n+1}^2-a_na_{n+1}+a_na_1$ so $a_{n+1} \mid a_na_1$ Now if $p \not \; \mid a_1$ then $\nu_p(a_{n+1}) \le \nu_p(a_n)$ so it becomes a decreasing sequence so it will be eventually constant. Now notice that if we had for some $p$ prime that $p \mid a_1,a_n$ then $p \mid a_{n+1}$ so we can let $a_i=p \cdot b_i$ and realice we have the same condition for the new sequence, therefore by repeating until stuck we have that $\gcd(a_1,a_n) \mid a_{n+1}$ and from here we can also easly get $a_{n+1} \mid \text{lcm}(a_1,a_n)$, so now for a prime $p \mid a_1$ we have that $\text{min} \{\nu_p(a_1), \nu_p(a_n) \} \le \nu_p(a_{n+1}) \le \text{max} \{\nu_p(a_1), \nu_p(a_n) \}$ This holds for all $n \ge N$ so if we ever had $\nu_p(a_n)=\nu_p(a_1)$ then we would get $\nu_p(a_j)=\nu_p(a_1)$ for all $j \ge n$ And in the other 2 cases we get that either both $\nu_p(a_n), \nu_p(a_{n+1})$ are less than $\nu_p(a_1)$ or we get that $\nu_p(a_n) \ge \nu_p(a_{n+1})$ so either way for any such $p$ we get that the sequence of $\nu_p$'s stabilizes and converges at some point. Therefore for some $M$ we have that $a_n$ is constant for all $n \ge M$ (since then we would get that $a_{n+1} \mid a_n$ and so on, so we would mess with decreasing-ness) thus we are done.

We prove the following quick claim, which allows us to focus on a finite number of primes. Claim: Only finitely many primes divide $a_1, a_2, \dots$. Proof. Actually, the only primes that divide elements of the sequence are the divisors of $a_1, a_2, \dots, a_{N - 1}$. Suppose $p \nmid a_1a_2 \cdots a_{N - 1}$ and $p \mid a_M$ for some $M \geq N$. Then \[\nu_p\left(\frac{a_1}{a_2} + \frac{a_2}{a_3} + \dots + \frac{a_{M - 1}}{a_M} + \frac{a_M}{a_1}\right) = \nu_p\left(\frac{a_{M - 1}}{a_M}\right) < 0\]since $\nu_p(a_M) > 0$, a contradiction since the expression is parentheses is an integer. Since finitely many primes are divisors of $a_1a_2 \dots a_{N - 1}$, we're done. $\square$ Now let $p$ one of these primes; it suffices to show that the sequence $\nu_p(a_1), \nu_p(a_2), \dots$ is eventually constant. Claim: For any integer $n \geq N$, we have \[\nu_p(a_1) \leq \nu_p(a_n) \leq \nu_p(a_N)\]if $\nu_p(a_1) \leq \nu_p(a_N)$ and \[\nu_p(a_N) \leq \nu_p(a_n) \leq \nu_p(a_1)\]otherwise. Proof. Observe that \begin{align*} \left(\frac{a_1}{a_2} + \frac{a_2}{a_3} + \dots + \frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1}\right) - \left(\frac{a_1}{a_2} + \frac{a_2}{a_3} + \dots + \frac{a_{n - 1}}{a_n} + \frac{a_n}{a_1}\right) \\ = \frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1} - \frac{a_n}{a_1} \end{align*}is an integer, so $a_n/a_{n + 1} + a_{n + 1}/a_1$ and $a_n/a_1$ have the same denominator. Thus \[\nu_p\left(\frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1}\right) \geq 0 \iff \nu_p\left(\frac{a_n}{a_1}\right) \geq 0\]and \[\nu_p\left(\frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1}\right) < 0 \iff \nu_p\left(\frac{a_n}{a_1}\right) < 0 \iff \nu_p\left(\frac{a_n}{a_{n + 1}} + \frac{a_{n + 1}}{a_1}\right) = \nu_p\left(\frac{a_n}{a_1}\right) < 0.\] Let $k = \nu_p(a_n/a_{n + 1} + a_{n + 1}/a_1)$. Suppose first that $\nu_p(a_n/a_1) \geq 0$, or alternately $\nu_p(a_n) \geq \nu_p(a_1)$. This implies that $k \geq 0$ as well, so if $\nu_p(a_{n + 1}) > \nu_p(a_n)$ or $\nu_p(a_{n + 1}) < \nu_p(a_1)$ we get $k < 0$, a contradiction. Thus $\nu_p(a_1) \leq \nu_p(a_{n + 1}) \leq \nu_p(a_n)$. On the other hand, suppose $\nu_p(a_n) < \nu_p(a_1)$. Then $k = \nu_p(a_n/a_1) = \nu_p(a_n) - \nu_p(a_1)$, but \[k = \min\left(\nu_p\left(\frac{a_n}{a_{n + 1}}\right), \nu_p\left(\frac{a_{n + 1}}{a_1}\right)\right)\]unless $\nu_p(a_n/a_{n + 1}) = \nu_p(a_{n + 1}/a_1)$, which is clearly impossible since this implies $k = \frac12(\nu_p(a_n) - \nu_p(a_1))$. Thus $\nu_p(a_{n + 1}) \in \{\nu_p(a_1), \nu_p(a_n)\}$. In either case, by starting at $n = N$ and inducting upward, we obtain the desired bounds on $\nu_p(a_n)$. $\square$ The claim implies that for $n \geq N$, the sequence $\nu_p(a_n)$ is monotonic and bounded between $\nu_p(a_1)$ and $\nu_p(a_n)$, so it clearly has a limiting value. Since we're only examining finitely many primes, there is some integer $K$ for which $\nu_p(a_K) = \nu_p(a_{K + 1}) = \dots$, and thus the sequence is constant beginning with $a_K$. This completes the proof. $\square$ Remark. I would have lost partial credit if I had actually done this problem in contest, since it didn't occur to me until reading hints after solving that simply showing $\nu_p(a_n)$ converges for each prime doesn't quite finish.

Claim: There are finitely many primes that divide an integer in the sequence. Proof: For $i \geq N$ and for any prime $p$, the integer condition implies that \[ \nu_p \left( \tfrac{a_{i-1}}{a_i} \right) \geq \min \left(\nu_p \left( \tfrac{a_1}{a_2} \right), \nu_p \left( \tfrac{a_2}{a_3} \right), \ldots, \nu_p \left( \tfrac{a_{i-2}}{a_{i-1}} \right), \nu_p \left( \tfrac{a_{i}}{a_{1}} \right) \right). \]In particular, if we set $p$ to a prime that does not divide any of $a_1, \dots, a_{i-1}$, it follows that $a_N, a_{N+1}, \dots$ cannot contain new prime divisors that don't divide any of $a_1, \dots, a_{N-1}$. From hereon, let $i$ be any integer index greater than $N$ and fix some arbitrary prime $p$. Claim: If $\nu ( a_{i-1} )\geq \nu ( a_1 )$, it follows that $\nu ( a_i ) \geq \nu ( a_1 )$. Proof: Suppose FTSOC that $\nu ( a_i )< \nu ( a_1 )$. Subtracting the assertion for $i-1$ from $i$ implies that $- \tfrac{a_{i-1}}{a_1} + \tfrac{a_{i-1}}{a_i} + \tfrac{a_i}{a_1}$ is an integer. But by assumption, $\nu ( \tfrac{a_{i-1}}{a_1} )$ and $\nu ( \tfrac{a_{i-1}}{a_i} )$ are positive while $\nu ( \tfrac{a_i}{a_1} )$ is negative. This is a contradiction. Claim: If $\nu (a_{i-1} ) < \nu ( a_i )$, we have $\nu (a_i) = \nu (a_1)$. Proof: Once again, we only use that $- \tfrac{a_{i-1}}{a_1} + \tfrac{a_{i-1}}{a_i} + \tfrac{a_i}{a_1}$ is an integer. By assumption, $\nu (\tfrac{a_{i-1}}{a_i})$ is negative – moreover, by assumption, $\nu ( \tfrac{a_{i-1}}{a_1} )$ and $\nu ( \tfrac{a_i}{a_1} )$ are not equal. Therefore, to satisfy the integer condition, the smaller of the two, $\nu ( \tfrac{a_{i-1}}{a_1} )$, must equal $\nu (\tfrac{a_{i-1}}{a_i})$. This implies the claim.

Note that for integral $C \ge 0$ $$\frac{a_1}{a_2} + \frac{a_2}{a_3}+ \cdots +\frac{a_{N+C-1}}{a_{N+C}} + \frac{a_{N+C}}{a_1} \in \mathbb Z$$$$\frac{a_1}{a_2} + \frac{a_2}{a_3}+ \cdots +\frac{a_{N+C}}{a_{N+C+1}} + \frac{a_{N+C+1}}{a_1} \in \mathbb Z$$Subtracting the first expression from the second expression gives: $$\frac{a_{N+C+1}}{a_1} + \frac{a_{N+C}}{a_{N+C+1}} -\frac{a_{N+C}}{a_1} \in \mathbb Z$$Suppose for some prime $p$, $\nu_p (a_1) = 0$ this implies $\nu_p(a_{N+C}) \ge \nu_p(a_{N+C+1})$ implying that the sequence is eventually constant. Now if $\nu_p (a_1) \ge 1$ then if $\nu_p(a_1) >\nu_p (a_{N+C+1}) > \nu_p (a_{N+C})$ We have $$\nu_p (a_{N+C}) - \nu_p (a_{N+C+1}) = \nu_p(a_{N+C+1} - a_{N+C}) -\nu_p (a_1)$$$$\nu_p (a_{N+C}) - \nu_p (a_{N+C+1}) = \nu_p(a_{N+C}) -\nu_p (a_1)$$$$\nu_p (a_{N+C+1}) = \nu_p (a_1)$$If $\nu_p (a_{N+C})= \nu_p (a_1)$ suppose for the sake of contradiction that $\nu_p (a_{N+C+1}) \neq \nu_p (a_1)$, we have: $$\nu_p (a_{N+C}) - \nu_p ( a_{N+C+1}) = \nu_p(a_{N+C+1}) - \nu_p (a_1)$$$$\nu_p (a_{N+C})+\nu_p (a_1) = 2 \nu_p(a_{N+C+1}) $$$$\nu_p(a_1) = \nu_p(a_{N+C+1})$$A contradiction. If $\nu_p(a_1) > \nu_p (a_{N+C}) > \nu_p (a_{N+C+1})$ we have the middle fraction is an integer and it is impossible for $\nu_p(a_{N+C+1} - a_{N+C}) =\nu_p( a_{N+C+1}) \ge \nu_p(a_1) $ to be true. Now suppose $\nu_p (a_{N+C}) > \nu_p (a_1)$ we have that $$\frac{a_{N+C+1}}{a_1}+\frac{a_{N+C}}{a_{N+C+1}} \in \mathbb Z$$If $\nu_p (a_1) < \nu_p( a_{N+C+1})$ we have $\nu_p(a_{N+C+1} \le \nu_p (a_{N+C})$. Otherwise $\nu_p (a_{N+C+1}) \le \nu_p (a_i)$. Therefore the sequence will be stuck at a constant with $\nu_p$ less than $\nu_p (a_1)$, $\nu_p(a_1)$ if the sequnce changes at all. It is impossible for the sequence to stay strictly above $\nu_p (a_1)$ due to our last argument. Thus $(a_n)$ is eventually constant.