# Pigeonhole Principle Proof Verification

Let $$a_1 different integers. Prove that $$n!\Big|\prod_{1\leq i< j\leq n+1}{(a_j-a_i)}$$Here's my proof:

Let $$k\in\bigl\{1,2,\ldots,n\bigr\}$$. $$k and using the Pigeonhole Principle, there are $$0\leq i (but $$0\leq i is enough) such that $$a_i \equiv a_j\pmod{k}$$Thus, $$k\big|(a_j-a_i)$$Every $$k\in\bigl\{1,2,\ldots,n\bigr\}$$ satisfies this, and we are done.

Is the proof correct? I couldn't find a mistake myself but it seemed weird that the use of the Pigeonhole Principle had $$n+1$$ pigeons and only $$k$$ holes (when $$k$$ can be as little as $$1,2,3$$). Am I missing something?

• what do you mean by $k\in[n]$? What is $[n]$? Oct 18, 2020 at 22:35
• It's a symbol for $\bigl\{1,2,\ldots,n\bigr\}$. I thought about changing it before as I wasn't sure if it's a known symbol or not. I changed it now though.
– Guy
Oct 18, 2020 at 22:42
• It is very common, at least in combinatorics. Oct 18, 2020 at 22:48
• Then I guess $k<n+1$ is redundant. Oct 18, 2020 at 22:54
• Your proof is not sufficient : you need to prove that the pair $(i,j)$ such that $k\mid (a_j-a_i)$ is different for every $k$. Otherwise with the same reasoning, you could prove that $2^{10} | 2$. Oct 18, 2020 at 22:56

It seems to me that your argument shows that $$\prod_{1\leq i (you shouldn't allow $$i=j$$), which is actually a Vandermonde determinant, is divisible by all $$k\leq n$$.
This is not (yet) enough to conclude that $$n!$$ divides it: $$3\cdot4\cdot 5=60$$ has this property but is actually smaller than $$5!$$.
Given a prime $$p\leq n there are always $$\lfloor\frac n{p^k}\rfloor+1$$ elements among the $$a_i$$'s that give the same class modulo $$p^k$$ as long as $$p^k\leq n$$. This should account for the $$\lfloor\frac n{p}\rfloor+\lfloor\frac n{p^2}\rfloor+\lfloor\frac n{p^3}\rfloor+\cdots$$ factors of $$p$$ that occur in $$n!$$.