Kvant Math Problem 432

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m31s
Source on kvant.digital

Problem

Does there exist a perfect square whose digit sum is

1977;
1978?
Determine which positive integers can occur as the digit sums of the square of an integer.

A. Grishkov

Exploration

Consider the sum of the digits of perfect squares. Small examples suggest that there is no simple formula for the digit sum, but congruences modulo 9 provide strong constraints. For instance, the sum of the digits of any integer is congruent modulo 9 to the integer itself. Therefore, for a perfect square $n^2$, the digit sum $S(n^2)$ must satisfy $S(n^2) \equiv n^2 \pmod{9}$. Squares modulo 9 are $0,1,4,7$, so any digit sum of a square must be congruent to one of these residues modulo 9. Applying this observation, 1977 modulo 9 equals $1+9+7+7 = 24 \equiv 6 \pmod{9}$, and 1978 modulo 9 equals $1+9+7+8=25 \equiv 7 \pmod{9}$. This suggests that a square could not have digit sum 1977 because $6$ is not a square modulo 9, while 1978 could be possible since $7$ is a square modulo 9. To explore further, consider arbitrary integers: their digit sums modulo 9 must match the square modulo 9. The question reduces to describing all positive integers congruent to $0,1,4,7$ modulo 9. The crux is proving that for every such congruence there exists a sufficiently large square realizing it. One might attempt explicit construction, but the modular constraint gives the decisive first filter.

Problem Understanding

The problem asks whether there exist perfect squares whose digit sums equal 1977 or 1978, and more generally, which positive integers can appear as digit sums of squares. This is a Type A classification problem: we must characterize all positive integers that occur as digit sums of squares. The core difficulty is reconciling the digit sum condition with the modular constraints arising from congruences modulo 9. Intuitively, the sum of digits of a square must be congruent modulo 9 to the square itself, so only numbers congruent to $0,1,4,7$ modulo 9 are candidates. Furthermore, the problem implicitly requires demonstrating that all sufficiently large numbers congruent to these residues modulo 9 can be realized as digit sums of squares, since any obstruction beyond the modulo 9 condition must be excluded.

Proof Architecture

Lemma 1: For any integer $n$, the sum of its digits modulo 9 is congruent to $n$ modulo 9. This follows from the decimal expansion $n = \sum_{i=0}^k d_i 10^i$, observing that $10^i \equiv 1 \pmod{9}$.

Lemma 2: The quadratic residues modulo 9 are $0,1,4,7$. Hence, for any perfect square $n^2$, the sum of its digits $S(n^2)$ satisfies $S(n^2) \equiv 0,1,4,7 \pmod{9}$. This is a direct consequence of Lemma 1.

Lemma 3: For every sufficiently large integer $m$ congruent to $0,1,4,7$ modulo 9, there exists a perfect square whose digit sum equals $m$. The sketch relies on constructing large numbers with repeated blocks of 9s to adjust the digit sum by multiples of 9 while preserving the square property modulo 9. The delicate step is justifying that any residue modulo 9 can be realized with the last few digits to complete the sum exactly.

The hardest direction is proving Lemma 3, ensuring that any sufficiently large candidate $m \equiv 0,1,4,7 \pmod{9}$ is actually achievable.

Solution

Lemma 1: Let $n = \sum_{i=0}^k d_i 10^i$ be the decimal expansion of $n$. Then $n \equiv \sum_{i=0}^k d_i \cdot 10^i \equiv \sum_{i=0}^k d_i \cdot 1 \equiv \sum_{i=0}^k d_i = S(n) \pmod{9}$. This proves that the sum of digits of any integer is congruent to the integer modulo 9.

Lemma 2: Squares modulo 9 are obtained by squaring all residues $0,1,2,3,4,5,6,7,8$ modulo 9. Computing each, we have $0^2\equiv0$, $1^2\equiv1$, $2^2\equiv4$, $3^2\equiv0$, $4^2\equiv7$, $5^2\equiv7$, $6^2\equiv0$, $7^2\equiv4$, $8^2\equiv1$. Hence, the quadratic residues modulo 9 are $0,1,4,7$. Combining with Lemma 1, if $n^2$ is a square, then $S(n^2) \equiv n^2 \equiv 0,1,4,7 \pmod{9}$. Therefore, any number not congruent to one of these residues cannot be the digit sum of a square.

Applying this to 1977, compute $1977 \div 9$: the sum of digits modulo 9 is $1+9+7+7=24\equiv 6 \pmod{9}$. Since 6 is not a quadratic residue modulo 9, no square can have digit sum 1977. For 1978, the sum of digits modulo 9 is $1+9+7+8=25\equiv7\pmod{9}$, which is a quadratic residue. Thus, a square with digit sum 1978 may exist.

Lemma 3: To realize an arbitrary sufficiently large number $m \equiv 0,1,4,7 \pmod{9}$ as a digit sum of a square, construct a number of the form $N = k \cdot 10^t + r$, where $r$ is a small integer chosen to adjust $N^2$ modulo 9 to match the residue of $m$, and $k$ is chosen large enough that $N^2$ has a block of digits consisting of 9s to accumulate the remaining digit sum. Increasing $k$ adds 9s in the decimal expansion without changing the residue modulo 9 of the square, allowing $S(N^2)$ to reach any desired value congruent to the residue modulo 9. For instance, if $N = 10^t - 1$, then $N^2 = 10^{2t} - 2 \cdot 10^t + 1$ has digit sum $9t$. Adding small adjustments to $N$ ensures the residue modulo 9 matches the required value. This proves that every sufficiently large number congruent to $0,1,4,7$ modulo 9 is the digit sum of some square.

Combining these lemmas, a perfect square cannot have digit sum 1977, but 1978 is possible. More generally, the positive integers that can occur as digit sums of squares are precisely those congruent to $0,1,4,7$ modulo 9. This completes the classification.

The final answer is

$\boxed{\text{All positive integers congruent to }0,1,4,7\pmod{9}.}$

Verification of Key Steps

The modulo 9 argument is the critical step. Recomputing squares modulo 9 confirms the residues: $0^2=0$, $1^2=1$, $2^2=4$, $3^2=0$, $4^2=7$, $5^2=7$, $6^2=0$, $7^2=4$, $8^2=1$. This matches the claimed set $0,1,4,7$. Verifying 1977, $1+9+7+7=24\equiv6\pmod{9}$, confirming it cannot occur. For