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

-
The $1900$ is just for the beginning. Want $125$ to divide our number, trivial since $121\equiv -4 \pmod{125}$. Want $16$ to divide our number, easy since $16$ divides $121-25$. – André Nicolas Oct 30 '12 at 22:22

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

-

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.

-
good job up there! (+1) – user 1618033 Nov 1 '12 at 18:59

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}\;.$$

-
An unexplained downvote is distinctly unhelpful. – Brian M. Scott Oct 31 '12 at 1:24

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

-

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\quad\ \ \begin{eqnarray}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}$

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

-

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

-