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

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

Solution:

Problem 11 in Other Years