Show that $121^{n}-25^{n}+1900^{n}-(-4)^{n}$ is divisible by 2000. My question comes from the British Mathematical Olympiad (Round 1) paper from 2000:
Show that $121^{n}-25^{n}+1900^{n}-(-4)^{n}$ is divisible by 2000 for any natural $n$.
My immediate idea was to write $121^{n}-25^{n}=(11^{n}
+5^{n})(11^{n}-5^{n})$ but this doesn't seem to help.
My next idea was to use induction; the base case is easy but I can't see how the $k^{th}$ case would imply the $(k+1)^{th}$. Any help would be appreciated.
 A: 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)$
A: 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}\;.$$
A: 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.
A: It's special case $\rm\ j=16,\ k = 125,\,\ a,b,c,d = 121,25,1900,-4,\:$ and $\rm\:f(x) = x^n\ $ of the following
Theorem $\rm\ \ \ \begin{eqnarray}\rm j\mid a\!-\!b,\\ \rm j\mid c\!-\!d,\end{eqnarray}$
$ \begin{eqnarray}\:\rm k\mid a\!-\!d\\ \rm k\mid b\!-\!c\end{eqnarray}\, \ \Rightarrow\,\rm\ lcm(j,k)\mid f(a)-f(b)+f(c)-f(d),\ $ for $\rm\ f(x)\in \Bbb Z[x]$ 
$\rm{\bf Proof}\,\ \  mod\,\ j\!:\ $ $\rm\ \ \begin{eqnarray}\color{#C00}a&\equiv&\rm \color{#0A0}b\\ \rm \color{#88f}c&\equiv&\rm \color{brown}d\end{eqnarray}$ $\ \ \Rightarrow\ \ $ $\begin{eqnarray}&&\rm f(\color{#C00}a)-\,f(b)+f(\color{#88f}c)-f(d)\\ \equiv\: &&\rm f(\color{#0A0}b)-f(b) + f(\color{brown}d)-f(d)\,\equiv\, 0\end{eqnarray} $
where we used that  $\ \rm \color{#C00}a\equiv\rm \color{#0A0}b\,\Rightarrow\ f(\color{#C00}a)\equiv f(\color{#0A0}b)\,$ etc  by the Polynomial Congruence rule.
Similarly it's $\rm\,\equiv\, 0\pmod{\! k}.\:$ So, being a multiple of $\rm\:j,k\:$ it's a multiple of $\rm\:lcm(j,k).\ \ $ QED
Remark $ $ See also here and its links for generalizations highlighting the innate symmetry.
A: $2000=125\cdot 16$
$1900\equiv 25\pmod {125}$ as $15\cdot125=1875$
$121^n-25^n+1900^n-(-4)^n\equiv (-4)^n-25^n+25^n-(-4)^n\pmod {125}\equiv0$
$121\equiv 9\pmod{16},25\equiv 9\pmod{16}, 1900\equiv -4\pmod{16}$ as $1904=119\cdot 16$
$121^n-25^n+1900^n-(-4)^n\equiv 9^n-9^n+(-4)^n-(-4)^n\pmod{16}\equiv 0$
So, $lcm(125,16)\mid 121^n-25^n+1900^n-(-4)^n$
Now $lcm(125,16)=125\cdot 16=2000$
A: Just to give a different approach, using binomial expansions and the fact that $2000=16\cdot125$, note that for $n\ge2$ we have
$$121^n=(125-4)^n\equiv125^n-4\cdot125^{n-1}n+(-4)^n\mod2000$$
$$25^n=(125-100)^n\equiv125^n-100\cdot125^{n-1}n\mod2000$$
and
$$1900^n\equiv0\mod2000$$
and thus
$$\begin{align}
121^n-25^n+1900^n-(-4)^n
&=(125-4)^n-(125-100)^n+1900^n-(-4)^n\\
&\equiv(125^n-4\cdot125^{n-1}n+(-4)^n)-(125^n-100\cdot125^{n-1}n)+0-(-4)^n\\
&=96\cdot125^{n-1}n\\
&=2000\cdot6\cdot125^{n-2}n\\
&\equiv0\mod 2000
\end{align}$$
The remaining cases, $n=0$ and $n=1$, are dispatched directly:
$$121^0-25^0+1900^0-(-4)^0=1-1+1-1=0$$
and
$$121^1-25^1+1900^1-(-4)^1=121-25+1900+4=2000$$
A: Do it by induction. Does it work for $n = 1$? Assume it works for some $n = k$ and show it holds for $n = k + 1$.
