Showing $\prod\limits_{i<j} \frac{x_i-x_j}{i-j}$ is an integer

Let $x_1,...,x_n$ be distinct integers. Prove that

$$\prod_{i<j} \frac{x_i-x_j}{i-j}\in \mathbb Z$$

I know there is a solution using determinant of a matrix, but I can't remember it now. Any help will be appreciated.


If $x_1$, $\ldots$, $x_n$ are integers, then $\prod_{1\le i<j\le n} \frac{x_i-x_j}{i-j}$ is integral because it is the determinant of the integral matrix $$\left(x_i \choose j-1\right)_{i,j=1,\ldots,n}.$$

You can see this by starting with the formula for the determinant of the Vandermonde matrix, $$\det\left( (x_i^{j-1})_{i,j=1,\ldots,n}\right) = \prod_{1\le i<j\le n} (x_j-x_i);$$ then, divide column $j$ of the Vandermonde matrix by $(j-1)!$ to get the matrix $$\left(\frac{x_i^{j-1}}{(j-1)!}\right)_{i,j=1,\ldots,n}$$ given by Eric Naslund above. Its determinant equals $\prod_{1\le i<j\le n} \frac{x_j-x_i}{j-i}=\prod_{1\le i<j\le n} \frac{x_i-x_j}{i-j}$. Finally, taking $j=n$, $n-1$, $\ldots$, $1$ in succession, add in rational multiples of columns $1$, $\ldots$, $j-1$ to column $j$ to change each $\frac{x_i^{j-1}}{(j-1)!}$ to $x_i \choose j-1$; this does not change the determinant of the matrix.


Here's a very direct approach. For each prime up to $n-1$, we just need to check that $$ \text{val}_p\left( \prod_{i<j}(i-j)\right) \leq \text{val}_p\left( \prod_{i<j}(x_i-x_j) \right) $$ for any choice of integers $x_i$. (Here, the $p$-adic valuation $\text{val}_p(x)$ simply counts the powers of $p$ that divide $x$.) That is, we need to show that choosing $x_1, x_2, \ldots, x_n$ to be $1, 2, \ldots, n$ gives the smallest $p$-adic valuation possible.

To do this, notice that setting $x_i=i$ gives the minimum possible number of pairs $(i,j)$ such that $x_i-x_j$ is divisible by $p$ (or divisible by $p^2$, or by $p^3$, or any $p^k<n$ ). This is because the numbers $1, 2, \ldots, n$ are as evenly spread out among the residue classes modulo $p^k$ as possible. By the Pigeonhole principle, any other choice of integers $x_1, x_2, \ldots, x_n$ will have at least as many repeated residue classes, and an uneven distribution leads to a greater total number of pairs $(x_i,x_j)$ from the same residue class. (Because of the inequality of triangular numbers $T_{n+i}+T_{n-i} \geq 2T_{n}$.)

Thus, $\displaystyle \prod_{i<j} \frac{x_i-x_j}{i-j}$ is an integer, because there are at least as many powers of $p$ on top as there are on the bottom for each prime $p$.