2011 AIME I Problem 7

Question

Find the number of positive integers

m

for which there exist nonnegative integers

x_0,

x_1,

\ldots,

x_{2011},

such that

m^{x_0} = \sum_{k=1}^{2011} m^{x_k}.

Answer

Answer: 16

Concepts:modular arithmetic factor counting

Difficulty rating: 2710

Small hint:

Reduce both sides mod

m - 1:

every power of

m

is congruent to

1

Big hint:

So

m - 1

must divide

2010.

Conversely, expand

m^n

by repeatedly splitting one power into

m

copies of the next-lower power; each split adds

m - 1

terms.

Solution:

The value

m = 1

fails, since the right side would be

2011

while the left side is

1.

For

m \ge 2,

reduce mod

m - 1:

every power of

m

is

\equiv 1,

so the equation forces

1 \equiv 2011 \pmod{m - 1},

that is,

m - 1

divides

2010.

Conversely, suppose

2010 = (m - 1)n.

Take

x_0 = n,

let

m

of the

x_k

equal

0,

and for each

r = 1, 2, \ldots, n - 1

let

m - 1

of the

x_k

equal

r.

This uses

m + (m - 1)(n - 1)

= n(m - 1) + 1

= 2011

terms, and the sum telescopes:

\begin{aligned} &m \\ &\quad {}+ (m - 1) \\ &\quad {}\cdot (m + m^2 + \cdots + m^{n-1}) \\ &\quad {}= m + (m^n - m) \\ &\quad {}= m^n = m^{x_0}. \end{aligned}

So the equation is solvable exactly when

m - 1

divides

2010 = 2 \cdot 3 \cdot 5 \cdot 67,

which has

2^4 = 16

divisors. There are

16

such

m.