Track / Stage 5 / 311 of 400 #911 of 2000

Problem 911

AIME late

Number theory Difficulty 5.8 Prove it

$8 \cdot 6$ Write down the 1976 natural numbers $1, 2, \cdots, 1976$ in any order in a row, and prove that the resulting number is not a perfect square.
(Kyiv Mathematical Olympiad, 1976)

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

[Proof] Calculate the sum of these 1976 natural numbers
$\begin{aligned} 1+2+\cdots+1976 & =\frac{1976 \cdot 1977}{2} \\ & =988 \cdot 1977 \\ & =(9 \cdot 109+7)(9 \cdot 219+6) \\ & \equiv 6(\bmod 9) . \end{aligned}$

Thus, the number formed by these 1976 natural numbers leaves a remainder of 6 when divided by 9.
Since when $m=9 k, 9 k \pm 1,9 k \pm 2,9 k \pm 3,9 k \pm 4$ ,
$m^{2} \equiv 0,1,4,7 \quad(\bmod 9) \text {. }$

Therefore, the resulting number is not a perfect square.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.