This works - I don't know why

Okay, let's see.

Thing to understand 1: If two integers $a,b$ give the same remainder when divided by another integer $n$ . Then $a-b$ is divisible by $n$ .

First we try to minimize the size of the prime factors(and also their powers) that can come up while taking differences For example, $11$ may come up, but it isn't necessary. If we write $8$ numbers, all of which give different remainders with $11$ , we can see that $11$ will not be a factor in our product. The same argument can be applied to all primes and prime powers greater than $11$ to understand that these are not necessarily a factor of our product.

Now let us come to $7$ . We want to find out the minimum number of times that $7$ can occur. Consider the remainders given by numbers when divided by $7$ : $(0,1,2,3,4,5,6)$ . Now, we take seven numbers, each giving a different remainder with seven and make our set. What will we do for the eighth number? A little thinking tells us that we have to choose a number which gives remainder same as one of the numbers we have chosen earlier. This means that $7$ must be a factor of the product of differences. And $7^1$ is the largest power of seven that must necessarily be present in all products.

This logic or way of thinking is called pigeonhole principle. Where the numbers $a_0, a_1, \cdots a_7$ can be thought of as pigeons, and the remainders given by these numbers when divided by a prime are the holes. We have to map each pigeon to a hole.

Similar arguments can be applied for each of the primes $5,3,2$ to see that:

$5^3$ must be a factor.(refer comments for explanation)

$3^7$ must be a factor.

$2^{16}$ must be a factor. Explanation: If we proceed using similar arguments as in the case for $5$ , we will get that $2^{12}$ is a sure divisor of our product. But there is a catch here. It turns out that this is not the largest power of two that divides all products. This arises due to the fact that a few numbers in the product are divisible by $4$ (this is the only prime power which is present in the given range). So we proceed with $4$ as we did with the other prime factors, and see that four of the even numbers we counted are actually divisible by $4$ , hence, we can further push up the power of two to $2^{16}$

Hence the product is always divisible by $2^{16}3^75^37^1=\boxed{125411328000}$

Otherwise, you can just go with your intuition and take eight consecutive numbers like $1,2,3,4,5,6,7,8$ and you are done!

Thank you.

There are a few nice tricks involved in this problem.

If we let $a _ i = i$ , then we get that $P = 125411328000$ , which gives us an upper bound on the answer. The challenge is to show that this is indeed the solution.

Observe that $125411328000 = 2 ^ { 16 } \times 3^{ 7} \times 5^{3} \times 7 ^ 1$ . We will work via the prime factors.

The cases of $p = 3, 5, 7$ are much easier, and we will do them together. For each set of $a_i$ , let $b_1$ be the number of $a_i$ which leave a remainder of $i$ when divided by $p$ . Similarly, define $b_2, \ldots b_p$ .

Then, let $s_p = { b_1 \choose 2 } + { b_2 \choose 2 } + \ldots { b_p \choose 2 }$ . We clearly have $p ^ { s_p} \mid P$ .

How do we minimize $s_p$ subject to $\sum b_i = 8$ ? Well, by Jensens's inequality, since ${ b \choose 2 } = \frac{1}{2} \times b \times (b-1)$ is a quadratic, hence the minimum occurs when all of them are equal. However, this is not great, because it would give us a non-integer value of $s_p$ . Instead, we use a method called smoothing , to show that $s_p$ is minimized when all of the $b_i$ values differ by at least 1. In particular, we have

$s_ 7 = { 1 \choose 2 } + { 1 \choose 2 } + { 1 \choose 2 } + { 1 \choose 2 } + { 1 \choose 2 } + { 1 \choose 2 } + { 2 \choose 2 } = 1$ $s_5 = { 1 \choose 2 } + { 1 \choose 2 } + { 2 \choose 2 } + { 2 \choose 2 } + { 2 \choose 2 } = 3$ $s_3 = { 3 \choose 2 } + {3 \choose 2 } + { 2 \choose 2 } = 7$

Now, if we tried the same for $p = 2$ , we will simply get $s_2 = { 4 \choose 2 } + { 4 \choose 2 } = 12.$ However, we need $2 ^ {16} \mid P$ , instead of just $2 ^ {12}$ . How do we account for the additional powers of 2? Those arise when $4 \mid a_i - a_j$ , where we would only have counted them once, but they should yield 2 to the count.

As such, we use the trick of "counting the total powers of 2, by counting each contribution once". For example, when finding the number of powers of 2 in $100 !$ , we take $\lfloor \frac { 100 } { 2 } \rfloor + \lfloor \frac { 100 } { 4 } \rfloor + \lfloor \frac { 100 } { 8 } \rfloor + \lfloor\frac { 100 } { 16 } \rfloor + \ldots$ . This way, the contribution of 24 to the power of 2 comes in 3 places, namely $\lfloor \frac { 100 } { 2 } \rfloor, \lfloor \frac { 100 } { 4 } \rfloor, \lfloor \frac { 100 } { 8 } \rfloor$ .

So, let's count the number of " $2^2$ terms" which will appear. By the above argument, we have

$s_4 = { 2 \choose 2 } + { 2 \choose 2 } + { 2 \choose 2 } + { 2 \choose 2 } = 4 .$

Hence, the number of powers of 2 will be $s_2 + s_4 = 16$ . Thus, we can conclude that $2 ^ {16 } \mid P$ .

Now, can you generalize to the case of $n$ integers? Be careful about when we have to use the "2" trick, and when the simple cases of "3, 5, 7" will work. How do you know?

I'm serious about not knowing why this works.

A more serious answer can probably be found in Professor Bhargava's article . (Theorem 3)

However the following code does a good job of showing that it works.

Mathematica Code:

1
2
3

Times @@ ((#[[1]] - #[[2]]) & /@ 
    Subsets[RandomInteger[1000, 8], {2}])/
 Product[i!, {i, 7}] // IntegerQ

So, the answer is actually

1

Product[i!, {i, 7}] 

I'll just leave this here.......

Note that $a-b\equiv 0\pmod{n} \implies a \equiv b \pmod{n}$ .

We can ignore negative integer factors of $P$ because we are looking for the largest number which always divides $P$ .

For $n=k$ , there are $k$ possible equivalencies $\pmod{k}$ , namely $0, 1, ... k-1$ . Since there are 8 integers $a_{0\leq i \leq 7}$ , if $k\geq8$ , there are always enough possible equivalencies that each $a_{0\leq i \leq 7}$ can be unique $\pmod{k}$ . However, when $k<8$ , there are not enough equivalencies so that each integer $a_{0\leq i \leq 7}$ can be unique $\pmod{k}$ . This involves the Pigeonhole Principle, which indicates that there are at least $8-k$ duplicates, i.e. at least $8-k$ pairs of integers such that $a_i \equiv a_j \pmod{k} \implies k \vert (a_i - a_j)$ . $P$ has $8-k$ factors of $k$ , so $k^{8-k}$ divides $P$ . This is true for all $k<8$ .

Then, $P$ is always divisible​ by ${\displaystyle \prod_{k=1}^{7} k^{8-k} } = {\displaystyle \prod_{k=1}^{7} k! } = 125411328000$

This can be easily generalized for $m$ integers $a_{0\leq i \leq m-1}$ , using the same argument as above: $P$ is always divisible by ${\displaystyle \prod_{k=1}^{m-1} k^{m-k} } = {\displaystyle \prod_{k=1}^{m-1} k! }$