# Find the largest integer n, where 2009^n divides (2008^2009^2010 + 2010^2009 ^2008)

• November 17th 2010, 05:28 PM
elemental
Find the largest integer n, where 2009^n divides (2008^2009^2010 + 2010^2009 ^2008)
Find the largest integer n, where 2009^n divides (2008^(2009^2010) + 2010^(2009 ^2008))

So, the only observation I've made is that you can rewrite this in the form:

(x-1)^(x^(x+1)) + (x+1)^(x^(x-1))

I also know that I have to use the binomial theorem, but I'm not exactly sure how that relates to finding the largest n possible...

Help?
• November 17th 2010, 08:37 PM
aman_cc
In this case x = 2009 is odd.

Had x been even life would have been simpler !

I have not tried this completely but would go down this route first - hope it works
• November 17th 2010, 08:49 PM
Chris L T521
Quote:

Originally Posted by elemental
Find the largest integer n, where 2009^n divides (2008^(2009^2010) + 2010^(2009 ^2008))

So, the only observation I've made is that you can rewrite this in the form:

(x-1)^(x^(x+1)) + (x+1)^(x^(x-1))

I also know that I have to use the binomial theorem, but I'm not exactly sure how that relates to finding the largest n possible...

Help?

From how this question is posed, I have the feeling that this is from an official math olympiad contest of some kind (due to the fact that the numerical values for years appear throughout the problem and it is something that pops up in olympiad questions from time to time).

If you can justify this isn't from an olympiad of some kind, please message me and I'll consider reopening this thread.

EDIT: The user has informed me that this comes from an olympiad competition that took place in 2008. As a result, feel free to make contributions to this thread.
• November 19th 2010, 12:11 PM
Opalg
By looking at the powers of n that occur in the binomial coefficients $n^{n-1}\choose k$, you should be able to see that

$(1+n)^{n^{n-1}} = 1 + n^n + (\text{multiples of }n^{n+1}).$

In the same way, if n is odd then

$(-1+n)^{n^{n+1}} = -1 + (\text{multiples of }n^{n+1}).$

Therefore $(n-1)^{n^{n+1}} + (n+1)^{n^{n-1}}$ is a multiple of $n^n$, but not a multiple of $n^{n+1}.$

So the highest power of 2009 that divides $2008^{2009^{2010}}\!\! + 2010^{2009^{2008}}$ is $2009^{2009}$.