# A delightful division

Let $$a_1,a_2,\dots,a_8$$ be arbitrary integers (i.e. elements of $$\mathbb{Z}$$) and consider the product of their pairwise differences: $\prod_{i\lt j}(a_i-a_j)\text{.}$ What is the largest integer that always divides the above product, independent of the choice of elements $$a_1,a_2,\dots,a_8$$? Prove your answer.

Source: Brilliant.

The answer is $$125\,411\,328\,000$$.

This problem can be solved by a clever application of the pidgeon hole principle. Suppose $$P$$ is equal to the product mentioned above, for arbitrary integers $$a_1,a_2,\dots,a_8$$. We can ask ourselves: how many times can we consecutively divide $$P$$ by $$2$$?
The integers $$a_i$$ can either be even or odd, and if two such integers are of the same type, we know their difference is divisable by $$2$$. If, let's say, $$5$$ integers are odd, we know that $$\binom{5}{2}=10$$ pairs in the product consist of two odd integers, thus with a difference divisible by $$2$$. The other $$3$$ integers would be even, leading up to $$\binom{3}{2}=3$$ differences divisible by $$2$$. As we do not know how many integers are even or odd, we calculate the least possible number of pairs of numbers of the same parity: $\min\left\{\binom{k}{2}+\binom{8-k}{2}\|k\in\{0,1,2,\dots,8\}\right\}=\binom{4}{2}+\binom{4}{2}=12\text{.}$ Next, we can look at the number of times we can consecutively divide $$P$$ by $$3$$. For this, we look at the residual classes of the eight integers, modulo $$3$$. If two integers share the same residual class, we know their difference is divisable by $$3$$. Analogous to the arguments above, the minimal number of such pairs is equal to $\min\left\{\binom{k}{2}+\binom{l}{2}+\binom{m}{2}\|k+l+m=8\right\}=\binom{3}{2}+\binom{3}{2}+\binom{2}{2}=7\text{.}$ Intuïtively, we consider all next prime numbers below $$8$$, i.e. $$5$$ and $$7$$, and realise that $$P$$ must be divisable by $$5^3$$ and $$7$$, respectively. As prime numbers are obviously pairwise coprime, we can conclude that $$P$$ must be divisable by $$2^{12}\cdot3^7\cdot5^3\cdot7$$.
However, we have yet to consider the divisibility of $$P$$ by $$4$$, as this is a prime power. We find at least $$4$$ pairs of numbers sharing the same residual class modulo $$4$$. For each of these pairs, the difference of the numbers is not only divisible by $$2$$ (which we have already taken into account), but also by $$4$$. This means $$P$$ is not only divisible by $$2^{12}$$, but $$2^{16}$$. In conclusion, we know that $$P$$ is divisable by $$2^{16}\cdot3^7\cdot5^3\cdot7=125\,411\,328\,000$$.
By taking specific integers $$a_i=i$$, we see that all the above minima are met. You can also check numerically that $$\prod_{i,j=1; i\lt j}^8(i-j)=2^{16}\cdot3^7\cdot5^3\cdot7$$. This implies that no integer larger than this will divide $$P$$, independent of the choice of $$a_1,a_2,\dots,a_8$$.

Remarks? Want to submit your own solution? Don't hesitate to send me an email!