Many many tuples

First note that 599 is prime.

For a odd number $n$ let $N_n$ be the number of solutions of $x_1^2-x_2^2+x_3^2-x_4^2+\cdots+x_{n}^2 \equiv 1 \pmod{599}$ , where $0\leq x_i \leq 598$ , for $i=1$ to $n$ . We need to know the last three digits of $N_{599}$ .

Consider now the odd number $n\geq 3$ .

Let $t\equiv x_1-x_2 \pmod{599}$ , i.e. $x_1 \equiv x_2+t \pmod{599}$ . Replacing in the principal equation we get: $t^2+2x_2t+x_3^2-x_4^2+\cdots+x_{n}^2 \equiv 1 \pmod{599}.$

1. If $t=0$ we get $N_{n-2}$ solutions for the $(n-2)$ -tuple $(x_3, \ldots, x_n)$ , thus we get $599N_{n-2}$ solutions of the form $(m,m,x_3, \ldots, x_n)$ , where $m$ can take any value between 0 and 598.

2. If $t\neq0$ we get exactly one possible value of $x_2$ given the values $x_3, \ldots, x_n$ (here we use the fact that 599 is a prime number). Thus, if we select the values of $x_3, \ldots, x_n$ then the value of $x_2$ is determined and then the value of $x_1$ is also determined, since $x_1 \equiv x_2+t \pmod{599}$ . Therefore, in this case we have $599^{n-2}$ solutions for each value of $t$ and the total number of solutions is $598\cdot 599^{n-2}$ since $t$ can take 598 values.

Hence we conclude that $N_n=599N_{n-2}+598\cdot 599^{n-2}$ , for any odd number $n\geq3$ .

In the other hand, we know that $N_1=2$ , then $N_3=599\times2+598\times599=599^2+599,$ and $N_5=599\times N_3+598\times599^3=599(599^2+599)+(599-1)\times 599^3=599^4+599^2,$ and by an induction we can conclude that $N_n=599^{n-1}+599^{\frac{n-1}{2}},$ for each odd $n$ .

Therefore, we have $N_{599}=599^{598}+599^{299}$ .

By the Binomial Theorem: $599^{299}=(600-1)^{299}\equiv {299 \choose 1}600^1(-1)^{298}+{299 \choose 0}(-1)^{299} \pmod{1000},$ then $599^{299} \equiv 600\times299-1 \equiv 399 \pmod{100}.$ Squaring we get $599^{598} \equiv 201 \pmod{1000}$ , therefore $N_{599}\equiv 201+399 \equiv 600 \pmod{1000}.$