0

Let $a_1,a_2,a_3,$ and $a_4$ be integers. Show that the product $\prod_{1 \leq i<j \leq 4}(a_i-a_j)$ is divisible by $12$

$\prod_{1 \leq i<j \leq 4}(a_i-a_j)=(a_1-a_2)(a_1-a_3)(a_1-a_4)(a_2-a_3)(a_2-a_4)(a_3-a_4)$ The hint is to consider the pigeonhole principle but I'm not seeing how to assign my boxes or pigeons. I know that the product of $4$ consecutive integers would be divisible by $24$ and also by $12$ but is there a way to apply the pigeonhole principle as well?

Could I consider my boxses as the remainders of $12$ and then my pigeons as all the combinations of subtracting those numbers and multiplying them to get a factor of $12$. So if the difference of any of those numbers is divisible by $12$ we are done or if multiplying any of those differences is divisible by $24$ we are done. Find some way to get more pigeons then boxses this way?

HighSchool15
  • 2,061
  • 14
  • 35
  • Look first by parity. You could have 2 odd, 2 even, or 1 odd, 3 even, or... In any case, the product will be divisible by 4. Now look at them mod 3, two of them will be the same, so ... – orangeskid Sep 20 '17 at 04:07
  • 2
    Among any four numbers, at least two of them must leave the same remainder on division by 3 (since there are only three remainders possible and we have 4 numbers). Thus the difference is a multiple of 3. Among four numbers if two leave the same remainder when divided by 4 we are done. Otherwise they all leave different remainders. Thus they must be 0,1,2,3. Thus we have two even numbers among their differences. Thus the product is also a multiple of 4. –  Sep 20 '17 at 04:09
  • @Muralidharan: that should be an answer. – Ross Millikan Sep 20 '17 at 04:10
  • Thanks, posted as an answer. –  Sep 20 '17 at 04:11

1 Answers1

4

Among any four numbers, at least two of them must leave the same remainder on division by 3 (since there are only three remainders possible and we have 4 numbers). Thus the difference is a multiple of 3. Among four numbers if two leave the same remainder when divided by 4 we are done. Otherwise they all leave different remainders. Thus they must be 0,1,2,3. Thus we have two even numbers among their differences. Thus the product is also a multiple of 4.