Западно-Китайская математическая олимпиада, 2018 год

Даны простое целое число $p$ и составное целое число $c$. Докажите, что найдутся положительные целые числа $m$ и $n$, удовлетворяющие условию \[0 < m-n < \frac{\text{НОК}\left(n+1, n+2, \ldots , m\right)}{\text{НОК}\left(n, n+1, \ldots , m-1\right)} =p^{c} .\]

Комментарий/решение

НОК - это произведение всех входящих в разложения простых множителей, взятых с их максимальными показателями степеней. Переобозначим простое как $p_{0}$

Воспользуемся преобразованной формулой Лежандра(которая для факториала):

Степень простого числа в НОК : $v_p\big(\text{НОК}(a, \dots, b)\big) = k_{\max}$

$k_{\max} = \max \left\{ k \in \mathbb{N} \;\middle|\; \Delta_k(a,b) \ge 1 \right\}$

Разность слагаемых Лежандра : $\Delta_k(a,b) = \left\lfloor \frac{b}{p^k} \right\rfloor - \left\lfloor \frac{a-1}{p^k} \right\rfloor$

или $$v_p\big(\text{НОК}(a, \dots, b)\big) = \max \left\{ k \in \mathbb{N} \;\middle|\; \left\lfloor \frac{b}{p^k} \right\rfloor - \left\lfloor \frac{a-1}{p^k} \right\rfloor \ge 1 \right\} \ \ (1)$$

Если взять в качестве $m=p_{0}^{k+c} ,n=p_{0}^{k+c}-p_{0}^k=p_{0}^k(p_{0}^c-1)$ где очевидно выполняется $m>n$ , если подставит этот набор :

$$\Delta_{k+c}(n+1,m) = \left\lfloor \frac{p_0^{k+c}}{p_{0}^{k+c}} \right\rfloor - \left\lfloor \frac{p_0^k (p_0^c - 1)}{p_{0}^{k+c}} \right\rfloor = 1 - 0 = 1 \geq 1$$

$$\Delta_{k}(n,m-1) = \left\lfloor \frac{p_0^{k+c}-1}{p_{0}^{k}} \right\rfloor - \left\lfloor \frac{p_0^k (p_0^c - 1)-1}{p_{0}^{k}} \right\rfloor = p_{0}^c - (p_{0}^c-1)= 1 \geq 1$$

То есть соотношение НОК-ов этих дробей равна $p^{k+c-k} \cdot N = p^c \cdot N$

Теперь покажем, что $N = 1$. Выберем такое $k$, чтобы выполнялось неравенство $p_0^k > M$, где $M = q^t$ — наибольшая примарная степень в каноническом разложении числа $p_0^c - 1$ на простые множители, тогда:

$$p_{0}^k(p_{0}^c-1)+1 < p_{0}^k(p_{0}^c-1)+M< p_{0}^{k+c}$$

то есть $\Delta_{k} \geq 1$ при $p>p_{0}$ значит в НОК-ах у числителя и знаменателя будут равные степени вхождения отличных $p_{0}$ простых числах, а значит $N=1$