We prove that the greatest $N$ with the required property is $N=1000$. First note that $x_{i}^{2}-x_{i} x_{j}=x_{i}\left(x_{i}-x_{j}\right)$, and that the prime factorisation of 1111 is $11 \cdot 101$.

We first show that we can find 1000 integers $x_{1}, x_{2}, \ldots, x_{1000}$ such that $x_{i}^{2}-x_{i} x_{j}$ is not divisible by 1111 for any $i \neq j$. Consider the set $\{1,2, \ldots, 1110\}$. This set contains 10 integers divisible by 101, and it contains 100 integers divisible by 11 . None of the integers in the set are divisible by both 11 and 101. If we delete all of these $10+100$ integers from the set, we are left with 1000 integers. Call these $x_{1}, x_{2}, \ldots, x_{1000}$. Now we have $11 \nmid x_{i}$ and $101 \nmid x_{i}$ for all $i$. Suppose there are $i \neq j$ with $1111 \mid x_{i}\left(x_{i}-x_{j}\right)$, then we must have $1111 \mid x_{i}-x_{j}$, which is a contradiction, since $x_{i}, x_{j} \in\{1,2, \ldots, 1110\}$. So this set satisfies the requirement.

We now prove that given 1001 (or more) integers $x_{1}, x_{2}, \ldots, x_{1001}$ there are $i \neq j$ with $1111 \mid x_{i}\left(x_{i}-x_{j}\right)$. Suppose for a contradiction that for all indices $i \neq j$, we have that $x_{i}\left(x_{i}-x_{j}\right)$ is not divisible by 1111, and write $X=\left\{x_{1}, \ldots, x_{1001}\right\}$. We may (after reducing modulo 1111 if necessary) assume that $x_{i} \in\{0,1, \ldots, 1110\}$ for all $i$. Then we know that $x_{i} \neq 0$ for all $i$, and $x_{i} \neq x_{j}$ for all $i \neq j$. Suppose for some $i$ we have $11 \mid x_{i}$. (Since $x_{i} \neq 0$, we know that $101 \nmid x_{i}$.) Then any integer $a \neq x_{i}$ with $a \equiv x_{i} \bmod 101$ cannot be an element of $X$, since $1111 \mid x_{i}\left(x_{i}-a\right)$. In $\{1,2, \ldots, 1110\}$ there are 10 such integers, all of them coprime with $11 \cdot 101$. If there are exactly $k$ different values of $i$ such that $11 \mid x_{i}$, there are $10 k$ different integers from $\{1,2, \ldots, 1110\}$ that cannot be elements of $X$, all of them coprime with $11 \cdot 101$. Similarly, if there are exactly $m$ different values of $i$ such that $101 \mid x_{i}$, then there are $100 \mathrm{~m}$ different integers from $\{1,2, \ldots, 1110\}$ that cannot be elements of $X$, all of them coprime with $11 \cdot 101$. (Note that those $10 k$ and $100 \mathrm{~m}$ integers can overlap.)

In $\{1,2, \ldots, 1110\}$ there are 100 multiples of 11 , there are 10 multiples of 101 and there is no multiple of $11 \cdot 101$, so there are 1000 integers that are coprime with $11 \cdot 101$. In $X$ we have $1001-k-m$ integers that are coprime with $11 \cdot 101$, so exactly $k+m-1$ of the coprime integers in $\{1,2, \ldots, 1110\}$ are not in $X$. This implies that $10 k \leqslant k+m-1$ and $100 m \leqslant k+m-1$. Adding these two inequalities we find $8 k+98 m \leqslant-2$, a clear contradiction. So $N<1001$.
. Find the greatest positive integer $N$ with the following property: there exist integers $x_{1}, \ldots, x_{N}$ such that $x_{i}^{2}-x_{i} x_{j}$ is not divisible by 1111 for any $i \neq j$.