NMO Selection Tests for BMO and IMO

Lemma. For any integer $p \ge 2$, if $c-1 \equiv 2^p \pmod{2^{p+1}}$, then $c^2 - 1 \equiv 2^{p+1} \pmod{2^{p+2}}$.
Proof. Write $c^2 - 1 = (c-1)(c+1)$. By hypothesis, $c-1$ is divisible by $2^p$. As $c+1$ leaves remainder 2 upon division by $2^p$, it follows that $2^{p+1}$ is the highest power of 2 dividing $c^2 - 1$, whence the conclusion of the lemma.
Let $2^\alpha$ and $2^\beta$ be the highest powers of 2 dividing $a-1$ and $b-1$, respectively. By hypothesis, $\alpha \ge 2$ and $\beta \ge 2$. Note that $a-1 \equiv 2^\alpha \pmod{2^{\alpha+1}}$ and $b-1 \equiv 2^\beta \pmod{2^{\beta+1}}$. We may and will assume $\alpha \le \beta$. Apply the lemma $\beta - \alpha$ times to get $a^{2^{\beta-\alpha}} - 1 \pmod{2^{\beta+1}} = 2^\beta$, so $a^{2^{\beta-\alpha}} - b = (a^{2^{\beta-\alpha}} - 1) - (b-1)$ is divisible by $2^{\beta+1}$.
Now, induct on $n$. By the preceding, if $n \le \beta + 1$, then $a^{2^{\beta-\alpha}} - b$ is divisible by $2^n$, so $k = 2^{\beta-\alpha}$ will do. Let $n > \beta$.
For the induction step, let $a^k - b$ be divisible by $2^n$ for some $k \ge 1$. If it is divisible by $2^{n+1}$ we are done, so let $a^k - b \equiv 2^n \pmod{2^{n+1}}$.

Second solution. Clearly, $k=1$ works for both $n=1$ and $n=2$, so let $n \ge 3$. If $a=1$ or $b=1$, the conclusion follows by Euler's theorem, so let $a \ge 5$ and $b \ge 5$. Note that $a$ and $b$ may be replaced by their residues modulo $2^n$ to assume them both less than $2^n$.
For every integer $2 \le m < n$, let $S_m = \{2^m u + 1 : u = 0, \dots, 2^{n-m} - 1\}$. We first show that if $x$ and $y$ are in $S_m$, then so is $xy \pmod{2^n}$. Write $x = 2^mu + 1$ and $y = 2^mv + 1$. Then $xy = 2^mv + 1$, where $w = 2^muv + u + v$. Note that $w_0 = w \pmod{2^{n-m}}$ falls in the range 0 through $2^{n-m} - 1$ and write $w = 2^{n-m}w' + w_0$. Then $xy = 2^m(2^{n-m}w' + w_0) + 1 = 2^nv + 2^mw_0 + 1$, where $2^mw_0 + 1 < 2^n$. Consequently, $xy \pmod{2^n} = 2^mv + 1$ is in $S_m$, as stated.
Let $2^\alpha$ and $2^\beta$ be the highest powers of 2 dividing $a-1$ and $b-1$, respectively. We may and will assume $\alpha \le \beta$. Note that $a = 2^\alpha u + 1$ belongs to $S_\alpha$, where $u$ is odd and $2 \le \alpha \le n-1$. By the preceding, the residues modulo $2^n$ of $a, a^2, a^3, \dots, a^{2^{n-\alpha}}$ are all in $S_\alpha$.
We now show that $2^{n-\alpha}$ is the least positive integer $s$ satisfying $a^s \equiv 1 \pmod{2^n}$. By minimality, $s$ divides $2^{n-1}$, as $a^{2^{n-1}} \equiv 1 \pmod{2^n}$. Write
$$a^{2^{n-\alpha}} - 1 = (a-1)(a+1)(a^2+1)\cdots(a^{2^{n-\alpha-1}} + 1).$$
As $2^\alpha$ divides $a-1$ and $2^{n-\alpha}$ divides $(a+1)(a^2+1)\cdots(a^{2^{n-\alpha-1}} + 1)$, it follows that $2^n$ divides $a^{2^{n-\alpha}} - 1$, so $a^{2^{n-\alpha}} \equiv 1 \pmod{2^n}$.
Suppose now, if possible, that $s$ divides $2^{n-\alpha-1}$. Then $a^{2^{n-\alpha-1}} \equiv 1 \pmod{2^n}$, so $2^n$ divides $(a-1)(a+1)(a^2+1)\cdots(a^{2^{n-\alpha-2}} + 1)$. As $(a+1)(a^2+1)\cdots(a^{2^{n-\alpha-2}} + 1)$ is divisible by $2^{n-\alpha-1}$ but not by $2^{n-\alpha}$, it follows that $a-1$ is divisible by $2^{\alpha+1}$, contradicting the choice of $\alpha$. Consequently, $s = 2^{n-\alpha}$, as stated.

Third solution. Work in $\mathbb{Z}_{2^n}$. Clearly, $k=1$ works for both $n=1$ and $n=2$, so let $n \ge 3$. The units of $\mathbb{Z}_{2^n}$ consist of all positive odd integers less than $2^n$. They form a multiplicative copy of the additive $\mathbb{Z}_{2^{n-2}} \times \mathbb{Z}_2$ with generators $5$, of order $2^{n-2}$, and $2^n-1$, of order $2$. Thus every unit has the form $5^\gamma (2^n-1)^\epsilon$, $\gamma = 0, 1, \dots, 2^{n-2}-1$, $\epsilon = 0, 1$.
As $a$ and $b$ are both $1$ modulo $4$, it follows that $a = 5^\alpha$ and $b = 5^\beta$. As $5$ has order $2^{n-2}$, it is sufficient to provide a positive integer $k$ such that at least one of the numbers $\alpha k - \beta$ and $\beta k - \alpha$ is divisible by $2^{n-2}$.
Let $2^m$ be the highest power of $2$ dividing $\gcd(\alpha, \beta)$. Then at least one of the numbers $\alpha/2^m$ and $\beta/2^m$ is odd and hence invertible modulo $2^{n-2}$; say, $\alpha/2^m$ is odd and let $\alpha'$ be its inverse modulo $2^{n-2}$. Then $k = \alpha'\beta/2^m$ makes $\alpha k - \beta$ divisible by $2^{n-2}$, as desired.