Show that $\prod _{i<j}(x_i-x_j)$ can be divided wihout remainder in $\prod_{i<j}(i-j)$

Question

Let $x_1,...,x_n$ be a natural numbers,

show that $\prod _{i<j}(x_i-x_j)$ can be divided wihout remainder in $\prod_{i<j}(i-j)$

I know $\prod \left(x_i-x_j\right)$ is the result of Vandermonde Determinant, so is related with Det?

Answer 1

Lemma. For every m-coloring vertices of complete graph $K_n$ ($m \leq n$) there are at least $n-m$ edges which have two vertices of the same color.

proof: Inducion by $n$ - number of vertices. For $n=1,2,3$ this fact is obvious.

$n-1 \rightsquigarrow n$: Let $V$ is the set of vertices, of $K_n$ ($\left\vert{V}\right\vert= n$). $m \leq n$ hecnce from pigeonhole principle we have at least two vertices of the same color, for example $a$ and $b$. Consider graph $K_{n-1}$ with set of vertices $V \setminus {a}$. From induction, we have at least $n-1-m$ edges with 2 vetrices of te same color. These edges plus edge $\{a,b\}$ gives us the desirable at least $(n-m)$-element edge set.

Consider now $A := \prod_{i<j} (i-j)$. Note that given difference: $i-j=m$ occurs exactly $n-m$ times in this product ($A$). So $m^{n-m} | A$.

We ask why $m^{n-m} | \prod_{i<j} (x_i-x_j)$ ? Consider graph $K_n$ of $V=\{1,2,\ldots,n\}$ veritices. Each vertex $v$ has color from $\{0,1,\ldots,m-1\}$ $m$-element set and this color equals $\chi(v) := x_v \bmod m$. From above lemma we have at least $n-m$ egdes with both vertices of the same color, so there are at least $n-m$ pairs: $x_{i_1}-x_{j_1}, \ldots, x_{i_{n-m}}-x_{j_{n-m}}$, such that $m | x_{i_k}-x_{j_k}$, hence $m^{n-m} | \prod_{i<j} (x_i-x_j)$. This is true for all $m = i-j$, so we have $\prod_{i<j} (i-j) | \prod_{i<j} (x_i-x_j)$.