Question

已知对所有正整数

k

，

\begin{aligned} &1^2 + 2^2 + 3^2 + \cdots + k^2 \\ &= \frac{k(k+1)(2k+1)}{6} \end{aligned}\text{。}

求最小的正整数

k

，使得

1^2 + 2^2 + 3^2 + \cdots + k^2

是

200

的倍数。

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.

答案

答案：112

知识点：前n项平方和中国剩余定理分类讨论

难度评级：2500

小提示：

需要

k(k+1)(2k+1)

是

1200 = 2^4 \cdot 3 \cdot 5^2

的倍数，其中因子

3

自动满足。

You need

k(k+1)(2k+1)

to be a multiple of

1200 = 2^4 \cdot 3 \cdot 5^2,

and the factor

3

comes for free

大提示：

2k+1

是奇数，所以

16

必须整除

k

或

k+1

；另外

25

必须整除

k

、

k+1

，或

2k+1

。比较合并同余后的最小解。

2k+1

is odd, so

16

must divide

k

or

k+1;

separately

25

must divide

k,

k+1,

or

2k+1.

Compare the smallest solutions of the combined congruences.

解答：

该平方和是

200

的倍数，当且仅当

k(k+1)(2k+1)

是

1200 = 2^4 \cdot 3 \cdot 5^2

的倍数。因子

3

总会整除

k(k+1)(2k+1)

（若

k \equiv 1 \pmod 3

，则

2k+1

能被

3

整除），所以只需考虑

2^4

和

5^2

。

由于

2k+1

是奇数，且

k

、

k+1

不可能都为偶数，

16

必须整除

k

或

k+1

，所以

k \equiv 0

或

15 \pmod{16}

。类似地，

25

必须整除

k

、

k+1

、

2k+1

中的一个，得到

k \equiv 0

、

24

或

12 \pmod{25}

。将每一对同余条件合并到模

400

，所得最小正解依次为

112

、

175

、

224

、

287

、

399

和

400

。

最小的是

k = 112

：确实，

112 \cdot 113 \cdot 225

= (16 \cdot 7) \cdot 113 \cdot (9 \cdot 25)

是

1200

的倍数。

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

2k+1

is divisible by

3

), 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 第 7 题

答案：112

难度评级：2500

小提示：

大提示：

解答：

其他年份的第 7 题