Find the numbers of ordered array $(x_1,...,x_{100})$ that satisfies the following conditions: ($i$)$x_1,...,x_{100}\in\{1,2,..,2017\}$; ($ii$)$2017|x_1+...+x_{100}$; ($iii$)$2017|x_1^2+...+x_{100}^2$.
Problem
Source: 2017 China TST 4 Problem 3
Tags: combinatorics, set theory, Quadratic Residues, China TST
22.03.2017 19:30
The key idea is to use the identity $$4(x_1^2+x_2^2+x_3^2+x_4^2) = (x_1+x_2+x_3+x_4)^2 + (x_1+x_2-x_3-x_4)^2 + (x_1-x_2+x_3-x_4)^2 + (x_1-x_2-x_3+x_4)^2.$$This allows us to replace the conditions with $2017|y_1+ \dots + y_{25}$ and $2017|y_1^2 + \dots + y_{100}^2$. Iterating this procedure, we can reduce it to $2017|a+b+c+d$ and $2017|a^2+4b^2+4c^2+16d^2+z_1^2+ \dots + z_{96}^2$. The rest should be relatively easy.
29.03.2017 18:03
@angiland: Can you elaborate more please? I don't see how it works.
29.03.2017 21:37
Very nice solution Canton. My solution is to use the identity $$4(x_1^2+x_2^2+x_3^2+x_4^2) = (x_1+x_2+x_3+x_4)^2 + (x_1+x_2-x_3-x_4)^2 + (x_1-x_2+x_3-x_4)^2 + (x_1-x_2-x_3+x_4)^2.$$We now define $y_1 = x_1 + x_2 + x_3 + x_4$, $y_2 = x_1 + x_2 - x_3 - x_4$, $y_3 = x_1 - x_2 + x_3 - x_4$, $y_4= x_1 - x_2 - x_3 + x_4$, $y_5 = x_5 + x_6 + x_7 + x_8$, etc etc. Then the two conditions become $$ 2017 | y_1 + y_5 + y_9 + \dots + y_{97} $$and $$2017 | y_1^2 + \dots + y_{100}^2.$$This pair of conditions is drastically simpler than the original, because only $25$ variables appear in the first condition. Furthermore, the linear transformations involved are bijective, so we can simply count the number of tuples $(y_1, \dots, y_{100})$. We can iterate this reduction procedure to further reduce the number of variables appearing in the first condition, until $2017|a+b+c+d$ and $2017|a^2+4b^2+4c^2+16d^2+z_1^2+ \dots + z_{96}^2$. This last pair of conditions is sufficiently easy to work out by brute force.
07.03.2018 04:01
Hi, Quote: Claim. For each residue $t$ modulo $2017$, the number of solutions to $x^2 + y^2 = t$ is $4033$ if $t = 0$ and $2016$ otherwise. Proof. Well-known; will edit in later if requested. I was wondering how to prove this. Thanks
07.03.2018 04:41
(Credit goes to the AMSP NT3 notes for reminding me of some of the details of this argument.) It is easy to check $t=0$, so assume $t\neq 0$. First remark that the number of solutions to $x^2-y^2\equiv t\pmod p$ is $p-1$ upon rewriting as $(x-y)(x+y)\equiv t\pmod p$. Since the number of solutions to $x^2\equiv a\pmod p$ is $1+(\tfrac ap)$ (just case on whether $a$ is a quadratic residue or not), we obtain \[p - 1 = N(x^2 - y^2 = t) = \sum_y\left[1 + \left(\frac{t + y^2}p\right)\right] = p + \left(\frac{-1}p\right)\sum_y\left(\frac{-t-y^2}p\right),\]which rearranges to $\textstyle\sum_y(\tfrac{-t-y^2}p) = -(\tfrac{-1}p) = -(-1)^{(p-1)/2}$. Now the number of solutions to $x^2 + y^2 = -t$ is by a similar argument equal to \[\sum_y\left[1 + \left(\frac{-t-y^2}p\right)\right] = p + \sum_y\left(\frac{-t-y^2}p\right) = p - (-1)^{(p-1)/2}.\]Plugging in $p=2017$ gives the desired.
02.04.2018 20:21
Main idea is the same as Canton's but with details nontrivially different.