Show that $121^{n}-25^{n}+1900^{n}-(-4)^{n}$ is divisible by 2000.

Factor $2000 = 2^5 \cdot 5^3$

then split $$121^{n}-25^{n}+1900^{n}-(-4)^{n}$$ into

• $$9^{n}-9^{n}+12^{n}-12^{n} \equiv 0 \pmod {2^4}$$

• $$121^{n}-25^{n}+25^{n}-121^{n} \equiv 0 \pmod {5^3}$$

using Chinese remainder theorem.

Prove that $16$ and $125$ divide it making use of the fact that $(a-b)$ divides $a^n - b^n$.

$16$ divides $121^{n}-25^{n}+1900^{n}-(-4)^{n}$:

$(121-25) \vert (121^n - 25^n) \implies 96 \vert (121^n - 25^n) \implies 16 \vert (121^n - 25^n)$

$(1900-(-4)) \vert (1900^n - (-4)^n) \implies 1904 \vert (1900^n - (-4)^n) \implies 16 \vert (1900^n - (-4)^n)$

$125$ divides $121^{n}-25^{n}+1900^{n}-(-4)^{n}$:

$(121-(-4)) \vert (121^n - (-4)^n) \implies 125 \vert (121^n - (-4)^n)$

$(1900-25) \vert (1900^n - 25^n) \implies 1875 \vert (1900^n - 25^n) \implies 125 \vert (1900^n - 25^n)$

It’s easy to verify the statement for $n=0$ and $n=1$. If $n\ge 2$, $1900^n$ is divisible by $2000$, so the problem is really to show that $2000\mid 121^n-25^n-(-4)^n$ for $n\ge 2$.

Now $2000=2^4\cdot5^3$, and $2^4$ and $5^3$ are relatively prime, so for any integer $n$, $2000\mid n$ iff $2^4\mid n$ and $5^3\mid n$.

• Clearly $2^4\mid(-4)^n$ for $n\ge 2$, so $2^4\mid 121^n-25^n-(-4)^n$ iff $2^4\mid 121^n-25^n$.

• Similarly, $5^3\mid 25^n$ for $n\ge 2$, so $5^3\mid 121^n-25^n-(-4)^n$ iff $5^3\mid 121^n-(-4)^n$ for $n\ge 2$.

Thus, it suffices to show that $2^4\mid 121^n-25^n$ and $5^3\mid 121^n-(-4)^n$ for $n\ge 2$.

But these are easy: just use the familiar identity $$a^n-b^n=(a-b)\sum_{k=0}^{n-1}a^kb^{n-1-k}\;.$$