Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

6 Answers 6

up vote 7 down vote accepted

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer
1  
good job up there! (+1) –  Chris's sis 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}\;.$$

share|improve this answer
    
An unexplained downvote is distinctly unhelpful. –  Brian M. Scott Oct 31 '12 at 1:24

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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