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.
Show that $121^{n}-25^{n}+1900^{n}-(-4)^{n}$ is divisible by 2000.
-
0The $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$. β 2012-10-30
6 Answers
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$.
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.
-
1good job up there! (+1) β 2012-11-01
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}\;.$
-
0An unexplained downvote is distinctly unhelpful. β 2012-10-31
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} $
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.
$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$