6
$\begingroup$

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?

$\endgroup$
2
  • 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, 2018 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, 2018 at 9:09

1 Answer 1

Reset to default
5
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .