2013 AIME I Problem 11

Below is the professionally curated solution for Problem 11 of the 2013 AIME I, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2013 AIME I solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:least common multiplemodular arithmeticChinese Remainder Theorem

Difficulty rating: 2990

11.

Ms. Math's kindergarten class has 1616 registered students. The classroom has a very large number, N,N, of play blocks which satisfies the conditions:

• If 16,16, 15,15, or 1414 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<x<y<z<140 \lt x \lt y \lt z \lt 14 such that when x,x, y,y, or zz 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 NN satisfying the above conditions.

Solution:

Divisibility by 16,16, 15,15, and 1414 means N=1680mN = 1680m where 1680=lcm(14,15,16)=24357.1680 = \operatorname{lcm}(14, 15, 16) = 2^4 \cdot 3 \cdot 5 \cdot 7. Every positive integer less than 1414 divides 16801680 except 9,9, 11,11, and 13,13, and a divisor of NN leaves remainder 0,0, not 3.3. So necessarily {x,y,z}={9,11,13},\{x, y, z\} = \{9, 11, 13\}, and we need 1680m31680m \equiv 3 modulo each of 9,9, 11,11, 13.13.

Since 16806(mod9),1680 \equiv 6 \pmod 9, the first congruence is 6m3(mod9),6m \equiv 3 \pmod 9, i.e. m2(mod3).m \equiv 2 \pmod 3. Since 16808(mod11),1680 \equiv 8 \pmod{11}, we need 8m3(mod11),8m \equiv 3 \pmod{11}, i.e. m10(mod11).m \equiv 10 \pmod{11}. Since 16803(mod13),1680 \equiv 3 \pmod{13}, we need m1(mod13).m \equiv 1 \pmod{13}. By the Chinese remainder theorem these combine to m131(mod429),m \equiv 131 \pmod{429}, so the least mm is 131.131.

Then N=1680131=24357131,N = 1680 \cdot 131 = 2^4 \cdot 3 \cdot 5 \cdot 7 \cdot 131, and since 131131 is prime, the sum of the distinct prime divisors is 2+3+5+7+131=148.2 + 3 + 5 + 7 + 131 = 148.

← Problem 10Full ExamProblem 12

Problem 11 in Other Years