Residues of 2017

This solution is adapted from two MathSE answers - Answer 1 and Answer 2

Observe that 2017 is a prime and is 1 mod 4. We will make use of properties of primes that are 1 mod 4.

Lemma: For any prime $p \equiv 1 \pmod{4}$ , we see that $-1$ is a quadratic residue $\text{mod } p$ .

Proof: We can make use of Wilson's theorem to prove this. We can write $\begin{aligned} -1 & \equiv (p-1)! \\ & \equiv \left( 1 \times 2 \times 3 \times \cdots \times \frac{p-1}{2} \right) \times \left( \frac{p+1}{2} \times \cdots \times (p-1) \right)\\ & \equiv \left(\left( \frac{p-1}{2} \right)! \right)^{2} \times (-1)^{\frac{p-1}{2} } \\ & \equiv \left(\left( \frac{p-1}{2} \right)! \right)^{2} \times \color{#3D99F6}{1} ~~~~ \color{#3D99F6}{\text{(Since } \frac{p-1}{2} \text{ is even.)}} \\ & \equiv \left(\left( \frac{p-1}{2} \right)! \right)^{2} \pmod{p} \end{aligned}$

We see that there exists an integer $\left(\left( \frac{p-1}{2} \right)!\right)$ whose square is -1 mod p. Hence $-1$ is a quadratic residue mod p. $_\blacksquare$

---

Since product of two residues is also a residue, for every residue $a$ , we see that $a \times (-1) = -a \equiv p - a$ is also a quadratic residue mod p. We can divide all residues of $p$ into pairs $a$ and $p - a$ . The sum of each pair is $a + p - a = p$ .

We know that any odd prime number has exactly $\frac{p-1}{2}$ quadratic residues mod p, which means there are $\frac{ p -1 }{4}$ pairs of residues. Each pair has sum of $p$ , therefore the total sum is $p \times \frac{p-1}{4}$ .

In this problem, $p = 2017$ . There the sum is $2017 \times \frac{ 2017 -1 }{ 4} = \frac { 2017 \times 2016 }{4} = 2017 \times 504$ . We need to find its last three digits.

$\begin{aligned} 2017 \times 504 & \equiv 17 \times 504 \pmod{1000} \\ &\equiv 8568 \pmod{1000} \\ & \equiv 568 \pmod{1000} \\ \end{aligned}$

The last three digits of the sum of residues is $\boxed{568}$ $_\square$