Lucky pick

The problem reduces to being sure that you have two numbers, a and b, in the set such that 1000|(a^2-b^2) which implies that a^2=b^2 mod 1000. Note that 1000= (2^3)*(5^3).
x^2 has 3 possible values mod 8.
x^2 has 53 possible values mod 125.
By the Chinese remainder theorem, x^2 has $3 \times 53=159$ possible values mod 1000. Thus, by the pigeonhole principle, in a set of 160 integers, at least two will exist such that their squares are congruent mod 1000.

There are $159$ different remainders, modulo $1000$ , that squares can give. We only need to check this for numbers from $0$ to $250$ , since $x^2$ , $(500-x)^2$ and $(500+x)^2$ all give the same remainder modulo $1000$ .

The fact that $160$ numbers are bound to provide at least two squares which have the same remainder modulo $1000$ , and hence whose difference is a multiple of $1000$ , is now an elementary application of the Pigeon-Hole Principle.

We need to consider the quadratic residues $\mod 1000$ . If there are $q$ of these, then by the pigeonhole principle a set of size $q+1$ , and no smaller, must contain two integers with the same quadratic residue $\mod 1000$ and therefore their difference is a multiple of 1000.

Let $q(X)$ be the number of quadratic residues $\mod X$ . From the Chinese Remainder Theorem we can prove that if $M,N$ are coprime then $q(X) = q(M)q(N)$ . So $q(1000) = q(2^3) q(5^3) = 3 \times 53 = 159$ and the answer we want is $\boxed{160}$ .

$q(2^3)$ can easily be checked by inspection to be $3$ because the residues are ${0,1,4}$ .

$q(5^3)$ is trickier to explain. Gauss found the general solution for powers of an odd prime in Disquisitions Arithmeticae articles 101 and 102.

I didn't prove it myself from scratch, but took hints from Gauss's proof.

Any member of the integers $\mod 5^3$ can be written in one of these forms: $a, 5a, \mbox{ or } 5^2a$ where $a$ is coprime to $5$ . We'll look at those cases separately.

Case 1: If we have $x^2 \equiv a \mod 5^3 \\ y^2 \equiv a \mod 5^3$ then $x^2 - y^2 \equiv 0 \mod 5^3$ so $5$ divides $(x+y)(x-y)$ .

$5$ can't divide both of those, otherwise it would divide their sum $2x$ , contradicting that $x^2$ is coprime to $5$ . Therefore either $x \equiv y$ or $x \equiv -y$ . Since we already know that $-a$ is a quadratic residue $\mod p$ iff $a$ is, we conclude that $a$ is a quadratic residue $\mod p^n$ iff it is one $\mod p$ .

Case 2: $x^2 \equiv 5a \mod 5^3$ . Suppose there is $s$ such that $5a \equiv s^2 \mod 5^3$ . Since $5 \vert s^2$ , then $5 \vert s$ . So $5^2 \vert s^2$ , so $5 \vert a$ , contradicting the defintion of $a$ . Conclusion: $5a$ is never a residue.

Case 3: $x^2 \equiv 5^2a \mod 5^3$ . If $a$ is a quadratic residue $\mod 5^3$ then $a = s^2$ for some $s$ , and then $5^2a = (5s)^2$ , so $5^2a$ is also a quadratic residue.

And if $a$ is not a quadratic residue $\mod 5^3$ then there cannot be a solution $s$ to $5^2a \equiv s^2 \mod 5^3$ otherwise $5^2$ would divide $s^2$ .

Conclusion: in this case, $5^2a$ is a residue iff $a$ is.

Totalling the three cases and using the fact that the quadratic residues $\mod 5$ are $\{0, -1, +1\}$ : Case 1 gives us all numbers of the form $5k \pm 1 \mod 5^3$ , of which there are $25 * 2 = 50$ . Case 3 gives us $0, 5^2, -5^2$ which is $3$ cases, for a sum of $50 + 3 = 53$ .

Let $k$ be the number of quadratic residues. If we have $k+1$ integers, then by the pigeonhole principle, there must be 2 whose square are congruent in modulo 1000 (since there are a total of $k$ possible residues). There is a total of 159 quadratic residues so we need 160 numbers.