Maths Olympiad Prep

Library / /56 of 97

Number theory Difficulty 8.0 Shortlist Find the answer

Find the numbers of ordered array (x1,...,x100)(x_1,...,x_{100}) that satisfies the following conditions:
(ii)x1,...,x100{1,2,..,2017}x_1,...,x_{100}\in\{1,2,..,2017\};
(iiii)2017x1+...+x1002017|x_1+...+x_{100};
(iiiiii)2017x12+...+x10022017|x_1^2+...+x_{100}^2.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We are asked to find the number of ordered arrays (x1,x2,,x100)(x_1, x_2, \ldots, x_{100}) that satisfy the following conditions:
1. x1,x2,,x100{1,2,,2017}x_1, x_2, \ldots, x_{100} \in \{1, 2, \ldots, 2017\},
2. 2017(x1+x2++x100)2017 \mid (x_1 + x_2 + \cdots + x_{100}),
3. 2017(x12+x22++x1002)2017 \mid (x_1^2 + x_2^2 + \cdots + x_{100}^2).

To solve this problem, we generalize to an arbitrary prime p p and use a classical roots of unity filter to count the number of such tuples. Let ω=e2πip\omega = e^{\frac{2 \pi i }{p}} and NN be the total number of such ordered tuples.

The key observation is that:
0a,bp1ωb(x1+x2++x100)+a(x12+x22++x1002)={p2if (x1,x2,,x100) satisfies the conditions,0otherwise. \sum_{0 \leq a, b \leq p-1} \omega^{b(x_1 + x_2 + \cdots + x_{100}) + a (x_1^2 + x_2^2 + \cdots + x_{100}^2)} = \begin{cases} p^2 & \text{if } (x_1, x_2, \ldots, x_{100}) \text{ satisfies the conditions}, \\ 0 & \text{otherwise}. \end{cases}

From this observation, we see that:
p2N=(x1,x2,,x100)0a,bp1ωb(x1+x2++x100)+a(x12+x22++x1002). p^2 \cdot N = \sum_{(x_1, x_2, \ldots, x_{100})} \sum_{0 \leq a, b \leq p-1} \omega^{b(x_1 + x_2 + \cdots + x_{100}) + a (x_1^2 + x_2^2 + \cdots + x_{100}^2)}.

Swapping the sums makes it easier to factor:
p2N=0a,bp1(x=0p1ωax2+bx)100. p^2 N = \sum_{0 \leq a, b \leq p-1} \left( \sum_{x=0}^{p-1} \omega^{ax^2 + bx} \right)^{100}.

We deal with the edge case a=0a = 0 first. If bb is nonzero, then 1+ωb+ω2b++ω(p1)b=01 + \omega^b + \omega^{2b} + \cdots + \omega^{(p-1)b} = 0. On the other hand, if b=0b = 0, then the sum evaluates to pp.

Hence:
p2N=p100+1ap10bp1(x=0p1ωax2+bx)100. p^2 N = p^{100} + \sum_{\substack{1 \leq a \leq p-1 \\ 0 \leq b \leq p-1}} \left( \sum_{x=0}^{p-1} \omega^{ax^2 + bx} \right)^{100}.

To relate the inner sums to Gauss sums, we complete the square:
p2N=b=0p1a=1p1ωb2a(x=0p1ωa(x+b2a)2)100. p^2 N = \sum_{b=0}^{p-1} \sum_{a=1}^{p-1} \omega^{\frac{-b^2}{a}} \left( \sum_{x=0}^{p-1} \omega^{a(x + \frac{b}{2a})^2} \right)^{100}.

Since ω\omega is a primitive ppth root of unity,
x=0p1ωa(x+b2a)2=x=0p1ωax2. \sum_{x=0}^{p-1} \omega^{a(x + \frac{b}{2a})^2} = \sum_{x=0}^{p-1} \omega^{ax^2}.

For aa not divisible by pp, define G(a)=x=0p1ωax2G(a) = \sum_{x=0}^{p-1} \omega^{ax^2} and denote G(1)G(1) by GG. We wish to compute G(a)G(a).

Claim: G(a)=(ap)GG(a) = \left(\frac{a}{p}\right) G.

This follows from the properties of quadratic residues and non-residues. Since G(a)G(a) is raised to an even power, its sign does not matter. We need to evaluate G100G^{100}.

Claim: G2=(1)p12pG^2 = (-1)^{\frac{p-1}{2}} p.

This follows from the properties of Gauss sums. Using Euler's Criterion, we conclude that G2=(1)p12pG^2 = (-1)^{\frac{p-1}{2}} p.

Returning to our expression for NN:
p2N=p100+b=0p1a=1p1ωb2aG100. p^2 N = p^{100} + \sum_{b=0}^{p-1} \sum_{a=1}^{p-1} \omega^{\frac{-b^2}{a}} G^{100}.

Since the sum over aa for fixed bb evaluates to zero, we conclude:
N=p98. N = p^{98}.

Thus, for p=2017p = 2017, the number of ordered arrays (x1,x2,,x100)(x_1, x_2, \ldots, x_{100}) that satisfy the given conditions is:
201798. \boxed{2017^{98}}.

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