Given a sequence of positive integers $a_1, a_2, a_3, \ldots$ such that for any positive integers $k$, $l$ we have $k+l ~ | ~ a_k + a_l$. Prove that for all positive integers $k > l$, $a_k - a_l$ is divisible by $k-l$.
Problem
Source: Polish MO Finals P1 2023
Tags: number theory, Sequence, Divisibility
Tintarn
29.03.2023 17:47
Write $d=k-\ell$ and choose $n$ such that $k+n$ is a multiple of $d$. Note that then also $\ell+n$ is a multiple of $d$ by construction.
Hence, by assumption $d \mid a_k+a_n$ and $d \mid a_\ell+a_n$ and hence also $d \mid a_k-a_{\ell}$ as desired.
timon92
29.03.2023 23:14
This problem was proposed by Burii.
Chiaquinha
13.04.2023 18:27
For $n \geq l+1$, taking $k= n-l$ give $n ~ | ~ a_{n-l} + a_{l}$. But $n ~ | ~ 2n ~ | ~ a_{n+l} + a_{n-l}$, so $n ~ | ~ a_{n+l} - a_{l}$ $\implies$ $k-l ~ | ~ a_{k} - a_{l}$.
levifb
06.06.2023 16:36
@above to do it you need $k \geq 2l$, not guaranteed. Fixing this idea: Let $\dfrac{k}{l} = 1 + \epsilon$ and take $n \in \mathbb{N}$ with $n > \dfrac{1}{\epsilon}$. Hence, $\dfrac{k}{l} > \dfrac{n+1}{n} \Rightarrow nk - (n+1)l >0$. Now, $k-l \mid nk - nl \mid a_l + a_{nk - (n+1)l}$ and $k-l \mid (n+1)k - (n+1)l \mid a_k + a_{nk - (n+1)l}$. Subtracting these two gives the conclusion.