We are asked to find the number of ordered arrays (x1,x2,…,x100) that satisfy the following conditions:
1. x1,x2,…,x100∈{1,2,…,2017},
2. 2017∣(x1+x2+⋯+x100),
3. 2017∣(x12+x22+⋯+x1002).
To solve this problem, we generalize to an arbitrary prime p and use a classical roots of unity filter to count the number of such tuples. Let ω=ep2πi and N be the total number of such ordered tuples.
The key observation is that:
0≤a,b≤p−1∑ωb(x1+x2+⋯+x100)+a(x12+x22+⋯+x1002)={p20if (x1,x2,…,x100) satisfies the conditions,otherwise.
From this observation, we see that:
p2⋅N=(x1,x2,…,x100)∑0≤a,b≤p−1∑ωb(x1+x2+⋯+x100)+a(x12+x22+⋯+x1002).
Swapping the sums makes it easier to factor:
p2N=0≤a,b≤p−1∑(x=0∑p−1ωax2+bx)100.
We deal with the edge case a=0 first. If b is nonzero, then 1+ωb+ω2b+⋯+ω(p−1)b=0. On the other hand, if b=0, then the sum evaluates to p.
Hence:
p2N=p100+1≤a≤p−10≤b≤p−1∑(x=0∑p−1ωax2+bx)100.
To relate the inner sums to Gauss sums, we complete the square:
p2N=b=0∑p−1a=1∑p−1ωa−b2(x=0∑p−1ωa(x+2ab)2)100.
Since ω is a primitive pth root of unity,
x=0∑p−1ωa(x+2ab)2=x=0∑p−1ωax2.
For a not divisible by p, define G(a)=∑x=0p−1ωax2 and denote G(1) by G. We wish to compute G(a).
Claim: G(a)=(pa)G.
This follows from the properties of quadratic residues and non-residues. Since G(a) is raised to an even power, its sign does not matter. We need to evaluate G100.
Claim: G2=(−1)2p−1p.
This follows from the properties of Gauss sums. Using Euler's Criterion, we conclude that G2=(−1)2p−1p.
Returning to our expression for N:
p2N=p100+b=0∑p−1a=1∑p−1ωa−b2G100.
Since the sum over a for fixed b evaluates to zero, we conclude:
N=p98.
Thus, for p=2017, the number of ordered arrays (x1,x2,…,x100) that satisfy the given conditions is:
201798.