British Maths Olympiad 2000 Round 1 Problem 2

My solution to an Olympiad problem.

By Vamshi Jandhyala in mathematics

September 27, 2019

Show that, for every positive integer $n$,

$$ \begin{align} 121^{n}-25^{n}+1900^{n}-(-4)^{n} \end{align} $$

is divisible by $2000$.

Solution

As $a^{n}-b^{n}$ is divisible by $a-b$ for all $n$,

$121^{n}-(-4)^{n}$ is divisible by $121-(-4)=125$.

$1900^{n}-25^{n}$ is divisible by $1900-25=1875$ which is divisible by $125$.

From the above we see that $121^{n}-25^{n}+1900^{n}-(-4)^{n}$ is divisible by $125$.

We also have

$$ \begin{align} 121 &\equiv& 1 \mod 8 &\implies& 121^{n} &\equiv& 1 \mod 8\
25 &\equiv& 1 \mod 8 &\implies& 25^{n} &\equiv& 1 \mod 8 \
1900 &\equiv& 4 \mod 8 &\implies& 1900^{n} &\equiv& 4^{n} \mod 8 \
-4 &\equiv& 4 \mod 8 &\implies& (-4)^{n} &\equiv& 4^{n} \mod 8 \end{align} $$

From the above we see that $121^{n}-25^{n}+1900^{n}-(-4)^{n}$ is divisible by $8$.

As $121^{n}-25^{n}+1900^{n}-(-4)^{n}$ is divisible by $125$ and $8$ which are relatively prime to each other, it is divisible by $125\cdot8=2000$.