Recently, I came across this exercise:

Suppose that $a$ and $b$ are odd numbers. Prove that only for finitely many positive integers $j$ does $2^j$ divide $a^j+b^j$.

I tried to solve it using basic mathematics (i.e. congruences modulo powers of $2$), but I could not prove the statement. Considering that it comes from some high school math competition, I think it should be solvable with very little mathematical background. What am I missing?

  • 3
    $\begingroup$ Hints: If $j$ is even show that $a^j+b^j$ is not divisible by four. If $j$ is odd show that $a^j+b^j=(a+b) K$ where $K$ is odd. $\endgroup$ – Jyrki Lahtonen Oct 9 '18 at 9:08
  • $\begingroup$ If $j$ is even, $a^j+b^j\equiv2\pmod8$ else $a^j\equiv-b^j\pmod{2^j}\iff\left(-\dfrac ab\right)^j\equiv1$ $\endgroup$ – lab bhattacharjee Oct 9 '18 at 9:09

Suppose $j=2k$. Since $a,b$ are odd, $a^2,b^2$ and thus $a^{2k},b^{2k}$ are 1 modulo 4, so $a^j+b^j\equiv2\bmod4$. Thus $4\nmid a^j+b^j$, and in particular $2^j\nmid a^j+b^j$.

Now suppose $j$ is odd. Algebraically $$a^j+b^j=(a+b)(a^{j-1}-ba^{j-2}+\dots+b^{j-1})$$ The right factor has an odd number of terms, each of which is an odd number (due to $a,b$ being odd), so it is odd. Thus for $2^j$ to divide $a^j+b^j$ it must divide $a+b$. For any fixed $a,b$, since $2^j$ is an increasing function, there are only finitely $j$ for which $2^j<a+b$, i.e. $2^j$ has a chance to divide $a+b$, thus $a^j+b^j$.

In summary, for any $a,b$ there are only finitely many $j$ with $2^j\mid a^j+b^j$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.