Find distinct positive integers $n_1<n_2<\dots<n_7$ with the least possible sum, such that their product $n_1 \times n_2 \times \dots \times n_7$ is divisible by $2016$.
Problem
Source: RMO Maharashtra and Goa 2016, P1
Tags: inequalities, number theory, construction
12.10.2016 21:46
1,2,3,4,6,7,8
29.09.2017 12:18
The choice of distinct positive integers n1, n2, · · · , n7 with the smallest possible sum is (1, 2, · · · , 7), with sum 1 + 2 + .. + 7 = 28. However, we see that 1 × 2 × · · · × 7 = 7! = 5040 = 2016 × 5/2 . This means the above product is not divisible by 2016; it is falling short by just one factor of 2. Hence, we will have to choose at least one number in our set, that is larger than 7. The smallest such choice available is 8; which will provide us with the required additional factor of 2. Now, to decide which number to replace: We cannot replace 7 or 6, because both contain prime factors that are required for the product to be divisible by 2016. However, we observe that the number 5 is not needed, since 5 and 2016 are coprime. So we can remove 5 and put 8 in our set. Hence we get the answer as (1, 2, 3, 4, 6, 7, 8); with sum 31; and product divisible by 2016.
03.10.2018 22:58
Quite an easy problem. Notice that $2016= 2^5\cdot 3^2\cdot 7$. Hence conclude that $1,2,3,4,6,7,8$ is the desired tuple. We only need to consider the cases when sum is $29$ or $30$, which is not lengthy.
31.10.2024 14:01
1,2,3,4,6,7,8 Easy tbh