The problem is strongly connected with the structure of the multiplicative group $\left(\mathbb{Z}/2^n\mathbb{Z} \right)^{\times}$ of odd residues modulo $2^n$. This group is isomorphic to $C_2\times C_{2^{n-2}}$ for $n\ge 3$. That's why, we cannot claim $ a^mb-1$ or $b^ma-1$ is multiple of $2^n$ but must raise slightly the power of $a$ , resp. $b$. For more details see here. Most probably, the problem was proposed by Titu Andreescu. The claim can be generalized. For any prime $p>2$ and $a,b$ not multiple of $p$, and any $n\in \mathbb{N} $ there exists $m\in\mathbb{N}$ such that either $a^mb^{p-1}-1$ or $b^ma^{p-1}-1$ is multiple of $p^n$.

Let WLOG $\nu_{2}(a^2-1)\geq\nu_2(b^2-1)$. We shall prove that $\nu_2 (a^{2}b^{m}-1)$ is unbounded which is essentially the problem statement. Let FSOC $\nu_2(a^{2}b^{m}-1)$ be bounded. Then $\exists$ $m_0$ s.t. $\nu_2(a^{2}b^{m_0}-1)$ is maximum and let the maximum be $M$. Claim : $M\geq\nu_2(a^2-1)$. Proof: Choose $m=2^{\nu_2(a^2-1)}$. Then we have $b^m-1$ is divisible by $2^{\nu_2(a^2-1)}$. Hence we have that $M\geq\nu_2(a^2b^m-1)=\nu_2((a^2-1)+(a^2(b^m-1)))\geq \nu_2(a^2-1)$. This proves our claim. Now we look at $m=m_0 + 2^{M-\nu_2(b^2-1)+1}$. Here note that $M-\nu_2(b^2-1)+1$ is positive integer by claim and $\nu_2(a^2-1)\geq\nu_2(b^2-1)$. Then $a^2b^m-1=(a^2b^{m_0}-1)+(a^2b^{m_0}(b^{2^{M-\nu_2(b^2-1)+1}}-1)$. Also note that $\nu_2(a^2b^{m_0}(b^{2^{M-\nu_2(b^2-1)+1}}-1)=\nu_2((b^{2^{M-\nu_2(b^2-1)+1}}-1)$ $=\nu_2(b^2-1)+\nu_2(2^{M-\nu_2(b^2-1)})=\nu_2(b^2-1)+M-\nu_2(b^2-1)=M$. Hence we obtain that $M=\nu_2(a^2b^{m_0}(b^{2^{M-\nu_2(b^2-1)+1}}-1)=\nu_2(a^2b^{m_0}-1)$ and hence $\nu_2(a^2b^m-1)>M$ which is a contradiction. Thus $\nu_2(a^2b^m-1)$ is unbounded as desired. Q.E.D.

dgrozev wrote: For any prime $p>2$ and $a,b$ not multiple of $p$, and any $n\in \mathbb{N} $ there exists $m\in\mathbb{N}$ such that either $a^mb^{p-1}-1$ or $b^ma^{p-1}-1$ is multiple of $p^n$. Define $\mathcal{M}:\stackrel{\text{def}}{=} \frac{1}{b^2} \pmod {p^n}$ Claim:- There exists $m \in \mathbb{Z}_{p^n}$ such that $$a^m \equiv \mathcal{M} \pmod {p^n}$$Proof:- We prove a stronger result i.e $$a^m \equiv \text{ any number not divisible by p } \pmod {p^n}$$where $m \in \mathbb{Z}_{p^n}$ Let $g$ be a primitive root modulo $p^n$,rewrite the condition as $$g^{\alpha_1 m} \equiv \text{ any number not divisible by p } \pmod {p^n}$$where $m \in \mathbb{Z}_{p^n}$ and $g^{\alpha_1} \equiv a \pmod {p^n}$ If $\gcd(\alpha_1,\phi(p^n))=d_1>1,\gcd(\alpha_2,\phi(p^n))=d_2>1$ then we choose $m$ such that $p-1|2\alpha_1+m \alpha_2$,and so assume that $\gcd(\alpha_1,\phi(p^n))=1$ Since $\gcd(\alpha_1,\phi(p^n))=1$,the result follows. The result follows by choosing $m$ such that $$a^m \equiv \mathcal{M} \pmod {p^n}$$