Given are real $y>1$ and positive integer $n \leq y^{50}$ such that all prime divisors of $n$ do not exceed $y$. Prove that $n$ is a product of $99$ positive integer factors (not necessarily primes) not exceeding $y$.
Problem
Source: Tuymaada 2021/J6
Tags: number theory
31.07.2021 06:33
i dont understand the problem ?
31.07.2021 06:45
You need to write n as a product of 99 positive integers (can be 1) and all of them are not greater than y.
31.07.2021 06:53
Justanaccount wrote: You need to write n as a product of 99 positive integers (can be 1) and all of them are not greater than y. ok, that's hard
31.07.2021 07:02
Let the prime divisors of $n$ be $p_1 \geq p_2 \geq \cdots \geq p_k$. We now distribute the primes into 99 boxes $B_1, B_2, \cdots B_{99}$ using the following algorithm: Starting with prime $p_1$, distribute each prime we look at into the box with the smallest product so far (take the product of numbers in an empty box to be $1$). Now we show that this algorithm works. Suppose that it fails, i.e. a prime $p$ cannot be added to any box. Letting the box $B_i$ have product of factors $a_i$, this is equivalent to having $a_i > \frac{y}{p}$ for all indices $i=1,2,\cdots,99$. Multiplying the $a_i$ together, we obtain $$\left(\frac{y}{p}\right)^{99} < a_1 a_2 \cdots a_{99} \leq \frac{n}{p} \leq \frac{y^{50}}{p}$$where the second inequality holds because the product of the factors does not include the factor of $p$, which means that the product is at most $\frac{n}{p}$. Thus, $$y^{49} < p^{98} \quad \Rightarrow \quad p > \sqrt{y}$$ But since $a_i \geq p$ for all $i$ (every pile contains at least 1 prime greater than $p$, otherwise the pile would have product $1$ and we could add $p$ to it), this means that $$n \geq a_1 a_2 \cdots a_{99} p > p^{100} > y^{50}$$ Contradiction.
31.07.2021 07:05
assume we can't. Let k be the minimun number such that $n$ is a product of k positive integer factors not exceeding $y$ then $k \geqslant 100$, \[n = {a_1}{a_2}..{a_k}\]The key: $a_ia_j>y$ then as $k>99$ lead to $n> y^{50} $