74th NMO Selection Tests for BMO and IMO

Lemma. For any integer $p\ge 2$, if $c-1\equiv 2^p(\mathrm{mod}{2}^{p+1})$, then $c^2-1\equiv 2^{p+1}(\mathrm{mod}{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 }(\mathrm{mod}{2}^{\alpha +1})$ and $b-1\equiv 2^{\beta }(\mathrm{mod}{2}^{\beta +1})$. We may and will assume $\alpha \le \beta$. Apply the lemma $\beta -\alpha$ times to get $a^{2^{\beta -\alpha }}-1(\mathrm{mod}{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(\mathrm{mod}{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(\mathrm{mod}{2}^n)$. Write $x=2^{m}u+1$ and $y=2^{m}v+1$. Then $xy=2^{m}v+1$, where $w=2^{m}uv+u+v$. Note that $w_0=w(\mathrm{mod}{2}^{n-m})$ falls in the range 0 through $2^{n-m}-1$ and write $w=2^{n-m}{w}^{\prime }+w_0$. Then $xy=2^m(2^{n-m}{w}^{\prime }+w_0)+1=2^{n}v+2^m{w}_0+1$, where $2^m{w}_0+1<2^n$. Consequently, $xy(\mathrm{mod}{2}^n)=2^{m}v+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(\mathrm{mod}{2}^n)$. By minimality, $s$ divides $2^{n-1}$, as $a^{2^{n-1}}\equiv 1(\mathrm{mod}{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(\mathrm{mod}{2}^n)$. Suppose now, if possible, that $s$ divides $2^{n-\alpha -1}$. Then $a^{2^{n-\alpha -1}}\equiv 1(\mathrm{mod}{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{)}^{ϵ}$, $\gamma =0,1,\dots ,2^{n-2}-1$, $ϵ=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 }^{\prime }$ be its inverse modulo $2^{n-2}$. Then $k={\alpha }^{\prime }\beta /2^m$ makes $\alpha k-\beta$ divisible by $2^{n-2}$, as desired.