A fractional number $x$ is called pretty if it has finite expression in base$-b$ numeral system, $b$ is a positive integer in $[2;2022]$. Prove that there exists finite positive integers $n\geq 4$ that with every $m$ in $(\frac{2n}{3}; n)$ then there is at least one pretty number between $\frac{m}{n-m}$ and $\frac{n-m}{m}$
Problem
Source: Vietnam TST 2022 P5
Tags: base system, combinatorics
02.05.2022 12:33
I can't get myself out of the idea to choose a prime number $m$ for $n$ large enough xD. Lemma 1 : For every $b$, a rational number $x$ with its simplest form of fraction $\frac{y}{z}$ is finite expression in base$-b$ iff $z$ has a prime factor not divides $b$. Proof: Easy to check! Lemma 2: For each integer $n$, we define $p(n)$ to be the smallest prime number that does not divide $n$ then $$\lim_{n\to \infty} \frac{p(n)}{n}=0$$Proof: We only need to prove $$\lim_{n\to \infty, n\; \text{is square-free}} \frac{p(n)}{n}=0 $$since $\frac{p(n)}{n}\leq \frac{p(n)}{Rad(n)}=\frac{p(Rad(n))}{Rad(n)}$. Let $p_k$ be the $k-$th prime number for any $k=1,2,\dots$, and for each square-free number $p_1\dots p_{k-1}<n<p_1\dots p_k$, $p(n)$ must be less than $p_{k+1}$ otherwise $p_1\dots p_k|n$. Thus $\frac{p(n)}{n}\leq \frac{p_k}{p_1\dots p_{k-1}}$. To finish, we prove $$\lim_{k\to \infty}\frac{p_k}{p_1\dots p_{k-1}}=0$$This is straightforward from the Bertrand's postulate, $p_k\leq 2p_{k-1}$ so $$\frac{p_k}{p_1\dots p_{k-1}} \leq \frac{2}{p_1\dots p_{k-2}} \to 0 $$$\hfill \blacksquare$ Now back to the problem, by the Chinese Remainder Theorem and the Dirichlet Theorem for distribution of prime in arithmetic progressions, for $n$ large enough, there is a prime number $p\in (\frac{2n}{3}, n)$ such that $p\equiv 1 \pmod{2022!}$ and $p \equiv n \pmod{p(2022!n)}$ ($n\gg p(2022!n)$ by Lemma 2 ). Both $\frac{p}{n-p}$ and $\frac{n-p}{p}$ are in their simplest form and both $n-p$ and $p$ have a prime factor greater than 2022. This complete our proof. $\hfill \square$