Question

It is known that, for all positive integers $k,$ $\begin{aligned} &1^2 + 2^2 + 3^2 + \cdots + k^2 \\ &= \frac{k(k+1)(2k+1)}{6}. \end{aligned}$ Find the smallest positive integer $k$ such that $1^2 + 2^2 + 3^2 + \cdots + k^2$ is a multiple of $200.$

Answer

Answer: 112

Concepts:sum of first n squares Chinese Remainder Theorem casework

Difficulty rating: 2500

Solution:

The sum is a multiple of $200$ exactly when $k(k+1)(2k+1)$ is a multiple of $1200 = 2^4 \cdot 3 \cdot 5^2.$ The factor $3$ always divides $k(k+1)(2k+1)$ (if $k \equiv 1 \pmod 3,$ then $3 \mid 2k+1$ ), so only $2^4$ and $5^2$ matter.

Since $2k+1$ is odd and $k,$ $k+1$ cannot both be even, $16$ must divide $k$ or $k+1,$ so $k \equiv 0$ or $15 \pmod{16}.$ Similarly $25$ must divide one of $k,$ $k+1,$ $2k+1,$ giving $k \equiv 0,$ $24,$ or $12 \pmod{25}.$ Combining each pair of congruences modulo $400,$ the smallest positive solutions are $112,$ $175,$ $224,$ $287,$ $399,$ and $400.$

The least is $k = 112:$ indeed $112 \cdot 113 \cdot 225$ $= (16 \cdot 7) \cdot 113 \cdot (9 \cdot 25)$ is a multiple of $1200.$

2002 AIME II Problem 7

Answer: 112

Difficulty rating: 2500

Solution:

Problem 7 in Other Years