IMO 2006 Shortlisted Problems

We will prove by induction on $d$ that, for every positive integer $N$, there exist positive integers $b_0,b_1,\dots ,b_{d-1}$ such that, for each $i=0,1,2,\dots ,d-1$, we have $b_i>N$ and $$2^{b_i}+b_i\equiv i(\mathrm{mod}d).$$ This yields the claim for $m=b_0$.

The base case $d=1$ is trivial. Take an $a>1$ and assume that the statement holds for all $d<a$. Note that the remainders of $2^i$ modulo $a$ repeat periodically starting with some exponent $M$. Let $k$ be the length of the period; this means that $2^{M+k^{\prime }}\equiv 2^M(\mathrm{mod}a)$ holds only for those $k^{\prime }$ which are multiples of $k$. Note further that the period cannot contain all the $a$ remainders, since $0$ either is missing or is the only number in the period. Thus $k<a$.

Let $d=\gcd (a,k)$ and let $a^{\prime }=a/d,k^{\prime }=k/d$. Since $0<k<a$, we also have $0<d<a$. By the induction hypothesis, there exist positive integers $b_0,b_1,\dots ,b_{d-1}$ such that $b_i>\max \left(2^M,N\right)$ and $$\begin{array}{c}{2}^{b_i}+b_i\equiv i(\mathrm{mod}d)\text{ for }i=0,1,2,\dots ,d-1.\end{array}\text{\hspace{1em}(1)}$$ For each $i=0,1,\dots ,d-1$ consider the sequence $$\begin{array}{c}{2}^{b_i}+b_i,2^{b_i+k}+\left(b_i+k\right),\dots ,2^{b_i+\left(a^{\prime }-1\right)k}+\left(b_i+\left(a^{\prime }-1\right)k\right).\end{array}\text{\hspace{1em}(2)}$$ Modulo $a$, these numbers are congruent to $$2^{b_i}+b_i,2^{b_i}+\left(b_i+k\right),\dots ,2^{b_i}+\left(b_i+\left(a^{\prime }-1\right)k\right),$$ respectively. The $d$ sequences contain $a^{\prime }d=a$ numbers altogether. We shall now prove that no two of these numbers are congruent modulo $a$.

Suppose that $$\begin{array}{c}{2}^{b_i}+\left(b_i+mk\right)\equiv 2^{b_j}+\left(b_j+nk\right)(\mathrm{mod}a)\end{array}\text{\hspace{1em}(3)}$$ for some values of $i,j\in \{0,1,\dots ,d-1\}$ and $m,n\in \left\{0,1,\dots ,a^{\prime }-1\right\}$. Since $d$ is a divisor of $a$, we also have $$2^{b_i}+\left(b_i+mk\right)\equiv 2^{b_j}+\left(b_j+nk\right)(\mathrm{mod}d).$$ Because $d$ is a divisor of $k$ and in view of (1), we obtain $i\equiv j(\mathrm{mod}d)$. As $i,j\in \{0,1,\dots ,d-1\}$, this just means that $i=j$. Substituting this into (3) yields $mk\equiv nk(\mathrm{mod}a)$. Therefore $m{k}^{\prime }\equiv n{k}^{\prime }\left(\mathrm{mod}{a}^{\prime }\right)$; and since $a^{\prime }$ and $k^{\prime }$ are coprime, we get $m\equiv n\left(\mathrm{mod}{a}^{\prime }\right)$. Hence also $m=n$.

It follows that the $a$ numbers that make up the $d$ sequences (2) satisfy all the requirements; they are certainly all greater than $N$ because we chose each $b_i>\max \left(2^M,N\right)$. So the statement holds for $a$, completing the induction.