Maths Olympiad Prep

Library / /16 of 22

Number theory Difficulty 8.6 Shortlist Prove it Vietnam

A fractional number xx is called ‘pretty’ if it has finite expression in base bb numeral system where bb is a positive integer in [2;2022][2; 2022]. Prove that there exists finite positive integers n4n \ge 4 such that with every mm in (2n3,n)\left(\frac{2n}{3}, n\right), there is at least one pretty number among two numbers mnm\frac{m}{n-m} and nmm\frac{n-m}{m}.

Solution

Call a positive integer nn 'good' if there exists mm that mm in the interval (2n3,n)\left(\frac{2n}{3}, n\right) and mnm,nmm\frac{m}{n-m}, \frac{n-m}{m} is not pretty. Next, we will prove the following claims.

Claim 1. If nn is good then any multiple of nn is also good.

Proof. Consider a good number nn, there exists m(2n3,n)m \in \left(\frac{2n}{3}, n\right) such that nmm\frac{n-m}{m} and mnm\frac{m}{n-m} are not pretty. Hence, knkn is not a good number because knkmkm,kmknkm\frac{kn-km}{km}, \frac{km}{kn-km} are not pretty. \square

Claim 2. Consider a prime qq such that there exists a prime rr that 2022<r<q2022 < r < q. For all pairs (p,k)(p, k) with pp is prime and kk is positive integer such that pk>3q!p^k > 3 \cdot q!, number pkp^k is good.

Proof. Choose m=3q!m = 3 \cdot q! then 2pk3<pkm<pk\frac{2p^k}{3} < p^k - m < p^k. Assume that pkmm\frac{p^k - m}{m} is pretty then there exists b<2023b < 2023 and finite non-negative integers b0,b1,b2,,btb_0, b_1, b_2, \dots, b_t that
pkmm=i=0tbibi=b0bt+b1bt1++btbt, \frac{p^k - m}{m} = \sum_{i=0}^{t} \frac{b_i}{b^i} = \frac{b_0 b^t + b_1 b^{t-1} + \dots + b_t}{b^t},
which means mgcd(m,pk)bt\frac{m}{\text{gcd}(m, p^k)} \mid b^t.
Hence, all prime divisors of mm, except pp, are smaller than 20222022. On the other hand, mm is divisible for q,r>2022q, r > 2022 which implies that mm still has a prime divisor larger than 20222022 and differs from 20222022, which is a contradiction. Therefore, pkmm\frac{p^k - m}{m} is not pretty.
Continue, assume that mpkm\frac{m}{p^k - m} is pretty. Similarly, pkmgcd(m,pkm)\frac{p^k - m}{\text{gcd}(m, p^k - m)} only has prime divisors that are smaller than 20222022. Assume that there exists a prime number p1<2022p_1 < 2022 such that
p1pkmmp1pkp1=p, p_1 \mid \frac{p^k - m}{m} \longrightarrow p_1 \mid p^k \longrightarrow p_1 = p,
which means p<2022p < 2022 and there exists l>0l > 0 that
plgcd(m,pkm)=pkm. p^l \cdot \text{gcd}(m, p^k - m) = p^k - m.
Let m=pstm = p^s \cdot t where (p,t)=1(p, t) = 1, the above equation becomes
plps=pkpst or pkst=pl. p^l \cdot p^s = p^k - p^s \cdot t \text{ or } p^{k-s} - t = p^l.
Note that pks>1p^{k-s} > 1 then ppksp \mid p^{k-s}. We also have gcd(t,p)=1\text{gcd}(t, p) = 1 then gcd(pl,p)=1\text{gcd}(p^l, p) = 1 or l=0l = 0, which means pkmgcd(m,pkm)=1\frac{p^k - m}{\text{gcd}(m, p^k - m)} = 1 or pkmm<pk3p^k - m \mid m < \frac{p^k}{3}, which is a contradiction.
Hence, both mpkm\frac{m}{p^k - m} and pkmm\frac{p^k - m}{m} are not pretty, or pkp^k is good. \square

Back to the original problem, let NN be the number of the numbers that have the form pkp^k and not exceed Q=3q!Q = 3 \cdot q!. We will point out that all positive integers n>QNn > Q^N is good. Assume that the prime factorization of nn is as follows
n=i=1tpiαi. n = \prod_{i=1}^{t} p_i^{\alpha_i}.
If piαi<Qp_i^{\alpha_i} < Q for all iti \le t then nQtQNn \le Q^t \le Q^N, a contradiction.
Therefore, there exists an index ii such that piαi>Qp_i^{\alpha_i} > Q, which means piαip_i^{\alpha_i} is good by Claim 2. Hence, nn is the multiple of piαip_i^{\alpha_i} and nn is good by Claim 1. The problem is solved. \square

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 reproduced verbatim; metadata (topic, difficulty) added by this project.