# Parity of sum of powers of odd numbers

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?

• 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. – Jyrki Lahtonen Oct 9 '18 at 9:08
• 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$ – 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, 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$$.