Problem 1331

To solve the problem, we need to compute the number of $k$-tuples $(x_1, x_2, \ldots, x_k)$ such that $0 \le x_i < 73$ for each $i$ and $73 \mid x_1^2 + x_2^2 + \cdots + x_k^2 - 1$. We denote this number by $T_k$. We then need to find the remainder when $T_1 + T_2 + \cdots + T_{2017}$ is divided by 2017.

1. **Counting the number of solutions $T_k$:**
We start by considering the function $f(x_1, \ldots, x_k) = x_1^2 + x_2^2 + \cdots + x_k^2 - 1$. We need to count the number of solutions $(x_1, \ldots, x_k)$ in $\mathbb{Z}/73\mathbb{Z}^k$ that satisfy $f(x_1, \ldots, x_k) \equiv 0 \pmod{73}$.

2. Using the roots of unity filter:
Let $\zeta = e^{2\pi i / 73}$ be a primitive 73rd root of unity. The number of solutions $N$ can be expressed using the roots of unity filter:
$$73 \cdot N = \sum_{x_1, \ldots, x_k} \sum_{j=0}^{72} \zeta^{j f(x_1, \ldots, x_k)}.$$
This simplifies to:
$$73^k + \sum_{j=1}^{72} \sum_{x_1, \ldots, x_k} \zeta^{j (x_1^2 + x_2^2 + \cdots + x_k^2 - 1)}.$$

3. Simplifying the inner sum:
$$\sum_{x_1, \ldots, x_k} \zeta^{j (x_1^2 + x_2^2 + \cdots + x_k^2 - 1)} = \zeta^{-j} \left( \sum_{x_1} \zeta^{j x_1^2} \right) \left( \sum_{x_2} \zeta^{j x_2^2} \right) \cdots \left( \sum_{x_k} \zeta^{j x_k^2} \right).$$
Each sum $\sum_{x_i} \zeta^{j x_i^2}$ is a Gauss sum $G(j)$.

4. Properties of Gauss sums:
The Gauss sum $G(j)$ is defined as:
$$G(j) = \sum_{x=0}^{72} \zeta^{j x^2}.$$
If $j \neq 0$, $G(j) = \left( \frac{j}{73} \right) G$, where $G = G(1)$ and $\left( \frac{j}{73} \right)$ is the Legendre symbol. For $j = 0$, $G(0) = 73$.

5. Combining the results:
$$N = 73^{k-1} + \frac{1}{73} \sum_{j=1}^{72} \zeta^{-j} G(j)^k.$$
Using the properties of Gauss sums, we get:
$$G(j)^k = \left( \frac{j}{73} \right)^k G^k.$$
For even $k$, the sum $\sum_{j=1}^{72} \zeta^{-j} \left( \frac{j}{73} \right)^k$ evaluates to $-1$ if $73 \nmid 1$, and for odd $k$, it evaluates to $G$.

6. **Final expressions for $T_k$:**
For even $k$:
$$T_k = 73^{k-1} - 73^{\frac{k-2}{2}} (-1)^{k/2}.$$
For odd $k$:
$$T_k = 73^{k-1} + 73^{\frac{k-1}{2}}.$$

7. **Summing $T_1 + T_2 + \cdots + T_{2017}$:**
We need to compute the sum of these expressions for $k$ from 1 to 2017 and find the remainder when divided by 2017.

$$\sum_{k=1}^{2017} T_k = \sum_{\text{odd } k} \left( 73^{k-1} + 73^{\frac{k-1}{2}} \right) + \sum_{\text{even } k} \left( 73^{k-1} - 73^{\frac{k-2}{2}} (-1)^{k/2} \right).$$

8. Modulo 2017:
Since 2017 is a prime number, we can use properties of modular arithmetic to simplify the sum. We need to compute the sum modulo 2017.

The final answer is $\boxed{0}$