Question

Math 老师的幼儿园班级有 $16$ 名注册学生。教室里有非常多的积木，数量为 $N$ ，并满足以下条件：

• 若班上有 $16$ 、 $15$ 或 $14$ 名学生到场，则每一种情况下都能把所有积木平均分给每名学生，并且

• 存在三个整数 $0 \lt x \lt y \lt z \lt 14$ ，使得当 $x$ 、 $y$ 或 $z$ 名学生到场并把积木平均分给每名学生时，都恰好剩下三块积木。

求满足以上条件的最小可能 $N$ 的不同素因数之和。

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.

答案

答案：148

知识点：最小公倍数模运算中国剩余定理

难度评级：2990

解答：

能被 $16$ 、 $15$ 、 $14$ 整除说明 $N = 1680m$ ，其中 $1680 = \operatorname{lcm}(14, 15, 16)$ $= 2^4 \cdot 3 \cdot 5 \cdot 7$ 小于 $14$ 的正整数中，除了 $9$ 、 $11$ 、 $13$ 外都整除 $1680$ ，而 $N$ 的因数分配后余数为 $0$ ，不是 $3$ 。所以必有 $\{x, y, z\} = \{9, 11, 13\}$ ，并且需要 $1680m \equiv 3$ 分别模 $9$ 、 $11$ 、 $13$ 。

因为 $1680 \equiv 6 \pmod 9$ ，第一个同余为 $6m \equiv 3 \pmod 9$ ，即 $m \equiv 2 \pmod 3$ 。因为 $1680 \equiv 8 \pmod{11}$ ，需要 $8m \equiv 3 \pmod{11}$ ，即 $m \equiv 10 \pmod{11}$ 。因为 $1680 \equiv 3 \pmod{13}$ ，需要 $m \equiv 1 \pmod{13}$ 。由中国剩余定理合并得 $m \equiv 131 \pmod{429}$ ，所以最小的 $m$ 是 $131$ 。

因此 $N = 1680 \cdot 131$ $= 2^4 \cdot 3 \cdot 5 \cdot 7 \cdot 131$ ，且 $131$ 是素数，所以不同素因数之和为 $2 + 3 + 5 + 7 + 131 = 148$ 。

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 第 11 题

答案：148

难度评级：2990

解答：

其他年份的第 11 题