3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – André Nicolas Oct 30 '12 at 22:22
8
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ good job up there! (+1) $\endgroup$ – user 1357113 Nov 1 '12 at 18:59
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ An unexplained downvote is distinctly unhelpful. $\endgroup$ – Brian M. Scott Oct 31 '12 at 1:24
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.