It suffices to prove that the product is divisible by both 4 and 3. By the pigeonhole principle, there are two amongst the quadruple $a,b,c,d$ that are congruent modulo 3; the difference of these two is therefore divisible by 3 and hence the whole product is divisible by 3. There must be at least two distinct pairs amongst $a,b,c,d$ that are congruent modulo 2: their differences are both divisible by 2 and hence the whole product is divisible by $2^2=4$.

Generalisation: Let $a_1, a_2, ..., a_n$ be integers. Then $\prod_{i<j} \left( a_{i}-a_{j} \right)$ is divisible by $\prod_{k=1}^{n-1} k!$. In other words, $\prod_{i<j} \left( \frac{a_{j}-a_{i}}{j-i} \right)$ is an integer.

ZeTaX, do you have a nice proof of the generalisation?

ZetaX wrote: Generalisation: Let $ a_1, a_2, ..., a_n$ be integers. Then $ \prod_{i < j} \left( a_{i} - a_{j} \right)$ is divisible by $ \prod_{k = 1}^{n - 1} k!$. In other words, $ \prod_{i < j} \left( \frac {a_{j} - a_{i}}{j - i} \right)$ is an integer. Proof:- It is well-known that the product $ \prod_{i < j} \left( a_{i} - a_{j} \right) = \det(V)$, where $ V: = [ a_i^{j-1} ]_{i,j}$ is the Vandemonde Matrix (see http://en.wikipedia.org/wiki/Vandermonde_matrix) Note that the expression $ P_{j-1}^{a_i} = a_i(a_i - 1)...(a_i - j + 2) = \sum_{k=0}^{j-1} A_{k} \cdot a_i^k$ for some constants $ A_{k}$ not depending on $ i$. Perform a series of column operations that does not change the determinant $ \mbox{for } j : = n \mbox{ down to } 3 \\ \mbox{ for } k : = j-1 \mbox{ down to } 2 \\ \mbox{ } \mbox{ column } j \leftarrow \mbox{ column } j - A_{k-1} \cdot \mbox{ column } k \\ \mbox{ end for} \\ \mbox{end for} $ We get \begin{eqnarray*} \prod_{i < j} \left( a_{i} - a_{j} \right) & = & \det(V) \\ & = & \det \left( \left[ {P_{j-1}^{a_i}} \right]_{i,j} \right) \\ & = & \det \left( \left[ (j-1)! {{a_i} \choose {j-1}} \right]_{i,j} \right) \\ & = & \prod_{j=1}^{n} {(j-1)!} \cdot \left| \left[ {{a_i} \choose {j-1}} \right]_{i,j} \right| \\ & = & \prod_{k=1}^{n-1} {k!} \cdot D \\ \end{eqnarray*} where $ D = \left| \left[ {{a_i} \choose {j-1}} \right]_{i,j} \right| \in \mathbb{Z}$. Therefore $ \prod_{i < j} (j - i) = \prod_{k=1}^{n-1} {k!} \left| \prod_{i < j} \left( a_{i} - a_{j} \right) \right.$ For more details, see http://groups.google.com/group/sci.math/browse_thread/thread/f14b3c2b944cdc5d/9e3bdfc5da0ec445#9e3bdfc5da0ec445

Peter wrote: ZeTaX, do you have a nice proof of the generalisation? You need to tell me if I forget to answer See http://www.mathlinks.ro/viewtopic.php?t=4858 .

let a=9, b=7, c=5, d=3 (a-b)(a-c)(a-d)(b-c)(b-d)(c-d)=(9-7)(9-5)(9-3)(7-5)(7-3)(5-3)=2.4.6.3.4.2=12k.... proof

YeOldeMan wrote: ZetaX wrote: Generalisation: Let $ a_1, a_2, ..., a_n$ be integers. Then $ \prod_{i < j} \left( a_{i} - a_{j} \right)$ is divisible by $ \prod_{k = 1}^{n - 1} k!$. In other words, $ \prod_{i < j} \left( \frac {a_{j} - a_{i}}{j - i} \right)$ is an integer. Proof:- It is well-known that the product $ \prod_{i < j} \left( a_{i} - a_{j} \right) = \det(V)$, where $ V: = [ a_i^{j-1} ]_{i,j}$ is the Vandemonde Matrix (see http://en.wikipedia.org/wiki/Vandermonde_matrix) Note that the expression $ P_{j-1}^{a_i} = a_i(a_i - 1)...(a_i - j + 2) = \sum_{k=0}^{j-1} A_{k} \cdot a_i^k$ for some constants $ A_{k}$ not depending on $ i$. Perform a series of column operations that does not change the determinant $ \mbox{for } j : = n \mbox{ down to } 3 \\ \mbox{ for } k : = j-1 \mbox{ down to } 2 \\ \mbox{ } \mbox{ column } j \leftarrow \mbox{ column } j - A_{k-1} \cdot \mbox{ column } k \\ \mbox{ end for} \\ \mbox{end for} $ We get \begin{eqnarray*} \prod_{i < j} \left( a_{i} - a_{j} \right) & = & \det(V) \\ & = & \det \left( \left[ {P_{j-1}^{a_i}} \right]_{i,j} \right) \\ & = & \det \left( \left[ (j-1)! {{a_i} \choose {j-1}} \right]_{i,j} \right) \\ & = & \prod_{j=1}^{n} {(j-1)!} \cdot \left| \left[ {{a_i} \choose {j-1}} \right]_{i,j} \right| \\ & = & \prod_{k=1}^{n-1} {k!} \cdot D \\ \end{eqnarray*}where $ D = \left| \left[ {{a_i} \choose {j-1}} \right]_{i,j} \right| \in \mathbb{Z}$. Therefore $ \prod_{i < j} (j - i) = \prod_{k=1}^{n-1} {k!} \left| \prod_{i < j} \left( a_{i} - a_{j} \right) \right.$ For more details, see http://groups.google.com/group/sci.math/browse_thread/thread/f14b3c2b944cdc5d/9e3bdfc5da0ec445#9e3bdfc5da0ec445 any proof without using matrix? also the mathlink link provided by Zatex won't work as it's old..

calculus_riju wrote: YeOldeMan wrote: ZetaX wrote: Generalisation: Let $ a_1, a_2, ..., a_n$ be integers. Then $ \prod_{i < j} \left( a_{i} - a_{j} \right)$ is divisible by $ \prod_{k = 1}^{n - 1} k!$. In other words, $ \prod_{i < j} \left( \frac {a_{j} - a_{i}}{j - i} \right)$ is an integer. Proof:- etc. any proof without using matrix? also the mathlink link provided by Zatex won't work as it's old.. It works for me... Try this link: http://artofproblemsolving.com/community/c6h4858

This problem can be easily proved as $(a-b)(a-c)(a-d)(b-c)(b-d)(c-d)$ can be either divided by $4$ and $3$ since $gcd(4,3)=1$ Let $P$ be the product $(a-b)(a-c)(a-d)(b-c)(b-d)(c-d)$ Trivial Case: P=0 $\implies$ $12|(a-b)(a-c)(a-d)(b-c)(b-d)(c-d)$ Case 1: All four numbers $a,b,c,d$ are odd integeres then each of the six differences on the right-hand of (1) must be even. And so, in this case $P$ is divisible by $2^6$ and so it is divisible by $2^2 = 4$. Case 2 : All four numbers $a,b,c,d$ are even $a\equiv b\equiv\ c equiv\d \equiv 0 \pmod 2$ ; and so $a-b\equiv a-c\equiv a-d\equiv b-c \equiv b-d \equiv c-d \equiv 0 \pmod 2$ which implies that $P$ is divisble by $4$. Case 3 : Three numbers are odd and one of them is even..... we continue the trivial casework unless we prove that $2|P$ But for $P$ is divisible by $3$ we can see that $4$ integers $a,b,c,d$ give us by Pigeonhole Principle that at least two of them must be congruent $\pmod 3$. Consequently at least one six factors of $P$ must be $0 \pmod 3$ this proves that $3|P$ and we are done.

Let $t:=(a-b)(a-c)(a-d)(b-c)(b-d)(c-d)$. By CRT we only need to show $t$ is divisible by $3$ and $4$. Note that at least two of $a,b,c,d$ must be congruent modulo $3$. Thus $t\equiv 0\pmod 3$. In mod 4, suppose that $a,b,c,d$ are pairwise not congruent (since otherwise it's obvious) then $$t\equiv \pm (4-1)(4-2)(4-3)(3-2)(3-1)(2-1) \equiv 0 \pmod 4$$as desired.