Maths Olympiad Prep

Library / /32 of 33

Number theory Difficulty 8.9 Shortlist Prove it Turkey

Find all positive integers nn for which an integer that can be written as sum of squares of nn integers with each of them is divisible by nn, can also be expressed as sum of squares of nn integers with none of them is divisible by nn.

Solution

The answer is all positive integers except 11, 22 and 44.

Let us call a positive integer *good* if it satisfies the condition given in the problem. We first show that if nn is good, so is any multiple of nn.

Let m=nkm = nk and x1,x2,,xmx_1, x_2, \dots, x_m be integers such that mxim \mid x_i for all 1im1 \le i \le m. Then since nxin \mid x_i for all 1im1 \le i \le m and nn is good, there exist integers y1,y2,,ymy_1, y_2, \dots, y_m such that
i=nl+1n(l+1)xi2=i=nl+1n(l+1)yi2 \sum_{i=nl+1}^{n(l+1)} x_i^2 = \sum_{i=nl+1}^{n(l+1)} y_i^2
for all 0lk10 \le l \le k-1 and nyin \nmid y_i for all 1im1 \le i \le m. Therefore we obtain that
i=1m=nkxi2=i=1m=nkyi2 \sum_{i=1}^{m=nk} x_i^2 = \sum_{i=1}^{m=nk} y_i^2
and m=nkyim = nk \nmid y_i for all 1im1 \le i \le m.

Lemma: Let nn be a positive odd integer and x1,x2,,xnx_1, x_2, \dots, x_n be integers with at least one of them is not divisible by nn. Then there exist integers y1,y2,,yny_1, y_2, \dots, y_n such that none of them is divisible by nn and
i=1n(nxi)2=i=1nyi2. \sum_{i=1}^{n} (n x_i)^2 = \sum_{i=1}^{n} y_i^2.
*Proof:* Without loss of generality we may assume that nx1n \nmid x_1. Let X=2i=1nxiX = 2 \sum_{i=1}^{n} x_i. If nXn \nmid X, then replace x1x_1 by x1-x_1. As nx1n \nmid x_1 and nn is odd, n4x1n \nmid 4x_1 and hence we may assume that nXn \nmid X. Then by the following identity
i=1n(nxi)2=i=1n(Xnxi)2 \sum_{i=1}^{n} (n x_i)^2 = \sum_{i=1}^{n} (X - n x_i)^2
letting yi=Xnxiy_i = X - n x_i for all 1in1 \le i \le n works.

For a positive odd integer nn, if a positive integer aa is sum of squares of nn integers with each of them is divisible by nn, then there exist integers x1,x2,,xnx_1, x_2, \dots, x_n and a positive integer rr such that a=i=1n(nrxi)2a = \sum_{i=1}^{n} (n^r x_i)^2 and nxin \nmid x_i for some 1in1 \le i \le n. Applying the lemma rr times we can find integers y1,y2,,yny_1, y_2, \dots, y_n such that a=i=1nyi2a = \sum_{i=1}^{n} y_i^2 and nyin \nmid y_i for all 1in1 \le i \le n.

Next we show that 88 is good. Let aa be positive integer which is sum of squares of 88 integers with each of them is divisible by 88. Then 64a64 \mid a, hence a64a \ge 64 and a=12+42+42+42+x12+x22+x32+x42a = 1^2 + 4^2 + 4^2 + 4^2 + x_1^2 + x_2^2 + x_3^2 + x_4^2 for some integers x1,x2,x3,x4x_1, x_2, x_3, x_4 by Lagrange's four-square theorem. Note that x12+x22+x32+x427(mod8)x_1^2 + x_2^2 + x_3^2 + x_4^2 \equiv 7 \pmod{8} and the only way to get 77 as sum of four quadratic residues in (mod 88) is 1+1+1+41+1+1+4. Therefore, 8xi8 \nmid x_i for all 1i41 \le i \le 4.

Finally, we observe that 32=42+42+02+0232 = 4^2 + 4^2 + 0^2 + 0^2 is a counterexample for 44 and we are done.

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.