Find the smallest positive integer $n$ having the property that for any $n$ distinct integers $a_1, a_2, \dots , a_n$ the product of all differences $a_i-a_j$ $(i < j)$ is divisible by $1991$.
Problem
Source:
Tags:
ssilwa
20.04.2013 00:31
Note that $1991 = 11 \cdot 181$ Therefore, $n$ must be at least $\boxed{182}$
Mathmick51
27.04.2021 12:17
Let $S = \prod_{1\leq i\leq j\leq n}(a_i-a_j).$ Note that $1991 = 11\cdot 181$. Therefore $S$ is divisible by $1991$ if and only if it is divisible by both $11$ and $181$. If $n\leq 181$ then we can take the numbers $a_1, a_2, ..., a_n $ from distinct congruence classes modulo $181$ so that $S$ will not be divisible by $181$. On the other hand, if $n\geq 182$ then according to the pigeonhole principle there always exist $a_i$ and $a_j$ such that $a_i-a_j$ is divisible by $181$ (and of course there exist $a_k$ and $a_l$ such that $a_{k}- a_{l}$ is divisible by $11$).