Team Selection Test for IMO

Lemma. Let $a$ and $n$ be integers such that $a\equiv 1(\mathrm{mod}p)$ for each prime $p\nmid n$ and $a_n=1+a+a^2+\cdots +a^{n-1}$. Then $n\mid a_n$.

Proof of the lemma. Let $p^r$ be the largest power of the prime number $p$ such that $p^r\mid n$. We will prove the equality $$1+a+a^2+\cdots +a^{n-1}=\left(1+a^{p^r}+a^{2p^r}+\cdots +a^{(p-1)p^r}\right)\prod _{k=1}^r\left(1+a^{p^{k-1}}+a^{2p^{k-1}}+\cdots +a^{(p-1)p^{k-1}}\right)$$ for each integer $a$. If $a=1$ the left-hand side is $n$ and the right-hand side is $\frac{n}{p^r}{p}^r=n$ (one $p$ for each term in the product). Let $a\ne 1$. If we multiply the left-hand side and right-hand side by $a-1$ from the right we get $$\begin{array}{rl}& (a-1)(1+a+\cdots +a^{p-1})(1+a^p+a^{2p}+\cdots +a^{(p-1)p})\dots \left(1+a^{2p^r}+\cdots +a^{p^r}\right)\\ & =(a^p-1)(1+a^p+a^{2p}+\cdots +a^{(p-1)p})\dots \left(1+a^{2p^r}+\cdots +a^{p^r}\right)\\ & =(a^{p^2}-1)(1+a^{p^2}+\cdots +a^{(p-1)p^2})\dots \left(1+a^{p^{k-1}}+\cdots +a^{p^{k-1}}\right)\\ & =(a^{p^r}-1)\left(1+a^{p^r}+\cdots +a^{p^{r-1}}\right)=a^n-1\end{array}$$ Each expression in the product is divisible by $p$ since $$1+a^{p^{k-1}}+a^{2p^{k-1}}+\cdots +a^{(p-1)p^{k-1}}=(a^{p^{k-1}}-1)+(a^{2p^{k-1}}-1)+\cdots +(a^{(p-1)p^{k-1}}-1)+p$$ each of the expressions in brackets is divisible by $p$.

Without loss of generality we can assume that $n_1<n_2$. It is clear that $$\frac{a_{n_2}-a_{n_1}}{n_2-n_1}=\frac{1+a+\cdots +a^{n_2-1}-1-a-\cdots -a^{n_1-1}}{n_2-n_1}=\frac{a^{n_1}(1+a+\cdots +a^{n_2-n_1-1})}{n_2-n_1}$$ Using the lemma we get $(n_2-n_1)\mid a_{n_2-n_1}$ from where we get that the number $\frac{a_{n_2}-a_{n_1}}{n_2-n_1}$ is a natural number.