Product of $k$ distinct positive integers is divisible by its sum

249 Views Asked by At

Is it true that for every positive integer $k, n$ satisfying $2 \leq k \leq n$, there exist $n$ distinct positive integers such that the product of any $k$ integers selected from those $n$ integers is divisible by the sum of that $k$ integers?

It can be seen that the statement is true for $n = k$ with $k+1$ is not a prime (for example, choose $1, 2, ... , k$ , we have $k!$ is divisible by $1+2+..+k$), however I cannot proof or find any $n$ different positive integers that satisfy the statement with $n > k$ or $k+1$ is a prime.

2

There are 2 best solutions below

1
On

Suppose $a_1a_2\cdots a_k$ is not divisible by $a_1+\cdots+a_k$. You can fix it by choosing $d$ such that $(a_1d)(a_2d)\cdots(a_kd)$ is divisible by $a_1d+\cdots+a_kd=(a_1+\cdots+a_k)d$. So for each set of $k$ of your $n$ numbers there a multiplier $d$ that fixes it. Take any common multiple of all these values of $d$, and multiply all the $a_i$ by it, and you've fixed everything.

0
On

Fix positive integers $k,n$ with $2\le k \le n$.

Let $x_1,...,x_n$ be any $n$ distinct positive integers, and let $a$ be the product of all sums of $k$-element subsets of $\{x_1,...,x_n\}$.

Define $y_1,...,y_n$ by $y_i=ax_i$.

Then the product of any $k$ elements of $\{y_1,...,y_n\}$ is a multiple of $a^2$, hence is a multiple of the sum of those $k$ elements.