Problem 1046

54. We will solve the generalized problem. Given a natural number $n$ and two odd natural numbers $a$ and $b$. Prove that there exists a natural number $k$ such that at least one of the numbers $b^{2 k}-a^{2}$ and $a^{2 k}-b^{2}$ is divisible by $2^{n}$.

We will use the following known statement: if the number $c-1$ gives a remainder of $2^{k}$ when divided by $2^{k+1}$, where $k \geqslant 2$, then $c^{2}-1$ gives a remainder of $2^{k+1}$ when divided by $2^{k+2}$.

Let $a^{2}-1$ be divisible by $2^{\alpha}$ and not divisible by $2^{\alpha+1}$, and let $b^{2}-1$ be divisible by $2^{\beta}$ and not divisible by $2^{\beta+1}$. Clearly, in this case, $\alpha, \beta \geqslant 2$. Then $a^{2}-1$ gives a remainder of $2^{\alpha}$ when divided by $2^{\alpha+1}$, and $b^{2}-1$ gives a remainder of $2^{\beta}$ when divided by $2^{\beta+1}$. Let $\alpha \leqslant \beta$, and for brevity, let $2^{\beta-\alpha}=m$. By the lemma, the number

$$a^{2 m}-1=((\left(a^{2}\right)^{2} \overbrace{}^{\cdots})^{2}-1$$

gives a remainder of $2^{\beta}$ when divided by $2^{\beta+1}$.

We will solve the problem by induction on $n$. If $n \leqslant \beta+1$, then $k=m$ will work, since $a^{2 m}$ and $b^{2}$ give the same remainder when divided by $2^{\beta}$. We will make the transition from $n$ to $n+1$. By the induction hypothesis, for some $k$ the number $a^{2 k}-b^{2}$ is divisible by $2^{n}$. If it is also divisible by $2^{n+1}$, then the transition is made. Otherwise, it gives a remainder of $2^{n}$ when divided by $2^{n+1}$. Let $r=2^{n-\beta}+1$. Then by the lemma, $b^{2(r-1)}-1$ gives a remainder of $2^{n}$ when divided by $2^{n+1}$. Therefore, $b^{2 r}-b^{2}$ gives a remainder of $2^{n}$ when divided by $2^{n+1}$. We will use the difference of powers formula:

$$a^{2 k r}-b^{2 r}=\left(a^{2 k}-b^{2}\right)\left(a^{2 k(r-1)}+a^{2 k(r-2)} b^{2}+a^{2 k(r-3)} b^{4}+\ldots+b^{2(r-1)}\right)$$

The first parenthesis gives a remainder of $2^{n}$ when divided by $2^{n+1}$, and the second consists of $r$ odd terms and, therefore, is odd. Thus, the difference $a^{2 k r}-b^{2 r}$ gives a remainder of $2^{n}$ when divided by $2^{n+1}$. But then $a^{2 k r}-b^{2}=\left(a^{2 k r}-b^{2 r}\right)-\left(b^{2 r}-b^{2}\right)$ is divisible by $2^{n+1}$, since the expressions in parentheses give the same remainder when divided by $2^{n+1}$.