67th NMO Selection Tests for BMO and IMO

Proceed by induction on $k$. Since $a\equiv 3(\mathrm{mod}8)$, $m=1$ works for $k=1,2,3$, so let $k\ge 3$ and let $m$ be a positive integer such that $a^m+a+2$ is divisible by $2^k$.

If $(a^m+a+2)/2^k$ is even, then $a^m+a+2$ is clearly divisible by $2^{k+1}$. If $(a^m+a+2)/2^k$ is odd, we will show that $a^{m+2^{k-2}}+a+2$ is divisible by $2^{k+1}$. To this end, write $a^{m+2^{k-2}}+a+2=a^{2^{k-2}}(a^m+a+2)-(a+2)(a^{2^{k-2}}-1)$. The first term is an odd multiple of $2^k$, and it is sufficient to prove that so is the second. Induct on $k\ge 3$ to show that $a^{2^{k-2}}-1$ is an odd multiple of $2^k$. Since $a\equiv 3(\mathrm{mod}8)$, this is clearly the case if $k=3$, and the induction step follows from the identity $a^{2^{k-1}}-1=(a^{2^{k-2}}-1)(a^{2^{k-2}}+1)=(a^{2^{k-2}}-1)((a^{2^{k-2}}-1)+2)$. This completes the proof.