Positive integers $d_1$, $d_2$, $\ldots$, $d_n$ divide $1995$. Prove that, for some $i,j$, the numerator of $\dfrac{d_i}{d_j}$ is at least $n$.

356 Views Asked by At

(Probably Correct Statement) Distinct positive integers $d_1$, $d_2$, $\ldots$, $d_n$ divide $1995$. Prove that, for some indices $i,j\in\{1,2,\ldots,n\}$, the numerator of the reduced fraction $\dfrac{d_i}{d_j}$ is at least $n$.

Well, the 16 divisors of 1995 are 1 3 5 7 15 19 21 35 57 95 105 133 285 399 665 1995. So, everything starting from 19/1(or, if you want quotient to be greater than 1, from 95/3) suits. But how to make it more general? enter image description here

2

There are 2 best solutions below

0
On BEST ANSWER

Claim: If $p_1,p_2,\dots,p_m$ are distinct primes with $p_i\geq 2^{i}-1$, then for any set of distinct divisors $d_1<d_2<\dots<d_n$ of $N=p_1p_2\cdots p_m$, there is some fraction $\frac{d_i}{d_j}$ with reduced numerator $\geq n$.

This gives your result since $1995=3\cdot 5\cdot 7\cdot 19$.

Proof:

We will prove by induction on $m$.

If $m=1$, then all divisors are $1,p_1$. Since $p_1\geq 2$ you are done.

If true for $m$, then take $p_1,\dots,p_{m+1}$ with $p_i\geq 2^{i}-1$.

If none of $d_1,\dots,d_n$ are divisible by $p_{m+1}$, then it reduces to the case of $m$.

If all of the $d_i$ are divisible by $p_{m+1}$, then we can take the set of distinct divisors $\frac{d_1}{p_{m+1}},\dots,\frac{d_n}{p_{m+1}}$ of $p_1\cdot p_m$, and reduce to the case of $m$.

If $d_i$ is divisible by $p_{m+1}$ and $d_j$ is not, then $\frac{d_i}{d_j}$ has $p_{m+1}$ as a factor of the numerator. So that handles the cases when $n\leq p_{m+1}$. But if $n> p_{m+1}\geq 2^{m+1}-1$, then, since there are exactly $2^{m+1}$ divisors of $N$, $n=2^{m+1}$ and $d_1,\dots,d_n$ is all of the divisors. In particular, one of the $d_i=1$ and another $d_j=N$, and since $\{d_1,\dots,d_n\}\subseteq \{1,\dots,N\}$, you have $N\geq n$.

0
On

All of the $16$ divisors of $1995$ are of the form $3^{\delta_1}5^{\delta_2}7^{\delta_3}19^{\delta_4}$ where each exponent is equal to $0$ or $1$.

There are $8$ divisors of the form $19\cdot3^{\delta_1}5^{\delta_2}7^{\delta_3}$ and $8$ divisors of the form $3^{\delta_1}5^{\delta_2}7^{\delta_3}$.

►All set of divisors containing $n\ge9$ elements should contain at least one element of each of the two forms in which case we choose as numerator a factor of $19$ and as denominator a divisor coprime with it. This end the proof for $n\ge9$ because $19\gt 16$.

It remains the proof for $n=1,2,3,4,5,6,7,8$.

► For $n=8$ if all the divisors are multiples of $19$ we choose, for example the quotient $\dfrac{19\cdot3\cdot5}{19\cdot7}$ For all other set of $8$ elements containing a multiple of $19$ and a divisor coprime with $19$ we choose as numerator the multiple of $19$ and as denominator the divisor coprime to $19$

►We can now to consider just divisors of the form $3^{\delta_1}5^{\delta_2}7^{\delta_3}$.

For $n=8$ we choose $\dfrac{d_i}{d_j}=\dfrac{7\cdot3\cdot5}{5}$ (there are other examples).

For $n=7$ one of the $8$ involved divisors must lack. If it is the largest we choose $\dfrac{d_i}{d_j}=\dfrac{7\cdot5}{3}$ and if not we choose as numerator the mentioned largest (there are other examples).

For $n=6$ two of the $8$ concerned divisors should lack. If its are the two largest we choose $\dfrac{d_i}{d_j}=\dfrac{7\cdot3}{5}$ and if not we choose $\dfrac{d_i}{d_j}=\dfrac{7\cdot3\cdot5}{5}$(there are other examples).

And so on for $n=5,4,3,2$ and the trivial case $n=1$.