grandes-ecoles 2025 Q18

grandes-ecoles · France · centrale-maths1__official Number Theory GCD, LCM, and Coprimality
For all $n \in \mathbb { N } ^ { * }$, we denote by $d _ { n }$ the LCM of the natural integers between 1 and $n$, in other words: $d _ { n } = \operatorname { LCM } ( 1,2 , \ldots , n )$. For all prime number $p$, we denote by $k _ { p }$ the largest natural integer such that $p ^ { k _ { p } } \leqslant n$.
For all prime number $p$, show that $k _ { p } = \left\lfloor \frac { \ln ( n ) } { \ln ( p ) } \right\rfloor$. Deduce that $d _ { n } \leqslant n ^ { \pi ( n ) }$.
For all $n \in \mathbb { N } ^ { * }$, we denote by $d _ { n }$ the LCM of the natural integers between 1 and $n$, in other words: $d _ { n } = \operatorname { LCM } ( 1,2 , \ldots , n )$. For all prime number $p$, we denote by $k _ { p }$ the largest natural integer such that $p ^ { k _ { p } } \leqslant n$.

For all prime number $p$, show that $k _ { p } = \left\lfloor \frac { \ln ( n ) } { \ln ( p ) } \right\rfloor$. Deduce that $d _ { n } \leqslant n ^ { \pi ( n ) }$.