Maths Olympiad Prep

Library / /14 of 42

Number theory Difficulty 5.6 AIME, harder Prove it Ireland

A positive integer is totally square if the sum of its digits (written in base 10) is a square number. For example, 1313 is totally square because 1+3=221 + 3 = 2^2, but 1616 is not totally square. Show that there are infinitely many positive integers that are not the sum of two totally square integers.

Solution

The squares modulo 99 are {0,1,4,7}\{0, 1, 4, 7\}. Any integer is congruent modulo 99 to the sum of its digits (as powers of 1010 are congruent to 11 modulo 99). Therefore any totally square integer is congruent modulo 99 to one of {0,1,4,7}\{0, 1, 4, 7\}. Taking all combinations of pairs, the sum of two totally square integers is congruent modulo 99 to one of {0,1,2,4,5,7,8}\{0, 1, 2, 4, 5, 7, 8\}. Positive integers congruent to 33 (or to 66), of which there are infinitely many, are not the sum of two totally square integers.

Alternatively, we may let S(a)S(a) denote the sum of the digits of a number aa and note that S(a)0,1(mod3)S(a) \equiv 0, 1 \pmod{3} when aa is totally square. When n=n1+n2n = n_1 + n_2 is the sum of two totally square integers n1,n2n_1, n_2 and if n0(mod3)n \equiv 0 \pmod{3}, we have 0nS(n1)+S(n2)(mod3)0 \equiv n \equiv S(n_1) + S(n_2) \pmod{3} which implies S(n1)S(n2)0(mod3)S(n_1) \equiv S(n_2) \equiv 0 \pmod{3}. A square number that is divisible by 33 actually is divisible by 99, hence S(n1)S(n2)0(mod9)S(n_1) \equiv S(n_2) \equiv 0 \pmod{9} and so nS(n1)+S(n2)0(mod9)n \equiv S(n_1) + S(n_2) \equiv 0 \pmod{9}. Therefore, positive integers that are congruent to 33 or 66 (mod 99) cannot be the sum of two totally square integers, e.g. the numbers 310k3 \cdot 10^k for all k0k \ge 0.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.