2013 AMC 12B Problem 23

Problem 23 of 25HarderNumber Theory

Bernardo chooses a three-digit positive integer

N

and writes both its base-

5

and base-

6

representations on a blackboard. Later LeRoy sees the two numbers Bernardo has written. Treating the two numbers as base-

10

integers, he adds them to obtain an integer

S.

For example, if

N = 749,

Bernardo writes the numbers

10{,}444

and

3{,}245,

and LeRoy obtains the sum

S = 13{,}689.

For how many choices of

N

are the two rightmost digits of

S,

in order, the same as those of

2N?

Show solution

Solution

Because

\mathrm{lcm}(25, 36, 100) = 900,

the condition on

N

depends only on

N \bmod 900,

so consider

0 \le N \le 899.

Let the last two base-

5

digits be

a_1, a_0

and the last two base-

6

digits be

b_1,b_0.

Modulo

10,

the desired equality and

N\equiv a_0\pmod5

force

a_0=b_0.

The Chinese Remainder Theorem applied modulo

25

and

36

then gives

\begin{aligned} N&\equiv180a_1+150b_1 \\ &\quad {}+a_0\pmod{900}. \end{aligned}

Comparing twice this residue modulo

100

with the decimal number

10(a_1+b_1)+a_0+b_0

reduces to

5a_1\equiv b_1\pmod{10}.

Hence the valid pairs are exactly

(0,0),(2,0),(4,0),(1,5),(3,5).

Each combines with

5

choices of

a_0

(0 \le a_0 \le 4),

giving

25

values of

N.

Thus, the correct answer is E.