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?
Best Answer
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$.