Problem

Source: 2024 Chinese TST P3

Tags: number theory, 2024 CTST



Given positive integer $M.$ For any $n\in\mathbb N_+,$ let $h(n)$ be the number of elements in $[n]$ that are coprime to $M.$ Define $\beta :=\frac {h(M)}M.$ Proof: there are at least $\frac M3$ elements $n$ in $[M],$ satisfy $$\left| h(n)-\beta n\right|\le\sqrt{\beta\cdot 2^{\omega(M)-3}}+1.$$Here $[n]:=\{1,2,\ldots ,n\}$ for all positive integer $n.$ Proposed by Bin Wang