Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Please avoid titles that are entirely in $\LaTeX$. – J. M. Feb 3 '12 at 16:25
Without the $i-j$, this is the determinant of a Vandermonde Matrix: – Eric Naslund Feb 3 '12 at 16:35
Your expression (up to a negative sign) is the determinant of the exponential vandermonde matrix: $$\left[\begin{array}{ccccc} 1 & \frac{x_{1}}{1!} & \cdots & \frac{x_{1}^{n-2}}{(n-2)!} & \frac{x_{1}^{n-1}}{(n-1)!}\\ 1 & \frac{x_{2}}{1!} & \cdots & \frac{x_{2}^{n-2}}{(n-2)!} & \frac{x_{2}^{n-1}}{(n-1)!}\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & \frac{x_{n-1}}{1!} & \cdots & \frac{x_{n}^{n-2}}{(n-2)!} & \frac{x_{n}^{n-1}}{(n-1)!}\\ 1 & \frac{x_{n}}{1!} & \cdots & \frac{x_{n}^{n-2}}{(n-2)!} & \frac{x_{n}^{n-1}}{(n-1)!} \end{array}\right].$$ – Eric Naslund Feb 3 '12 at 17:29
Argh. I used to know a very nice proof of this, but I've completely forgotten it. It's somewhere on AoPS. – Qiaochu Yuan Feb 3 '12 at 22:04
@Qiaochu: It must have been similar to David Moews answer. I doubt much nicer will appear. – robjohn Feb 4 '12 at 0:11
up vote 17 down vote accepted

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.

share|cite|improve this answer

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$.

share|cite|improve this answer
This is the idea behind of one of the existing proofs (cf. the post by Valiowk on ), but for it to be complete, the "uneven distribution" argument has to be made precise, and not only primes need to be counted (but also, at least, prime powers). – darij grinberg Aug 19 '15 at 0:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.