Among $26$ divisors of $120^4$ there is a pair that one of them divides the other

72 Views Asked by At

Given $26$ arbitrary divisors of $120^4$ ,using pigeon hole principle prove that there is a pair that one of them divides the other.

I considered prime decomposition of $120^4$ as $2^{12}\times 3^4 \times 5^4 $.It's seen that it has a total of $325$ divisors . So each divisor is of the form: $2^{a}\times 3^b \times 5^c $ such that: $a\leq 12,b\leq 4 , c\leq 4$.But I can't detect holes...

1

There are 1 best solutions below

2
On BEST ANSWER

Since I have provided a sufficient hint for this problem, I just want to show that it is possible to pick $25$ divisors of $120^4$ in such a way that none of the chosen numbers divides another. The set $S$ consisting of $25$ numbers of the form $$2^{12-a-b}\,3^a\,5^b$$ for $a,b\in\{0,1,2,3,4\}$ has the required property.

In general, suppose that an integer $n$ is of the form $p_1^{k_1}\,p_2^{k_2}\,\cdots\,p_r^{k_r}$, where $p_1<p_2<\ldots<p_r$ are prime natural numbers and $k_1,k_2,\ldots,k_r$ are positive integers. Let $D_n$ denote the partially ordered set consisting of (positive) divisors of $n$, equipped with the divisibility ordering (i.e., for $x,y\in D_n$, $x\preceq y$ if $x\mid y$). Clearly, any antichain of $D_n$ is of size at most $$\nu_n:=\min_{j\in\{1,2,\ldots,r\}}\,\prod_{i\in\{1,2,\ldots,r\}\setminus\{j\}}\,\left(k_i+1\right)\,.$$ If there exists $j\in\{1,2,\ldots,r\}$ such that $k_j \geq \sum\limits_{i\in\{1,2,\ldots,r\}\setminus\{j\}}\,k_i$, then $\nu_n$ is the width of $D_n$. However, this upper bound is very weak (e.g., $\nu_{p_1p_2\cdots p_r}=2^{r-1}$, but the width of $D_{p_1p_2\cdots p_r}$ is $\displaystyle\binom{r}{\lfloor r/2\rfloor}$). In fact, $\displaystyle\binom{r}{\lfloor r/2\rfloor}$ is a (quite weak) lower bound for the width of $D_n$ if $n$ has $r$ distinct prime factors (i.e., excluding multiplicities). For an exact algorithm to compute the width of $D_n$, see How do you calculate the width of the Poset Lattice of Divisors?.