Maths Olympiad Prep

Library / /6 of 18

Number theory Difficulty 6.4 National olympiad Prove it China

Determine the smallest real number λ\lambda with the following property: every positive integer nn can be written as a product n=x1x2x2023n = x_1x_2\cdots x_{2023}, with each xix_i either a prime number or a positive integer that is less than or equal to nλn^\lambda.

Solutions — 4

Solution 1

The number λ\lambda is 11012\frac{1}{1012}.
The minimal such λ\lambda is 11012\frac{1}{1012}.
To see that λ<11012\lambda < \frac{1}{1012} does not work, we take n=p2024n = p^{2024} for some prime number pp. Then when writing nn as the product of 20232023 integers, at least one of the integers is pαp^\alpha for some α2\alpha \ge 2 (which is not a prime number); then pαp2=n11012>nλp^\alpha \ge p^2 = n^{\frac{1}{1012}} > n^\lambda.
Now we prove that λ=11012\lambda = \frac{1}{1012} satisfies the condition of the problem. To start, we write nn as the product of its prime factors n=p1p2prn = p_1p_2\cdots p_r (allowing some pip_i's to be equal), where we order the primes so that p1p2p_1 \ge p_2 \ge \cdots.
Now starting from p1p_1, let r11r_1 \ge 1 be the smallest integer such that x1=p1p2pr1>n1/2024x_1 = p_1p_2\cdots p_{r_1} > n^{1/2024}. Note that this x1x_1 satisfies the condition of the problem, namely, if r1=1r_1 = 1, x1x_1 is a prime number; otherwise r12r_1 \ge 2, then we must have p1n1/2024p_1 \le n^{1/2024}. This means that prn1/2024p_r \le n^{1/2024}; so
x1=(p1p2pr1)prn1/2024n1/2024=n1/1012, x_1 = (p_1p_2\cdots p_{r-1})p_r \le n^{1/2024} \cdot n^{1/2024} = n^{1/1012},
where the first inequality holds by minimality of r1r_1.
Next, let r2r1+1r_2 \ge r_1 + 1 be the smallest integer such that x2=pr1+1pr2>n1/2024x_2 = p_{r_1+1}\cdots p_{r_2} > n^{1/2024}. The same argument as above shows that either x2x_2 is a prime number or x2n1/1012x_2 \le n^{1/1012}.
Continue this process. If we run out of pip_i's before reaching x2023x_{2023}, then set the rest of xjx_j to be 11, and then n=x1x2x2023n = x_1x_2\cdots x_{2023} gives the needed decomposition. Otherwise, we have constructed x1,x2,,x2022x_1, x_2, \dots, x_{2022} satisfying the condition of the problem (and that each xi>n1/2024x_i > n^{1/2024} by construction), then we must have
x2023:=nx1x2022<n(n1/2024)2022=n1/1012. x_{2023} := \frac{n}{x_1 \cdots x_{2022}} < \frac{n}{(n^{1/2024})^{2022}} = n^{1/1012}.
The decomposition n=x1x2x2023n = x_1x_2\cdots x_{2023} satisfies the conditions of the problem.

Solution 2

The proof for that λ<11012\lambda < \frac{1}{1012} does not work is the same as Solution 1. We prove that λ=11012\lambda = \frac{1}{1012} satisfies the requirement. Let n=p1p2prn = p_1p_2\cdots p_r be the prime factorization of nn (where p1p2prp_1 \ge p_2 \ge \cdots \ge p_r). For i=1,2,,1012i = 1, 2, \dots, 1012, define
yi=1jrji(mod1012)pj. y_i = \prod_{\substack{1 \le j \le r \\ j \equiv i \pmod{1012}}} p_j.
Then y1y2y1012y_1 \ge y_2 \ge \cdots \ge y_{1012} and y1y2y1012=ny_1y_2\cdots y_{1012} = n.
If y1n1/1012y_1 \le n^{1/1012}, then let x1,,x2023x_1, \dots, x_{2023} be y1,y2,,y1012y_1, y_2, \dots, y_{1012} plus 10111011 ones.
If y1>n1/1012y_1 > n^{1/1012}, since y1012n1/1012y_{1012} \le n^{1/1012}, suppose yk>n1/1012yk+1y_k > n^{1/1012} \ge y_{k+1}, then 1k10111 \le k \le 1011.
For 1ik1 \le i \le k, we have
yipiy1012n1/1012. \frac{y_i}{p_i} \le y_{1012} \le n^{1/1012}.
Let x1,x2,,x2023x_1, x_2, \dots, x_{2023} be y1p1,,ykpk,yk+1,,y1012,p1,,pk\frac{y_1}{p_1}, \dots, \frac{y_k}{p_k}, y_{k+1}, \dots, y_{1012}, p_1, \dots, p_k and 1011k1011 - k ones.

Solution 3

The proof for that λ<11012\lambda < \frac{1}{1012} does not work is the same as Solution 1. We prove that λ=11012\lambda = \frac{1}{1012} satisfies the requirement. Express nn as n=x1x2x2023n = x_1x_2\cdots x_{2023} such that

x1+x2++x2023x_1 + x_2 + \cdots + x_{2023} is minimized. (Since there are a finite number of ways to express this, such a representation must exist.) Next, we prove that every xix_i greater than n1/1012n^{1/1012} is a prime number.
We use proof by contradiction. Suppose x1>n1/1012x_1 > n^{1/1012} and x1x_1 is not a prime number. Let x1=abx_1 = ab where a>1a > 1 and b>1b > 1, and without loss of generality, assume aba \ge b. Since
x2x2023=nx1<x11012x1=x11011=(x1)2022a2022, x_2 \cdots x_{2023} = \frac{n}{x_1} < \frac{x_1^{1012}}{x_1} = x_1^{1011} = (\sqrt{x_1})^{2022} \le a^{2022},
there exists an xi<ax_i < a. Assume without loss of generality that x2<ax_2 < a.
Express nn as n=abx2x3x2023n = a \cdot b \cdot x_2 \cdot x_3 \cdots x_{2023}. Since
(ab+x2+x3++x2023)(a+bx2+x3++x2023)=(b1)(ax2)>0, (ab + x_2 + x_3 + \cdots + x_{2023}) - (a + bx_2 + x_3 + \cdots + x_{2023}) = (b-1)(a-x_2) > 0,
the expression n=x1x2x2023n = x_1x_2\cdots x_{2023} is not the one that minimizes x1+x2++x2023x_1+x_2+\cdots+x_{2023}, which is a contradiction!
Therefore, λ=11012\lambda = \frac{1}{1012} satisfies the problem's conditions.

Solution 4

The proof for that λ<11012\lambda < \frac{1}{1012} does not work is the same as Solution 1. We prove that λ=11012\lambda = \frac{1}{1012} satisfies the requirement. Let n=p1p2pkn = p_1p_2\cdots p_k, where p1p2pkp_1 \ge p_2 \ge \cdots \ge p_k are all the prime factors of nn.
If k2023k \le 2023, then express nn as the product of p1,p2,,pkp_1, p_2, \cdots, p_k and 2023k2023-k ones.
If k>2023k > 2023, first express nn as n=p1p2pkn = p_1p_2\cdots p_k. Then, perform the following operation: in each step, select the smallest two factors and combine them into their product, continue this process until only 20232023 factors remain. In each step, as the current number of factors is 2024\ge 2024, the product of the smallest two numbers will be n2/2024=n1/1012\le n^{2/2024} = n^{1/1012}. This indicates that every "composite" number formed after each operation is n1/1012\le n^{1/1012}.
Combining this with the fact that the initial numbers are primes, it can be concluded that when the operation ends, the 20232023 factors are either prime or do not exceed n1/1012n^{1/1012}. Hence, λ=11012\lambda = \frac{1}{1012} satisfies the conditions of the problem.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.