2013 AIME I Problem 11

Question

Ms. Math’s kindergarten class has

16

registered students. The classroom has a very large number,

N,

of play blocks which satisfies the conditions:

• If

16,

15,

or

14

students are present in the class, then in each case all the blocks can be distributed in equal numbers to each student, and

• There are three integers

0 \lt x \lt y \lt z \lt 14

such that when

x,

y,

or

z

students are present and the blocks are distributed in equal numbers to each student, there are exactly three blocks left over.

Find the sum of the distinct prime divisors of the least possible value of

N

satisfying the above conditions.

Answer

Answer: 148

Concepts:least common multiple modular arithmetic Chinese Remainder Theorem

Difficulty rating: 2990

Small hint:

N

is a multiple of

\operatorname{lcm}(14, 15, 16) = 1680,

and every positive integer below

14

except

9,

11,

and

13

divides

1680

Big hint:

So

x,

y,

and

z

must be

9,

11,

and

13:

solve

1680m \equiv 3

modulo

9,

11,

and

13

by the Chinese remainder theorem

Solution:

Divisibility by

16,

15,

and

14

means

N = 1680m

where

1680 = \operatorname{lcm}(14, 15, 16)

= 2^4 \cdot 3 \cdot 5 \cdot 7.

Every positive integer less than

14

divides

1680

except

9,

11,

and

13,

and a divisor of

N

leaves remainder

0,

not

3.

So necessarily

\{x, y, z\} = \{9, 11, 13\},

and we need

1680m \equiv 3

modulo each of

9,

11,

13.

Since

1680 \equiv 6 \pmod 9,

the first congruence is

6m \equiv 3 \pmod 9,

i.e.

m \equiv 2 \pmod 3.

Since

1680 \equiv 8 \pmod{11},

we need

8m \equiv 3 \pmod{11},

i.e.

m \equiv 10 \pmod{11}.

Since

1680 \equiv 3 \pmod{13},

we need

m \equiv 1 \pmod{13}.

By the Chinese remainder theorem these combine to

m \equiv 131 \pmod{429},

so the least

m

is

131.

Then

N = 1680 \cdot 131

= 2^4 \cdot 3 \cdot 5 \cdot 7 \cdot 131,

and since

131

is prime, the sum of the distinct prime divisors is

2 + 3 + 5 + 7 + 131 = 148.

2013 AIME I Problem 11

Answer: 148

Difficulty rating: 2990

Small hint:

Big hint:

Solution:

Problem 11 in other years