Maths Olympiad Prep

Library / /417 of 520

Number theory Difficulty 6.7 National olympiad Prove it

10. Let N4(n)N_{4}(n) denote the total number of solutions to n=x12+x22+x32+x42n=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2} (different orders and signs are considered as different solutions), and let σ(n)\sigma(n) denote the sum of the positive divisors of nn, i.e., σ(n)=dnd\sigma(n) = \sum_{d \mid n} d (for example, σ(6)=1+2+3+6=12\sigma(6) = 1 + 2 + 3 + 6 = 12). This problem aims to use the discussion and conclusions about the total number of solutions N(n)N(n) to x2+y2=nx^{2} + y^{2} = n to prove:
N4(n)={8σ(n),2n,24σ(m),n=2km,k1,2m.N_{4}(n)=\left\{\begin{array}{ll} 8 \sigma(n), & 2 \nmid n, \\ 24 \sigma(m), & n=2^{k} m, k \geqslant 1, 2 \nmid m . \end{array}\right.
(i) Suppose 2n2 \nmid n, and let M(n)M(n) be the total number of solutions to the indeterminate equation 4n=u12+u22+u32+u424 n = u_{1}^{2} + u_{2}^{2} + u_{3}^{2} + u_{4}^{2}, where 2uj(1j4)2 \nmid u_{j} (1 \leqslant j \leqslant 4). Prove that M(n)=σ(n)M(n) = \sigma(n).
(ii) Suppose 2n2 \nmid n. Prove that N4(2n)=3N4(n)N_{4}(2 n) = 3 N_{4}(n), N4(2n)=N4(4n)N_{4}(2 n) = N_{4}(4 n), and N4(4n)=16σ(n)+N4(n)N_{4}(4 n) = 16 \sigma(n) + N_{4}(n).
(iii) Derive the desired conclusion from (i) and (ii).
(iv) Verify the correctness of the above conclusions for n=105,210n = 105, 210 (Hint: To prove (i), use
M(n)=a+b=2nN(2a)4N(2b)4=a+b=2n(s2ah(s))(t2bh(t))=ax+y=2nh(st)\begin{aligned} M(n) & =\sum_{a+b=2 n} \frac{N(2 a)}{4} \frac{N(2 b)}{4} \\ & =\sum_{a+b=2 n}\left(\sum_{s \mid 2 a} h(s)\right)\left(\sum_{t \mid 2 b} h(t)\right) \\ & =\sum_{a x+y=2 n} h(s t) \end{aligned}

Here the variables s,t,x,ys, t, x, y take positive odd values. Divide the final sum into two parts: s=ts = t and sts \neq t. The sum of the part where s=ts = t equals σ(n)\sigma(n), and the other part is zero.

Solution

10. (i) For the terms where sts \neq t, pair them as {s,t,x,y},{s,t,x,y}\{s, t, x, y\},\left\{s^{\prime}, t^{\prime}, x^{\prime}, y^{\prime}\right\}: Let
l=[t/(st)],x=ls+(l+1)ty=(l+1)s(l+2)t,s=(l+2)x+(l+1)y\begin{array}{c} l=[t /(s-t)], \quad x^{\prime}=-l s+(l+1) t \\ y^{\prime}=(l+1) s-(l+2) t, \quad s^{\prime}=(l+2) x+(l+1) y \end{array}

and t=(l+1)x+lyt^{\prime}=(l+1) x+l y, then h(st)+h(st)=0h(s t)+h\left(s^{\prime} t^{\prime}\right)=0.
(ii) If 2n=x12+x22+x32+x422 n=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}, then these xix_{i} are two even and two odd. Therefore, the number of solutions where x1,x2x_{1}, x_{2} are even and x3,x4x_{3}, x_{4} are odd is N4(2n)/6N_{4}(2 n) / 6. From this set of solutions, we can obtain solutions for n=y12+y22+y32+y42n=y_{1}^{2}+y_{2}^{2}+y_{3}^{2}+y_{4}^{2}:
y1=(x1+x2)/2,y2=(x1x2)/2,y3=(x3+x4)/2,y4=(x3x4)/2y_{1}=\left(x_{1}+x_{2}\right) / 2, y_{2}=\left(x_{1}-x_{2}\right) / 2, y_{3}=\left(x_{3}+x_{4}\right) / 2, y_{4}=\left(x_{3}-x_{4}\right) / 2 \text {, }

and they satisfy 2y1+y2,2y3+y42 \mid y_{1}+y_{2}, 2 \nmid y_{3}+y_{4}. This implies N4(2n)/6N4(n)/2N_{4}(2 n) / 6 \leqslant N_{4}(n) / 2. Similarly, we can prove N4(n)/2N4(2n)/6N_{4}(n) / 2 \leqslant N_{4}(2 n) / 6. This proves N4(2n)=3N4(n)N_{4}(2 n)=3 N_{4}(n). If 4n=x12+x22+x32+x424 n=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}, then xix_{i} are either all even or all odd. Using the above transformation, we can establish a one-to-one correspondence with the solutions of 2n=y12+y22+y32+y422 n=y_{1}^{2}+y_{2}^{2}+y_{3}^{2}+y_{4}^{2}, which leads to N4(2n)=N4(4n)N_{4}(2 n)=N_{4}(4 n). From the discussion of the solutions for 4n4 n, using (i) and the definition, we derive the formula for N4(4n)N_{4}(4 n).

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.