Romanian Master of Mathematics

Arguing indirectly, assume that $a\nmid b$, so $r_n\ne 0$ for all $n$. Let $M=\max (b,N)$.

We now prove that $r_{n+1}\ge b{r}_n$ for all $n\ge M$. Indeed, as $r_n<2^n/b\le a^n/b$, it follows that $b{r}_n<a^n$ and $b^{n+1}\equiv b{r}_n(\mathrm{mod}{a}^n)$. Therefore, $b{r}_n$ is the remainder $b^{n+1}$ leaves upon division by $a^n$, i.e., $b{r}_n$ is the smallest non-negative integer $r$ such that $a^n\mid b^{n+1}-r$. This implies $b{r}_n\le r_{n+1}$, as $a^{n+1}\mid b^{n+1}-r_{n+1}$.

To complete the solution, note that $r_M\ge 1$, so $r_{M+k}\ge b^k{r}_M\ge 2^k$ for all $k\ge 0$. On the other hand, $r_{M+k}<2^{M+k}/(M+k)<2^k$ for $k$ sufficiently large. This is a contradiction.

---

Alternative solution.

The conclusion holds under the much less restrictive condition $r_n<2^n/b$ for all integers $n\ge N$. The argument hinges on the lemma below:

Lemma. Consider two integers $b>a>1$. If $a$ does not divide $b$, then $\{b^n/a^n\}>1/b$ for infinitely many positive integers $n$; as usual, $\{x\}$ denotes the fractional part of the real number $x$.

Proof. For every positive integer $n$, write $x_n=\lfloor b^n/a^n\rfloor$ and $y_n=\{b^n/a^n\}$ and note that $b{y}_n-a{y}_{n+1}=a{x}_{n+1}-b{x}_n$ is an integer.

Suppose now, if possible, that $y_n\le 1/b$ for all $n\ge M$. Consider any such $n$ and note that $y_n>0$, as $a$ does not divide $b$, so $-1<-a/b<b{y}_n-b/a\le b{y}_n-a{y}_{n+1}\le 1-a{y}_{n+1}<1$. Hence the integer $b{y}_n-a{y}_{n+1}=0$, so $y_{n+1}=(b/a)y_n$.

Consequently, $y_n=(b/a{)}^{n-M}{y}_M$ for all $n\ge M$. As $b>a$, it then follows that $y_n\ge 1$ for all large enough $n$, contradicting the fact that $y_n<1$ whatever $n$. This establishes the lemma.

Back to the problem, suppose $a$ does not divide $b$. Then $b>a$; otherwise $2^n/b>r_n=b^n\ge 2^n$ which is impossible. Note that $a^n\{b^n/a^n\}=r_n<2^n/b$ for all large enough $n$. The lemma then implies $1/b<\{b^n/a^n\}<(1/b)(2/a{)}^n\le 1/b$ for some large enough $n$ which is clearly a contradiction.